Count Out-of-Order Pairs
Solve this ProblemEasy15 min
Topics
BasicsComplexityArraysSorting
Companies
TCSInfosysWipro
Given an array
nums, return how many pairs of positions i < j have nums[i] > nums[j] — pairs that appear in the wrong order compared with a sorted array.
This count measures how unsorted an array is, and both solutions here are typical O(n²)Quadratic Time O(n²)Work that grows with the square of the input: doubling n makes it about four times slower. algorithms: two loops, one nested inside the other, each running up to n times. Quadratic code is fine for hundreds of values but becomes painfully slow for millions.
Test Case 1:
Input:nums = [3, 1, 2]
Output:2
Explanation:(3, 1) and (3, 2) are out of order; (1, 2) is fine.
Test Case 2:
Input:nums = [1, 2, 3]
Output:0
Explanation:Already sorted, so no pair is out of order.
Constraints
- ◆
1 ≤ nums.length ≤ 500 - ◆
-1000000 ≤ nums[i] ≤ 1000000
Try the Dry Run
Approach & Solutions
Check Every PairGood
A pair of positions i < j is "out of order" when nums[i] > nums[j]. Two nested loops visit every such pair once and count the bad ones. The inner loop runs about n/2 times on average for each of the n outer steps: n²/2 checks, which is O(n²).
Time
O(n²)Space
O(1)Java
class Solution {
public int countInversions(int[] nums) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] > nums[j]) {
count++;
}
}
}
return count;
}
}Count Swaps in Bubble SortBetter
Bubble sort only ever swaps two neighbours that are out of order, and each such swap fixes exactly one out-of-order pair. So sorting a copy with bubble sort and counting the swaps gives the same answer. It is another classic O(n²) algorithm: two nested loops over the array.
Time
O(n²)Space
O(n)Java
class Solution {
public int countInversions(int[] nums) {
int[] values = nums.clone();
int swaps = 0;
for (int pass = 0; pass < values.length - 1; pass++) {
for (int i = 0; i < values.length - 1 - pass; i++) {
if (values[i] > values[i + 1]) {
int tmp = values[i];
values[i] = values[i + 1];
values[i + 1] = tmp;
swaps++;
}
}
}
return swaps;
}
}