Count Inversions in Array in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is an inversion in an array?

An inversion is a pair of elements where the first element is greater than the second element, but the first element appears before the second in the array.

beginner

Why do we count inversions in an array?

Counting inversions helps measure how far the array is from being sorted. More inversions mean the array is less sorted.

beginner

What is the time complexity of the naive method to count inversions?

The naive method compares every pair and has a time complexity of O(n²), where n is the number of elements.

intermediate

How does the merge sort method help count inversions efficiently?

During merge sort, when merging two sorted halves, we count how many elements from the right half are placed before elements from the left half, which indicates inversions. This reduces time complexity to O(n log n).

intermediate

What is the key step to count inversions during the merge process?

When an element from the right half is smaller than an element from the left half, all remaining elements in the left half form inversions with that right element.

What does an inversion in an array represent?

A A pair where the first element is greater and appears before the second

B A pair where the first element is smaller and appears before the second

C Two equal elements next to each other

D Any two elements in the array

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

What is the time complexity of counting inversions using merge sort?

A O(n²)

B O(n)

C O(log n)

D O(n log n)

Merge sort counts inversions efficiently in O(n log n) time.

During merge sort, when do we count inversions?

A When merging two sorted halves

B When splitting the array

C Before sorting starts

D After the array is fully sorted

Inversions are counted during the merge step when combining sorted halves.

If the array is already sorted, how many inversions does it have?

A Maximum inversions

B Zero inversions

C Half the number of elements

D Cannot be determined

A sorted array has zero inversions because no element is out of order.

What is the naive approach to count inversions?

A Use binary search

B Use merge sort

C Compare every pair of elements

D Use a hash map

The naive method checks every pair to find inversions, which is slow.

Explain how merge sort can be used to count inversions in an array.

Think about how merging two sorted lists reveals inversions.

Describe what an inversion is and why counting inversions is useful.

Imagine how many swaps needed to sort the array.