Count Inversions in Array in DSA Java - Execution Trace

Concept Flow - Count Inversions in Array

Start with array

↓

Divide array into two halves

↓

Recursively count inversions in left half

↓

Recursively count inversions in right half

↓

Merge two halves while counting split inversions

↓

Sum left + right + split inversions

↓

Return total inversion count

The array is split recursively, counting inversions in each half and during merge, then sums all counts.

Execution Sample

DSA Java

int countInversions(int[] arr, int left, int right) {
  if (left >= right) return 0;
  int mid = (left + right) / 2;
  int leftCount = countInversions(arr, left, mid);
  int rightCount = countInversions(arr, mid + 1, right);
  int splitCount = mergeAndCount(arr, left, mid, right);
  return leftCount + rightCount + splitCount;
}

This code counts inversions by dividing the array, counting in halves, and merging while counting cross inversions.

Execution Table

Step	Operation	Subarray Processed	Inversions Counted	Array State
1	Divide array	[0..4]	0	[2, 4, 1, 3, 5]
2	Divide left half	[0..2]	0	[2, 4, 1, 3, 5]
3	Divide left-left half	[0..1]	0	[2, 4, 1, 3, 5]
4	Divide left-left-left half	[0..0]	0	[2, 4, 1, 3, 5]
5	Divide left-left-right half	[1..1]	0	[2, 4, 1, 3, 5]
6	Merge [0..0] and [1..1]	[0..1]	0	[2, 4, 1, 3, 5]
7	Merge [0..1] and [2..2]	[0..2]	2	[1, 2, 4, 3, 5]
8	Divide right half	[3..4]	0	[1, 2, 4, 3, 5]
9	Divide right-left half	[3..3]	0	[1, 2, 4, 3, 5]
10	Divide right-right half	[4..4]	0	[1, 2, 4, 3, 5]
11	Merge [3..3] and [4..4]	[3..4]	1	[1, 2, 4, 3, 5]
12	Merge [0..2] and [3..4]	[0..4]	0	[1, 2, 3, 4, 5]
13	Total inversions	[0..4]	3	[1, 2, 3, 4, 5]

💡 All subarrays processed and merged, total inversion count is 3.

Variable Tracker

Variable	Start	After Step 7	After Step 12	Final
arr	[2,4,1,3,5]	[1,2,4,3,5]	[1,2,3,4,5]	[1,2,3,4,5]
leftCount	0	2	3	3
rightCount	0	0	1	1
splitCount	0	0	0	0
totalInversions	0	2	4	4

Key Moments - 3 Insights

Why do we count inversions during the merge step and not just in the halves?

Because inversions can occur between elements in the left half and right half. The merge step counts these 'split' inversions, as shown in steps 7 and 12 in the execution_table.

Why does the array get sorted during the inversion count process?

The merge step sorts the array while counting inversions. This sorting helps efficiently count cross inversions. The array state changes in execution_table rows 7, 12, and 13 show this.

What happens when the subarray has only one element?

When the subarray size is 1 or 0 (like steps 4 and 5), no inversions exist, so the function returns 0 immediately, as seen in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the array state after step 7?

A [2, 4, 1, 3, 5]

B [1, 2, 3, 4, 5]

C [1, 2, 4, 3, 5]

D [2, 1, 4, 3, 5]

💡 Hint

Check the 'Array State' column in row with Step 7.

At which step does the total inversion count become 3?

A Step 13

B Step 12

C Step 7

D Step 6

💡 Hint

Look at the 'Inversions Counted' and 'Total inversions' in execution_table rows.

If the array was already sorted, how would the inversion count change in the execution_table?

A Inversion count would be negative

B Inversion count would be zero at all steps

C Inversion count would increase at merge steps

D Inversion count would be random

💡 Hint

Inversions count pairs where left element > right element; sorted array has none.

Concept Snapshot

Count Inversions uses divide and conquer:
- Split array into halves
- Recursively count inversions in halves
- Merge halves counting cross inversions
- Sum counts for total
- Array gets sorted during process

