Count Inversions in Array in DSA Go - Execution Trace

Concept Flow - Count Inversions in Array

Start with full 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 into halves recursively, counting inversions inside each half and those between halves during merge, then sums all counts.

Execution Sample

DSA Go

func countInversions(arr []int) int {
  if len(arr) <= 1 {
    return 0
  }
  mid := len(arr)/2
  left := make([]int, mid)
  right := make([]int, len(arr)-mid)
  copy(left, arr[:mid])
  copy(right, arr[mid:])
  return countInversions(left) + countInversions(right) + mergeCount(arr, left, right)
}

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

Execution Table

Step	Operation	Array Segment	Inversions Counted	Pointer Changes	Visual State
1	Start with full array	[2, 4, 1, 3, 5]	0	head=0, mid=2, tail=4	[2, 4, 1, 3, 5]
2	Divide into left half	[2, 4]	0	left head=0, left tail=1	[2, 4]
3	Divide into right half	[1, 3, 5]	0	right head=2, right tail=4	[1, 3, 5]
4	Count inversions in left half	[2, 4]	0	left mid=1	[2, 4]
5	Divide left half further	[2]	0	single element	[2]
6	Divide left half further	[4]	0	single element	[4]
7	Merge left halves and count split inversions	[2, 4]	0	pointers i=0, j=0	[2, 4]
8	Count inversions in right half	[1, 3, 5]	0	right mid=3	[1, 3, 5]
9	Divide right half further	[1, 3]	0	right left head=2, tail=3	[1, 3]
10	Divide right half further	[5]	0	single element	[5]
11	Divide right left half further	[1]	0	single element	[1]
12	Divide right left half further	[3]	0	single element	[3]
13	Merge right left halves and count split inversions	[1, 3]	0	pointers i=0, j=0	[1, 3]
14	Merge right halves and count split inversions	[1, 3, 5]	0	pointers i=0, j=0	[1, 3, 5]
15	Merge full array halves and count split inversions	[2, 4, 1, 3, 5]	3	pointers i=0, j=0	[1, 2, 3, 4, 5]
16	Total inversions counted	[2, 4, 1, 3, 5]	3	done	[1, 2, 3, 4, 5]

💡 All subarrays merged and counted, total inversions = 3

Variable Tracker

Variable	Start	After Step 4	After Step 7	After Step 14	After Step 15	Final
arr	[2,4,1,3,5]	[2,4]	[2,4]	[1,3,5]	[1,2,3,4,5]	[1,2,3,4,5]
inversions	0	0	0	0	3	3
left	N/A	[2,4]	[2,4]	[1,3]	[1,2,3,4,5]	[1,2,3,4,5]
right	N/A	[1,3,5]	[1,3,5]	[5]	[4,5]	[4,5]
i (left pointer)	0	0	0	0	2	2
j (right pointer)	0	0	0	0	3	3

Key Moments - 3 Insights

Why do we count inversions during the merge step and not only in the recursive calls?

Because inversions can be between elements in the left half and right half. The merge step compares elements across halves and counts these 'split' inversions, as shown in steps 15 and 16 in the execution_table.

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

The merge step combines two sorted halves into a sorted whole. This sorting is necessary to efficiently count split inversions by comparing elements in order, as seen in the visual state changes in steps 7, 13, 14, and 15.

How do pointer movements (i and j) relate to counting inversions?

Pointer i moves through the left half and j through the right half. When element at j is smaller than element at i, it means all remaining elements from i onwards in left half form inversions with element j. This is counted and pointers updated accordingly, as in step 15.

Visual Quiz - 3 Questions

Look at the execution_table at step 15, how many inversions are counted during the merge?

A 2

B 3

C 0

D 5

💡 Hint

Check the 'Inversions Counted' column at step 15 in execution_table.

At which step does the array segment [1, 3] get merged and counted for inversions?

A Step 13

B Step 7

C Step 15

D Step 4

💡 Hint

Look for the merge operation on [1, 3] in the 'Operation' and 'Array Segment' columns.

If the input array was already sorted, how would the 'Inversions Counted' column change in the execution_table?

A Random values

B Increase by 1 each merge

C All zeros

D Only counted in the last step

💡 Hint

Recall that inversions count pairs where left element is greater than right; sorted arrays have none.

Concept Snapshot

