Count Inversions in Array in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of inversion count for a small array

What is the output of the following JavaScript code that counts inversions in an array?

DSA Javascript

function countInversions(arr) {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] > arr[j]) count++;
    }
  }
  return count;
}

console.log(countInversions([2, 4, 1, 3, 5]));

A 3

B 5

C 2

D 4

💡 Hint

Count pairs where a number appears before a smaller number.

The pairs that are inverted are (2,1), (4,1), and (4,3), totaling 3 inversions.

❓ Predict Output

intermediate

Output of inversion count using merge sort method

What is the output of this JavaScript code that counts inversions using a merge sort approach?

DSA Javascript

function mergeSort(arr) {
  if (arr.length <= 1) return {sorted: arr, count: 0};
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  const merged = [];
  let i = 0, j = 0, count = left.count + right.count;
  while (i < left.sorted.length && j < right.sorted.length) {
    if (left.sorted[i] <= right.sorted[j]) {
      merged.push(left.sorted[i++]);
    } else {
      merged.push(right.sorted[j++]);
      count += left.sorted.length - i;
    }
  }
  while (i < left.sorted.length) merged.push(left.sorted[i++]);
  while (j < right.sorted.length) merged.push(right.sorted[j++]);
  return {sorted: merged, count};
}

const result = mergeSort([8, 4, 2, 1]);
console.log(result.count);

A 7

B 6

C 4

D 5

💡 Hint

Count how many elements from left remain when picking from right during merge.

The array [8,4,2,1] has 6 inversions: (8,4), (8,2), (8,1), (4,2), (4,1), (2,1).

🧠 Conceptual

advanced

Understanding inversion count complexity

What is the time complexity of counting inversions using the merge sort based method for an array of size n?

A O(n log n)

B O(n^2)

C O(log n)

D O(n)

💡 Hint

Think about how merge sort divides and merges the array.

The merge sort method divides the array into halves recursively and merges them counting inversions, leading to O(n log n) time.

🔧 Debug

advanced

Identify the error in inversion count code

What error will this code produce when run?

DSA Javascript

function countInversions(arr) {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] > arr[j]) count++;
    }
  }
  return count;
}

console.log(countInversions([1, 3, 2]));

A Output: 1

B SyntaxError: Unexpected token

C TypeError: Cannot read property of undefined

D Output: 0

💡 Hint

Check the loop boundary for j.

The inner loop runs with j <= arr.length, so arr[j] is undefined when j equals arr.length, causing a TypeError when comparing.

🚀 Application

expert

Count inversions in a large array efficiently

You have an array of 100,000 integers. Which approach is best to count inversions efficiently?

A Sort the array and count inversions by comparing sorted positions (O(n log n))

B Use a nested loop to compare all pairs (O(n^2))

C Use a hash map to count inversions in O(n)

D Use merge sort based counting (O(n log n))

💡 Hint

Consider time complexity for large n.

Nested loops are too slow for large arrays. Merge sort counting is efficient and accurate. Sorting alone does not count inversions. Hash map cannot count inversions in O(n).

Practice

1. What does the term inversion mean in the context of an array?

easy

A. A pair of elements where the first is smaller than the second and appears before it

B. A pair of elements where the first is greater than the second and appears before it

C. The total number of elements in the array

D. The sum of all elements in the array

Solution

1. Step 1: Understand the definition of inversion

   An inversion is when a larger number appears before a smaller number in the array.

2. Step 2: Compare options with the definition

   A pair of elements where the first is greater than the second and appears before it correctly describes this as a pair where the first element is greater and comes before the second.

3. Final Answer:

   A pair of elements where the first is greater than the second and appears before it -> Option B

4. Quick Check:

   Inversion = pair (i, j) with i < j and arr[i] > arr[j] [OK]

Hint: Inversion means bigger number comes before smaller one [OK]

Common Mistakes:

• Confusing inversion with sorted order
• Thinking inversion counts pairs where first is smaller
• Mixing inversion with total elements count

2. Which of the following JavaScript code snippets correctly initializes a variable to count inversions?

easy

A. int count = 0;

B. count := 0;

C. let count = 0;

D. var count == 0;

Solution

1. Step 1: Identify correct JavaScript syntax for variable initialization

   JavaScript uses let or var with = for assignment.

2. Step 2: Check each option

   let count = 0; uses let count = 0; which is correct. count := 0; uses ':=' which is not JavaScript. int count = 0; uses 'int' which is not JavaScript. var count == 0; uses '==' which is a comparison, not assignment.

3. Final Answer:

   let count = 0; -> Option C

4. Quick Check:

   Variable assignment in JS uses =, not := or == [OK]

Hint: Use let or var with = for assignment in JavaScript [OK]

Common Mistakes:

• Using ':=' instead of '='
• Using 'int' keyword from other languages
• Using '==' instead of '=' for assignment

3. What is the number of inversions in the array [2, 4, 1, 3, 5]?

medium

A. 3

B. 2

C. 4

D. 5

Solution

1. Step 1: Identify all inversion pairs in the array

   Check pairs where first element is greater and appears before second:
   - (2,1), (4,1), (4,3)

2. Step 2: Count the total inversions

   There are 3 such pairs.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Pairs (2,1), (4,1), (4,3) = 3 inversions [OK]

Hint: Count pairs where earlier number is bigger than later [OK]

Common Mistakes:

• Counting pairs where first is smaller
• Missing some inversion pairs
• Counting total pairs instead of inversions

4. Consider this code snippet to count inversions:

function countInversions(arr) {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] < arr[j]) {
        count++;
      }
    }
  }
  return count;
}

What is the error in this code?

medium

A. The function should return arr.length instead of count

B. The inner loop should start from j = 0

C. The count variable should be initialized inside the loops

D. The comparison should be arr[i] > arr[j] to count inversions

Solution

1. Step 1: Understand the inversion condition

   An inversion is when arr[i] > arr[j] and i < j, but code checks arr[i] < arr[j].

2. Step 2: Identify the fix

   The comparison should be changed to arr[i] > arr[j] to count inversions correctly.

3. Final Answer:

   The comparison should be arr[i] > arr[j] to count inversions -> Option D

4. Quick Check:

   Inversion means first element bigger, so use > [OK]

Hint: Use > to detect inversion pairs, not < [OK]

Common Mistakes:

• Using < instead of > in condition
• Starting inner loop from 0 instead of i+1
• Resetting count inside loops

5. Given the array [8, 4, 2, 1], which approach will efficiently count the number of inversions?

hard

A. Sort the array and count inversions during merge (O(n log n) time)

B. Count inversions by summing all elements

C. Use a nested loop to compare all pairs (O(n²) time)

D. Use a hash map to store counts of elements

Solution

1. Step 1: Understand the problem size and efficiency

   For larger arrays, nested loops (O(n²)) are slow. Merge sort based counting is efficient (O(n log n)).

2. Step 2: Identify the best approach

   Counting inversions during merge sort is a classic efficient method.

3. Final Answer:

   Sort the array and count inversions during merge (O(n log n) time) -> Option A

4. Quick Check:

   Merge sort inversion count = efficient O(n log n) [OK]

Hint: Use merge sort to count inversions efficiently [OK]

Common Mistakes:

• Using nested loops for large arrays causing slow performance
• Trying to sum elements instead of counting pairs
• Using hash maps which don't help count inversions