Full Transcript

Counting inversions in an array means finding pairs where a larger number appears before a smaller one. We use a divide and conquer method: split the array into halves, count inversions in each half, then merge while counting inversions between halves. The merge step sorts the array and counts 'split' inversions. The total inversion count is the sum of left, right, and split counts. This method is efficient and sorts the array as a side effect.

Practice

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

easy

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

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. 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 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 -> Option A

4. Quick Check:

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

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

Common Mistakes:

• Confusing inversion with sorted order
• Thinking inversion counts equal elements
• Mixing up element positions

2. Which of the following Java code snippets correctly initializes an integer array named arr with values 3, 1, 2?

easy

A. int arr = {3, 1, 2};

B. int[] arr = new int(3, 1, 2);

C. int[] arr = {3, 1, 2};

D. int arr[] = new int[3];

Solution

1. Step 1: Check array declaration syntax

   In Java, arrays are declared with square brackets and initialized with curly braces or using new keyword with curly braces.

2. Step 2: Validate each option

   int[] arr = {3, 1, 2}; uses correct syntax: int[] arr = {3, 1, 2}; int arr = {3, 1, 2}; misses brackets, int[] arr = new int(3, 1, 2); uses wrong constructor syntax, int arr[] = new int[3]; does not initialize to the given values (zeros instead).

3. Final Answer:

   B -> Option C

4. Quick Check:

   Correct array init = int[] arr = {3, 1, 2}; [OK]

Hint: Use int[] arr = {values}; to initialize arrays [OK]

Common Mistakes:

• Missing square brackets in declaration
• Using parentheses instead of braces
• Incorrect use of new keyword

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

medium

A. 2

B. 5

C. 4

D. 3

Solution

1. Step 1: Identify all inversion pairs

   Pairs where first element is greater and appears before second: (2,1), (4,1), (4,3), (4,5) is not inversion, (3,5) no inversion. Actually, count carefully: (2,1), (4,1), (4,3) are 3 inversions. But check if (2,3) or (2,5) are inversions? No. So total 3 inversions.

2. Step 2: Count the pairs

   Counting these pairs gives 3 inversions.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Inversions in [2,4,1,3,5] = 3 [OK]

Hint: Count pairs where left element > right element [OK]

Common Mistakes:

• Counting pairs with equal elements
• Missing some inversion pairs
• Counting sorted pairs as inversions

4. Consider the following Java method to count inversions. What is the error?

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

medium

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

B. The inner loop should start from j = 0

C. The count variable should be initialized inside the loops

D. The method should return void instead of int

Solution

1. Step 1: Analyze the inversion condition

   Inversion means arr[i] > arr[j] where i < j, but code checks arr[i] < arr[j], which is incorrect.

2. Step 2: Identify the fix

   Change condition to arr[i] > arr[j] to correctly count inversions.

3. Final Answer:

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

4. Quick Check:

   Correct condition = arr[i] > arr[j] [OK]

Hint: Inversion means left element greater than right [OK]

Common Mistakes:

• Using wrong comparison operator
• Starting inner loop incorrectly
• Resetting count inside loops

5. Given the array [8, 4, 2, 1], what is the total number of inversions? Also, explain why this number is significant in sorting algorithms.

hard

A. 6; It shows the array is nearly sorted

B. 6; It shows the array is sorted in descending order

C. 4; It shows the array is sorted in ascending order

D. 3; It shows the array has few inversions

Solution

1. Step 1: Count inversions in the array

   Pairs: (8,4), (8,2), (8,1), (4,2), (4,1), (2,1) total 6 inversions.

2. Step 2: Understand significance in sorting

   Maximum inversions mean array is sorted in descending order, which is worst case for some sorting algorithms.

3. Final Answer:

   6; It shows the array is sorted in descending order -> Option B

4. Quick Check:

   Inversions = 6; descending order = max inversions [OK]

Hint: Max inversions = descending order array [OK]

Common Mistakes:

• Miscounting inversion pairs
• Confusing max inversions with sorted array
• Ignoring significance in sorting