mediumTwo PointersPattern: Mixed
Count Inversions in Merging Solution
Problem Statement
You are given a sequence of integers `sequence` of length `n`. The task is to count the number of inversions in the sequence, where an inversion is defined as a pair of elements `sequence[i]` and `sequence[j]` such that `i < j` and `sequence[i] > sequence[j]`. You need to implement a function to compute this inversion count.
Examples
Example 1:
Input:{"sequence":[135246]}
Output:3
Explanation: The reverse pairs are (3,2), (5,2), (5,4)
Example 2:
Input:{"sequence":[4321]}
Output:6
Explanation: All pairs are reverse pairs: (4,3), (4,2), (4,1), (3,2), (3,1), (2,1)
Example 3:
Input:{"sequence":[12345]}
Output:0
Explanation: There are no reverse pairs since the sequence is sorted in ascending order
Constraints
- Length of the array will be in the range [1, 1000].
- Array elements will be integers in the range [-10^5, 10^5].
Time: O(n) Space: O(1)
Analyze constraints and compute optimal solutions step-by-step.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.