Count Inversions in Array in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the inversion count variable.

DSA Typescript

let inversionCount = [1];

Drag options to blanks, or click blank then click option'

Anull

B1

Cundefined

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Starting the count from 1 instead of 0.

Using null or undefined which are not numbers.

We start counting inversions from zero because initially no pairs are counted.

2fill in blank

medium

Complete the code to compare two elements for inversion detection.

DSA Typescript

if (arr[i] [1] arr[j]) {

Drag options to blanks, or click blank then click option'

A<

B>

C===

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using less than instead of greater than.

Checking for equality instead of order.

An inversion is when a larger element appears before a smaller one, so we check if arr[i] > arr[j].

3fill in blank

hard

Fix the error in the merge function to correctly count inversions.

DSA Typescript

while (i < left.length && j < right.length) {
  if (left[i] <= right[j]) {
    merged.push(left[i]);
    i++;
  } else {
    merged.push(right[j]);
    inversionCount += [1];
    j++;
  }
}

Drag options to blanks, or click blank then click option'

Aleft.length - i

Bright.length - j

Ci + j

Dleft.length + right.length

Attempts:

3 left

💡 Hint

Common Mistakes

Counting elements from the right array instead of left.

Adding total lengths instead of remaining elements.

When an element from right is smaller, all remaining elements in left from index i form inversions.

4fill in blank

hard

Fill both blanks to complete the merge sort recursive calls.

DSA Typescript

const left = arr.slice(0, [1]);
const right = arr.slice([2]);

Drag options to blanks, or click blank then click option'

A0

BMath.floor(arr.length / 2)

CMath.ceil(arr.length / 2)

Darr.length

Attempts:

3 left

💡 Hint

Common Mistakes

Using ceil instead of floor for middle index.

Starting left slice at middle instead of 0.

We split the array into two halves: left from 0 to middle, right from middle to end.

5fill in blank

hard

Fill both blanks to complete the inversion count function using merge sort.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

A1

B2

C3

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 as base case length.

Dividing by 3 or other numbers instead of 2.

Using mid incorrectly in slicing.

The base case is when array length is 1 or less, mid is found by dividing length by 2, and mid is used to slice the array.

Practice

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

easy

A. The sum of all elements in the array

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

C. The total number of elements in the array

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

Solution

1. Step 1: Understand the definition of inversion

   An inversion is a pair of elements (i, j) such that i < j but array[i] > array[j].

2. Step 2: Compare options with definition

   A pair of elements where the first is greater than the second and appears before it correctly describes this condition. Other options describe unrelated concepts.

3. Final Answer:

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

4. Quick Check:

   Inversion = pair where earlier element > later element [OK]

Hint: Inversion means earlier bigger than later element [OK]

Common Mistakes:

• Confusing inversion with sorted order
• Thinking inversion counts total elements
• Mixing up greater and smaller element order

2. Which of the following TypeScript function signatures correctly represents a function to count inversions in an array of numbers?

easy

A. function countInversions(arr: string): number[]

B. function countInversions(arr: number): string

C. function countInversions(arr: number[]): number

D. function countInversions(arr: any): void

Solution

1. Step 1: Analyze the function purpose and parameters

   The function should take an array of numbers and return a number representing the count of inversions.

2. Step 2: Match the correct signature

   function countInversions(arr: number[]): number matches this: input is number array, output is number. Others mismatch input/output types.

3. Final Answer:

   function countInversions(arr: number[]): number -> Option C

4. Quick Check:

   Input array, output number count [OK]

Hint: Input array of numbers, output single number [OK]

Common Mistakes:

• Using wrong input type like string instead of array
• Returning array instead of number
• Using void return type when output is needed

3. What is the output of the following TypeScript code?

function countInversions(arr: number[]): number {
  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]));

medium

A. 3

B. 4

C. 2

D. 5

Solution

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

   Array: [2, 4, 1, 3, 5]. Inversions are (2,1), (4,1), (4,3). Total 3 inversions.

2. Step 2: Confirm the count returned by the nested loops

   The nested loops count each inversion correctly, so output is 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Inversions = 3 [OK]

Hint: Count pairs where earlier > later element [OK]

Common Mistakes:

• Counting pairs incorrectly by missing some
• Confusing equal elements as inversions
• Off-by-one errors in loops

4. The following code attempts to count inversions but has a bug. What is the bug?

function countInversions(arr: number[]): number {
  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;
}

medium

A. The inner loop should start from j = 0 instead of i + 1

B. The outer loop condition should be < instead of <= to avoid out-of-bounds

C. The count variable should be reset inside the outer loop

D. The comparison should be arr[i] < arr[j] instead of >

Solution

1. Step 1: Analyze the outer loop condition

   The outer loop runs from i = 0 to i <= arr.length, which means i can be arr.length, causing arr[i] to be undefined (out-of-bounds).

2. Step 2: Correct the loop condition

   Changing to i < arr.length prevents out-of-bounds access and fixes the bug.

3. Final Answer:

   The outer loop condition should be < instead of <= to avoid out-of-bounds -> Option B

4. Quick Check:

   Loop bounds must prevent out-of-range access [OK]

Hint: Use < length, not <= length in loops [OK]

Common Mistakes:

• Using <= causes index out-of-bounds error
• Resetting count inside loop loses total count
• Changing comparison reverses inversion logic

5. Given the array [8, 4, 2, 1], which approach is the most efficient to count inversions and what is the inversion count?

hard

A. Use a modified merge sort to count inversions; count is 6

B. Use nested loops to count inversions; count is 3

C. Sort the array and count differences; count is 4

D. Use a hash map to count inversions; count is 5

Solution

1. Step 1: Identify inversion count manually

   Array: [8,4,2,1]. Inversions are (8,4), (8,2), (8,1), (4,2), (4,1), (2,1) totaling 6.

2. Step 2: Choose the most efficient method

   Modified merge sort counts inversions in O(n log n), better than nested loops O(n²). Hash map or sorting differences do not directly count inversions.

3. Final Answer:

   Use a modified merge sort to count inversions; count is 6 -> Option A

4. Quick Check:

   Merge sort method = 6 inversions [OK]

Hint: Use merge sort for large arrays to count inversions fast [OK]

Common Mistakes:

• Counting inversions incorrectly by missing pairs
• Using nested loops for large arrays causing slow performance
• Confusing sorting with inversion counting