226. Out-of-Order Pairs
A conveyor belt carries parcels with the weights nums[0], nums[1], ..., nums[n-1] in that order. Ideally, the weights would never decrease as the belt moves. A pair of positions (i, j) with i < j is out of order when the earlier parcel is strictly heavier than the later one, that is nums[i] > nums[j].
Count all out-of-order pairs and return the count. Equal weights are not out of order. For example, in the weights [3, 3, 1] the pairs (0, 2) and (1, 2) are out of order, so the answer is 2.
The belt may hold 50,000 parcels. The count can be as large as about 1.25 × 109, so make sure you use a 64-bit counter.
Example 1
- Input:
- nums = [6,2,5,5,1]
- Output:
- 7
- Explanation:
Out-of-order pairs: 6 with each of 2, 5, 5, 1 (4 pairs), 2 with 1 (1 pair), and each 5 with 1 (2 pairs): 7 in total. The two equal 5s do not count.
Example 2
- Input:
- nums = [1,2,2,9]
- Output:
- 0
- Explanation:
The weights never decrease, so there are no out-of-order pairs.
Example 3
- Input:
- nums = [3,3,2]
- Output:
- 2
- Explanation:
Both 3s are heavier than the 2 that comes after them: 2 pairs.
Constraints
1 ≤ nums.length ≤ 5 × 104
-109 ≤ nums[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)