Count Inversions in Array:
- Use divide and conquer (merge sort style)
- Recursively count inversions in left and right halves
- Count split inversions during merge
- Sum all counts for total inversions
- Array gets sorted as a side effect

Full Transcript

Counting inversions in an array means finding how many pairs are out of order. We split the array into halves recursively, count inversions inside each half, then merge halves while counting inversions between them. This merge step compares elements from left and right halves, counting how many elements in left are greater than those in right. The process continues until the whole array is merged and sorted, with the total inversion count returned. This method is efficient and uses the merge sort technique.

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 a pair of elements (i, j) such that i < j but array[i] > array[j].

2. Step 2: Identify the correct description

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

3. Final Answer:

   A -> Option B

4. Quick Check:

   Inversion = pair where first > second and first appears earlier [OK]

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

Common Mistakes:

• Confusing inversion with sorted order
• Thinking inversion counts equal or smaller pairs
• Mixing up element positions

2. Which of the following Go code snippets correctly declares a function to count inversions in an integer slice?

easy

A. func countInversions(arr []int) int { return 0 }

B. func countInversions(arr int[]) int { return 0 }

C. func countInversions(arr []int) void { return 0 }

D. func countInversions(arr []int) int { return "0" }

Solution

1. Step 1: Check function signature syntax in Go

   In Go, a function with an integer slice parameter and integer return type is declared as func name(arr []int) int.

2. Step 2: Validate return statement type

   func countInversions(arr []int) int { return 0 } returns an integer 0, matching the return type. Other options have syntax errors or wrong return types.

3. Final Answer:

   C -> Option A

4. Quick Check:

   Correct Go function syntax returns int [OK]

Hint: Go slices use []int, return type after params [OK]

Common Mistakes:

• Using wrong slice syntax like int[]
• Returning wrong type like string instead of int
• Using void instead of int for return type

3. What is the output of the following Go code snippet?

func main() {
    arr := []int{2, 4, 1, 3, 5}
    fmt.Println(countInversions(arr))
}

func countInversions(arr []int) int {
    count := 0
    for i := 0; i < len(arr); i++ {
        for j := i + 1; j < len(arr); j++ {
            if arr[i] > arr[j] {
                count++
            }
        }
    }
    return count
}

medium

A. 4

B. 5

C. 2

D. 3

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.

2. Step 2: Confirm count from nested loops

   Loops check all pairs i

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Inversions counted = 3 [OK]

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

Common Mistakes:

• Counting pairs where first is smaller
• Missing some inversion pairs
• Confusing index order

4. The following Go function is intended to count inversions but has a bug. What is the bug?

func countInversions(arr []int) int {
    count := 0
    for i := 0; i <= len(arr); i++ {
        for j := i + 1; j < len(arr); j++ {
            if arr[i] > arr[j] {
                count++
            }
        }
    }
    return count
}

medium

A. The outer loop uses <= causing index out of range error

B. The inner loop starts from wrong index

C. The comparison operator should be < instead of >

D. The count variable is not initialized

Solution

1. Step 1: Analyze loop boundaries

   The outer loop runs with i <= len(arr), which means i can equal len(arr), causing arr[i] to be out of range.

2. Step 2: Identify correct loop condition

   The loop should use i < len(arr) to avoid accessing invalid index.

3. Final Answer:

   The outer loop uses <= causing index out of range error -> Option A

4. Quick Check:

   Loop index must be less than length [OK]

Hint: Loop index must be less than length, not less or equal [OK]

Common Mistakes:

• Using <= instead of < in loops
• Starting inner loop at wrong index
• Wrong comparison operator

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 bubble sort swaps count; inversion count is 4

B. Use brute force nested loops; inversion count is 6

C. Use merge sort based method; inversion count is 6

D. Use quicksort partition count; inversion count is 3

Solution

1. Step 1: Understand efficient inversion counting

   Merge sort based method counts inversions in O(n log n) time, more efficient than brute force O(n²).

2. Step 2: Calculate inversion count for [8,4,2,1]

   Inversions: (8,4), (8,2), (8,1), (4,2), (4,1), (2,1) = 6 total.

3. Final Answer:

   Use merge sort based method; inversion count is 6 -> Option C

4. Quick Check:

   Merge sort counts 6 inversions efficiently [OK]

Hint: Use merge sort for fast inversion count [OK]

Common Mistakes:

• Using slow brute force for large arrays
• Miscounting inversion pairs
• Confusing inversion count with swap count