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

Challenge - 5 Problems

❓ Predict Output

intermediate

Count inversions using merge sort

What is the output of the following Java code that counts inversions in an array using merge sort?

DSA Java

public class InversionCount {
    public static int mergeSort(int[] arr, int[] temp, int left, int right) {
        int mid, invCount = 0;
        if (right > left) {
            mid = (right + left) / 2;
            invCount += mergeSort(arr, temp, left, mid);
            invCount += mergeSort(arr, temp, mid + 1, right);
            invCount += merge(arr, temp, left, mid + 1, right);
        }
        return invCount;
    }

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

    public static void main(String[] args) {
        int[] arr = {2, 4, 1, 3, 5};
        int[] temp = new int[arr.length];
        int result = mergeSort(arr, temp, 0, arr.length - 1);
        System.out.println(result);
    }
}

A 4

B 3

C 2

D 5

💡 Hint

Count pairs where left element is greater than right element during merge.

The code counts inversions by merging sorted halves and counting how many elements from the left half are greater than elements in the right half. For the array {2,4,1,3,5}, the inversions are (2,1), (4,1), and (4,3), totaling 3.

❓ Predict Output

intermediate

Count inversions in a sorted array

What is the output of the following Java code counting inversions in a sorted array?

DSA Java

public class InversionCount {
    public static int mergeSort(int[] arr, int[] temp, int left, int right) {
        int mid, invCount = 0;
        if (right > left) {
            mid = (right + left) / 2;
            invCount += mergeSort(arr, temp, left, mid);
            invCount += mergeSort(arr, temp, mid + 1, right);
            invCount += merge(arr, temp, left, mid + 1, right);
        }
        return invCount;
    }

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

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int[] temp = new int[arr.length];
        int result = mergeSort(arr, temp, 0, arr.length - 1);
        System.out.println(result);
    }
}

A 1

B 4

C 0

D 5

💡 Hint

A sorted array has no inversions.

Since the array is already sorted in ascending order, there are no pairs where a left element is greater than a right element, so the inversion count is zero.

🔧 Debug

advanced

Identify the error in inversion count code

What error will the following Java code produce when run?

DSA Java

public class InversionCount {
    public static int mergeSort(int[] arr, int[] temp, int left, int right) {
        int mid, invCount = 0;
        if (right >= left) {
            mid = (right + left) / 2;
            invCount += mergeSort(arr, temp, left, mid);
            invCount += mergeSort(arr, temp, mid + 1, right);
            invCount += merge(arr, temp, left, mid + 1, right);
        }
        return invCount;
    }

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

    public static void main(String[] args) {
        int[] arr = {2, 3, 8, 6, 1};
        int[] temp = new int[arr.length];
        int result = mergeSort(arr, temp, 0, arr.length - 1);
        System.out.println(result);
    }
}

A StackOverflowError due to infinite recursion

B No error, prints correct inversion count

C ArrayIndexOutOfBoundsException during merge

D NullPointerException due to uninitialized array

💡 Hint

Check the base condition for recursion termination.

The base condition uses 'if (right >= left)' which is always true when right == left, causing infinite recursion and eventually StackOverflowError.

❓ Predict Output

advanced

Count inversions in a reversed array

What is the output of the following Java code counting inversions in a reversed array?

DSA Java

public class InversionCount {
    public static int mergeSort(int[] arr, int[] temp, int left, int right) {
        int mid, invCount = 0;
        if (right > left) {
            mid = (right + left) / 2;
            invCount += mergeSort(arr, temp, left, mid);
            invCount += mergeSort(arr, temp, mid + 1, right);
            invCount += merge(arr, temp, left, mid + 1, right);
        }
        return invCount;
    }

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

    public static void main(String[] args) {
        int[] arr = {5, 4, 3, 2, 1};
        int[] temp = new int[arr.length];
        int result = mergeSort(arr, temp, 0, arr.length - 1);
        System.out.println(result);
    }
}

A 15

B 5

C 0

D 10

💡 Hint

Count all pairs where left element is greater than right element in reversed array.

A reversed array of size 5 has maximum inversions: 5*4/2 = 10. The code counts all these pairs correctly.

🧠 Conceptual

expert

Time complexity of inversion count using merge sort

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

A O(n log n)

B O(n^2)

C O(log n)

D O(n)

💡 Hint

Consider the divide and conquer nature of merge sort.

The merge sort based inversion count divides the array and merges in O(n) time at each level, with log n levels, resulting in O(n log n) time complexity.

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