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

Challenge - 5 Problems

❓ Predict Output

intermediate

Count Inversions Output for Small Array

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

DSA Go

package main
import "fmt"

func merge(arr []int, temp []int, left int, mid int, right int) int {
    i := left
    j := mid
    k := left
    invCount := 0
    for i < mid && j <= right {
        if arr[i] <= arr[j] {
            temp[k] = arr[i]
            i++
            k++
        } else {
            temp[k] = arr[j]
            invCount += mid - i
            j++
            k++
        }
    }
    for i < mid {
        temp[k] = arr[i]
        i++
        k++
    }
    for j <= right {
        temp[k] = arr[j]
        j++
        k++
    }
    for x := left; x <= right; x++ {
        arr[x] = temp[x]
    }
    return invCount
}

func mergeSort(arr []int, temp []int, left int, right int) int {
    invCount := 0
    if right > left {
        mid := (left + right) / 2
        invCount += mergeSort(arr, temp, left, mid)
        invCount += mergeSort(arr, temp, mid+1, right)
        invCount += merge(arr, temp, left, mid+1, right)
    }
    return invCount
}

func countInversions(arr []int) int {
    temp := make([]int, len(arr))
    return mergeSort(arr, temp, 0, len(arr)-1)
}

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

A 2

B 4

C 3

D 5

💡 Hint

Count pairs where a larger number appears before a smaller number.

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

🧠 Conceptual

intermediate

Understanding Inversion Count Concept

Which of the following best describes what an inversion in an array means?

A Two elements that are equal and appear consecutively in the array.

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

C Any two elements that are adjacent in the array regardless of their values.

D A pair of elements where the first is smaller than the second and appears after it in the array.

💡 Hint

Think about pairs that are out of order.

An inversion is when a bigger number comes before a smaller number in the array.

❓ Predict Output

advanced

Count Inversions Output for Descending Array

What is the output of this Go code counting inversions for a descending array?

DSA Go

package main
import "fmt"

func merge(arr []int, temp []int, left int, mid int, right int) int {
    i := left
    j := mid
    k := left
    invCount := 0
    for i < mid && j <= right {
        if arr[i] <= arr[j] {
            temp[k] = arr[i]
            i++
            k++
        } else {
            temp[k] = arr[j]
            invCount += mid - i
            j++
            k++
        }
    }
    for i < mid {
        temp[k] = arr[i]
        i++
        k++
    }
    for j <= right {
        temp[k] = arr[j]
        j++
        k++
    }
    for x := left; x <= right; x++ {
        arr[x] = temp[x]
    }
    return invCount
}

func mergeSort(arr []int, temp []int, left int, right int) int {
    invCount := 0
    if right > left {
        mid := (left + right) / 2
        invCount += mergeSort(arr, temp, left, mid)
        invCount += mergeSort(arr, temp, mid+1, right)
        invCount += merge(arr, temp, left, mid+1, right)
    }
    return invCount
}

func countInversions(arr []int) int {
    temp := make([]int, len(arr))
    return mergeSort(arr, temp, 0, len(arr)-1)
}

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

A 10

B 5

C 15

D 0

💡 Hint

Count all pairs where a bigger number is before a smaller number in a fully descending array.

For 5 elements in descending order, total inversions = 5*4/2 = 10.

🔧 Debug

advanced

Identify the Bug in Inversion Count Code

What error will this Go code produce when counting inversions?

DSA Go

package main
import "fmt"

func merge(arr []int, temp []int, left int, mid int, right int) int {
    i := left
    j := mid
    k := left
    invCount := 0
    for i < mid && j <= right {
        if arr[i] < arr[j] { // bug here: should be <=
            temp[k] = arr[i]
            i++
            k++
        } else {
            temp[k] = arr[j]
            invCount += mid - i
            j++
            k++
        }
    }
    for i < mid {
        temp[k] = arr[i]
        i++
        k++
    }
    for j <= right {
        temp[k] = arr[j]
        j++
        k++
    }
    for x := left; x <= right; x++ {
        arr[x] = temp[x]
    }
    return invCount
}

func mergeSort(arr []int, temp []int, left int, right int) int {
    invCount := 0
    if right > left {
        mid := (left + right) / 2
        invCount += mergeSort(arr, temp, left, mid)
        invCount += mergeSort(arr, temp, mid+1, right)
        invCount += merge(arr, temp, left, mid+1, right)
    }
    return invCount
}

func countInversions(arr []int) int {
    temp := make([]int, len(arr))
    return mergeSort(arr, temp, 0, len(arr)-1)
}

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

A The code outputs 2 instead of 3

B The code outputs 3 correctly

C The code outputs 4 instead of 3

D The code causes a runtime panic due to index out of range

💡 Hint

Check the comparison operator in the merge function.

Using '<' instead of '<=' skips counting some equal elements correctly, causing undercount.

🚀 Application

expert

Maximum Inversions in Array of Size N

For an array of size N, what is the maximum number of inversions possible?

A N + 1

B N * N

C N - 1

D N * (N - 1) / 2

💡 Hint

Think about the array sorted in descending order.

Maximum inversions occur when every pair is inverted, which is N*(N-1)/2.

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