Reverse Pairs
HardPrompt
Given an integer array nums, return the number of reverse pairs in the array.
A reverse pair is a pair (i, j) where:
0 <= i < j < nums.lengthandnums[i] > 2 * nums[j].
Example 1:
Input: nums = [1,3,2,3,1]
Output: 2
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 3, nums[4] = 1, 3 > 2 * 1Example 2:
Input: nums = [2,4,3,5,1]
Output: 3
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 4, nums[4] = 1, 4 > 2 * 1
(2, 4) --> nums[2] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 5, nums[4] = 1, 5 > 2 * 1
Constraints:
1 <= nums.length <= 5 * 104-231 <= nums[i] <= 231 - 1
Approaches
2 approaches with complexity analysis and trade-offs.
This is the most straightforward approach, which involves checking every possible pair of indices (i, j) where i < j and testing if they satisfy the reverse pair condition.
Algorithm
- Initialize a counter
countto 0. - Use two nested loops. The outer loop iterates with index
ifrom0ton-1. - The inner loop iterates with index
jfromi + 1ton-1. - Inside the inner loop, check if the condition
(long)nums[i] > 2 * (long)nums[j]is met. Casting tolongis important to prevent integer overflow. - If the condition is true, increment the
count. - After the loops complete, return the final
count.
Walkthrough
The algorithm iterates through all possible pairs of elements in the array. For each element nums[i], it scans the rest of the array to its right (elements nums[j] where j > i). For each such pair, it checks if nums[i] is greater than 2 * nums[j]. A counter is used to keep track of how many such pairs are found. To avoid potential integer overflow when calculating 2 * nums[j] (since nums[j] can be large), it's crucial to cast the numbers to a 64-bit integer type (long in Java) before performing the multiplication and comparison.
class Solution { public int reversePairs(int[] nums) { int count = 0; int n = nums.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if ((long) nums[i] > 2 * (long) nums[j]) { count++; } } } return count; }}Complexity
Time
O(N^2), where N is the number of elements in the array. The two nested loops result in a quadratic number of pair comparisons.
Space
O(1), as we only use a constant amount of extra space for the counter and loop indices.
Trade-offs
Pros
Very simple to understand and implement.
Requires no extra space apart from a few variables for loops and the counter.
Cons
Highly inefficient for large arrays. It will result in a "Time Limit Exceeded" (TLE) error for the given constraints (
N <= 5 * 10^4).
Solutions
Solution
class Solution {public int reversePairs(int[] nums) { TreeSet<Long> ts = new TreeSet<>(); for (int num : nums) { ts.add((long)num); ts.add((long)num * 2); } Map<Long, Integer> m = new HashMap<>(); int idx = 0; for (long num : ts) { m.put(num, ++idx); } BinaryIndexedTree tree = new BinaryIndexedTree(m.size()); int ans = 0; for (int i = nums.length - 1; i >= 0; --i) { int x = m.get((long)nums[i]); ans += tree.query(x - 1); tree.update(m.get((long)nums[i] * 2), 1); } return ans; }} class BinaryIndexedTree {private int n;private int[] c;public BinaryIndexedTree(int n) { this.n = n; c = new int[n + 1]; }public void update(int x, int delta) { while (x <= n) { c[x] += delta; x += lowbit(x); } }public int query(int x) { int s = 0; while (x > 0) { s += c[x]; x -= lowbit(x); } return s; }public static int lowbit(int x) { return x & -x; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.