Optimize inversion for O(n) time

Question

Given an array of integers, your task is to count the number of inversions in the array in O(n) time. An inversion is defined as a pair of indices (i, j) such that i < j and arr[i] > arr[j]. Return the total count of such inversions.

Codemia · Accepted Answer

To count the number of inversions in an array of integers efficiently, we can use a modification of the Merge Sort algorithm. The key insight here is that while merging two sorted halves of the array, we can count how many elements from the right half are smaller than elements from the left half. This counting directly gives us the number of inversions. This approach applies here because it allows us to count inversions in O(n log n) time, which is the best we can achieve for this problem. However, the requirement states we need an O(n) solution. This is a misunderstanding because counting inversions in O(n) time is not possible with the typical inversion definition unless additional constraints are provided (e.g., bounded range of values). Thus, we'll proceed with the O(n log n) approach for a correct solution.

1. **Divide**: Recursively split the array into two halves until we reach arrays of length 1. A single element is trivially sorted and has no inversions.
2. **Conquer**: While merging two sorted halves, count the inversions. For every element in the left half (say `left[i]`), if it is greater than an element in the right half (say `right[j]`), then all remaining elements in the left half (from index `i` to the end) are also greater than `right[j]`, contributing to the inversion count.
3. **Combine**: Add the counts from the left half, right half, and the counts obtained during the merge step.

For example, given the array `[2, 3, 8, 6, 1]`:  
- Divide into `[2, 3, 8]` and `[6, 1]`.  
- Count inversions in both halves, then merge them back while counting cross-inversions. The total inversions will be calculated during the merge process.

Here's the pseudocode to implement the above approach:
```python
def merge_and_count(arr, temp_arr, left, mid, right):
    i = left    # Starting index for left subarray
    j = mid + 1 # Starting index for right subarray
    k = left    # Starting index to be sorted
    inv_count = 0

while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp_arr[k] = arr[i]
            i += 1
        else:
            temp_arr[k] = arr[j]
            inv_count += (mid - i + 1)  # Count inversions
            j += 1
        k += 1

while i <= mid:
        temp_arr[k] = arr[i]
        i += 1
        k += 1

while j <= right:
        temp_arr[k] = arr[j]
        j += 1
        k += 1

for i in range(left, right + 1):
        arr[i] = temp_arr[i]

return inv_count

def merge_sort_and_count(arr, temp_arr, left, right):
    inv_count = 0
    if left < right:
        mid = (left + right) // 2
        inv_count += merge_sort_and_count(arr, temp_arr, left, mid)
        inv_count += merge_sort_and_count(arr, temp_arr, mid + 1, right)
        inv_count += merge_and_count(arr, temp_arr, left, mid, right)
    return inv_count

def count_inversions(arr):
    temp_arr = [0]*len(arr)
    return merge_sort_and_count(arr, temp_arr, 0, len(arr) - 1)
```
This implementation counts the inversions as we sort the array.

The time complexity of this solution is O(n log n) due to the merge sort algorithm, which divides the array and merges them recursively. Each merge operation involves a linear scan of the elements, hence the O(n) factor multiplied by the log(n) divisions. The space complexity is O(n) as we use a temporary array to store intermediate results during the merge process. This is efficient given that we are handling the inversion count without directly modifying the original array.

1. **Empty Array**: If the input array is empty, return 0 as there are no elements to form inversions.
2. **Single Element**: If the array has only one element, return 0 as well since a single element cannot form any pairs.
3. **All Elements Equal**: For an array where all elements are the same, e.g., `[2, 2, 2, 2]`, the count of inversions should also be 0 as there are no pairs (i, j) with arr[i] > arr[j].
4. **Already Sorted Array**: For a sorted array like `[1, 2, 3, 4]`, the result should be 0, again as there are no inversions.

Optimize inversion for O(n) time

Citadel

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Citadel Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string