If you\u2019re preparing for coding interviews, the “Count Inversions” problem is a classic and important question. In this blog, we\u2019ll explain the problem, walk you through the brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.<\/p>\n\n\n\n
Given an array of integers arr[]<\/strong>. Find the Inversion Count<\/strong> in the array. Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n Inversion Count<\/strong>: <\/em>For an array, inversion count indicates how far (or close) the array is from being sorted. If the array is already sorted then the inversion count is 0. Examples:<\/strong><\/p>\n\n\n\n Constraints:<\/strong> Let\u2019s solve the problem in the simplest way:<\/p>\n\n\n\n This approach is easy to understand but not efficient for large arrays.<\/p>\n\n\n\n
Two elements arr[i] and arr[j] form an inversion if arr[i] > arr[j]<\/strong> and i < j<\/strong>.<\/p>\n\n\n\n\n
If an array is sorted in the reverse order then the inversion count is the maximum. <\/p>\n<\/blockquote>\n\n\n\nInput<\/strong>: arr[] = [2, 4, 1, 3, 5]
Output<\/strong>: 3\nExplanation<\/strong>: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).<\/pre>\n\n\n\nInput<\/strong>: arr[] = [2, 3, 4, 5, 6]
Output<\/strong>: 0\nExplanation<\/strong>: As the sequence is already sorted so there is no inversion count.<\/pre>\n\n\n\nInput<\/strong>: arr[] = [10, 10, 10]
Output<\/strong>: 0\nExplanation<\/strong>: As all the elements of array are same, so there is no inversion count.<\/pre>\n\n\n\n
1 \u2264 arr.size() \u2264 105
<\/sup>1 \u2264 arr[i] \u2264 104<\/sup><\/p>\n\n\n
\n\n\n\nBrute Force Solution (Nested Loops)<\/h2>\n\n\n\n
Intuition and Approach<\/h3>\n\n\n\n
\n
For each element, compare it with every element that comes after it.<\/li>\n\n\n\n
If the current element is greater than the next one, it\u2019s an inversion.<\/li>\n\n\n\n
We check all possible pairs, so we count every inversion.<\/li>\n<\/ol>\n\n\n\nCode Implementation<\/h3>\n\n\n\n