Reverse Pairs - Practice Coding Problems

Reverse Pairs - Problem

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set Hard

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.length and
nums[i] > 2 * nums[j]

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,3,2,3,1]

› Output: 2

💡 Note: The reverse pairs are (1,4) where nums[1]=3 > 2*nums[4]=2*1=2, and (3,4) where nums[3]=3 > 2*nums[4]=2*1=2

Example 2 — No Pairs

$ Input: nums = [2,4,3,5,1]

› Output: 3

💡 Note: Pairs: (0,4) since 2>2*1=2 is false, (1,4) since 4>2*1=2 is true, (2,4) since 3>2*1=2 is true, (3,4) since 5>2*1=2 is true

Example 3 — Minimum Size

$ Input: nums = [5,1]

› Output: 1

💡 Note: Only one pair (0,1): 5 > 2*1 = 2, so count = 1

Constraints

1 ≤ nums.length ≤ 5 × 10⁴
-2³¹ ≤ nums[i] ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,3,2,3,1] - find reverse pairs

Check

For each i < j, check if nums[i] > 2 * nums[j]

Count

Return total count of valid pairs

Key Takeaway

🎯 Key Insight: Use merge sort to count reverse pairs efficiently in O(n log n) time

Asked in

G Google 25 M Microsoft 18 A Amazon 15 F Facebook 12

The key insight is to use modified merge sort to count reverse pairs efficiently during the merge process. The optimal approach uses divide and conquer with merge sort to achieve O(n log n) time complexity by counting cross-pairs between subarrays. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	Check all pairs (i,j) where i < j
Binary Search with Sorting	O(n² log n)	O(n)	Sort indices by values and use binary search to count pairs
Merge Sort with Counting	O(n log n)	O(n)	Use modified merge sort to count reverse pairs during merge process

Brute Force — Algorithm Steps

Iterate through each index i from 0 to n-2
For each i, iterate through indices j from i+1 to n-1
Check if nums[i] > 2 * nums[j] and increment count

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup

Start with first element, compare with all elements after it

Compare

Check if nums[i] > 2 * nums[j] for each pair

Count

Increment counter for valid reverse pairs

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if ((long long)nums[i] > 2LL * nums[j]) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[10000];
    int n = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops iterate through all n×n pairs

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses a counter variable, no extra data structures

✓ Linear Space

180.0K Views

Medium Frequency

~35 min Avg. Time

4.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler