Counting inversions in an array with typescript

user_12536796 0
Viewed 229

I've been banging my head against this error for a couple of hours now and can't seem to find where the error is.

I'm trying to count the inversions in a given array and all my tests pass except when using this array as input [6, 1, 2, 5, 4, 3].

The logic is as follows; given array A[1... n], for every i < j, find all inversion pairs such that A[i] > A[j]

The number I receive for this array is 14 inversions and the correct answer is 8.

The code so far is this

function mergeCount(left: number[], right: number[]): number {
  let count = 0;
  let leftCounter = 0;
  let rightCounter = 0;

  while (leftCounter < left.length && rightCounter < right.length) {
    if (left[leftCounter] < right[rightCounter]) {
      leftCounter += 1;
    } else {
      count += left.length - leftCounter;
      rightCounter += 1;
    }
  }

  return count;
}

function countInversions(input: number[]): number {
  if (input.length < 2) return 0;

  const middle = Math.floor(input.length / 2);

  const left = input.slice(0, middle);
  const right = input.slice(middle);

  return countInversions(left) + countInversions(right) + mergeCount(left, right);
}

Any idea what I'm missing or what's wrong with my code?

EDIT:

So the problem was that I wasn't sorting the arrays when splitting them up, I was just updating the counter. The working solution that I came up with is the following

function mergeCount(left: number[], right: number[]): { output: number[]; count: number } {
  let count = 0;
  let leftCounter = 0;
  let rightCounter = 0;
  const output: number[] = [];

  while (leftCounter < left.length && rightCounter < right.length) {
    if (left[leftCounter] < right[rightCounter]) {
      output.push(left[leftCounter]);
      leftCounter += 1;
    } else {
      output.push(right[rightCounter]);
      count += left.length - leftCounter;
      rightCounter += 1;
    }
  }

  return {
    output: output.concat(left.slice(leftCounter)).concat(right.slice(rightCounter)),
    count,
  };
}

function countInversions(input: number[]): { output: number[]; count: number } {
  if (input.length < 2) return { output: input, count: 0 };

  const middle = Math.floor(input.length / 2);

  const { output: left, count: a } = countInversions(input.slice(0, middle));
  const { output: right, count: b } = countInversions(input.slice(middle));
  const { output, count: c } = mergeCount(left, right);

  return { output, count: a + b + c };
}
typescript mergesort arrays algorithm
2 Answers

The Python code you linked to also sorts the array - you do not. This can cause wrong answers, because the mergesort-based inversion counting algorithm requires that you also sort the array while you're at it (otherwise, the shortcut it uses won't be valid).

Simply merge left and right in your mergeCount function, return that too and it should work.

The highlighted Python below is what's missing in your code:

 while i < left_len and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]) # this
            i += 1
        else:
            result.append(right[j]) # and this
            count += left_len - i
            j += 1

To give more background on the mergesort inversion-counting idea:

In mergesort, we have two sorted halves H1 and H2: H1 is sorted, H2 is sorted. We have a merge function that merges these two, efficiently, into one big sorted array.

Now, that is (well, should be) done in the OP's while loop. Note that, if, using his notation:

left[leftCounter] > right[rightCounter]

(his else condition), then because left is sorted, all the elements after leftCounter will also be larger than right[rightCounter], so we have left.length - leftCounter inversions - allowing us to count more than 1 at once.

Of course, this only holds if you let mergesort do its thing and actually sort the array.

user_2702870

The current implementation looks quite complicated. I think it could be a lot simpler (and accurate).

Iterate over all elements in an outer loop. Let's call the index i. Inside the inner loop, iterate over all elements greater than i and compare them against the outer index element.

function countInversions(input: number[]): number {
    let count = 0;
    for (let i = 0; i < input.length; i++) {
        for (const num of input.slice(i + 1)) {
            if (input[i] > num) {
                count++;
            }
        }
    }
    return count;
}
user_95152070
Related