The O(n) Club: Reverse Pairs & That Merge Sort Plot Twist

The O(n) Club: Reverse Pairs & That Merge Sort Plot Twist

⚡ TL;DR

LeetCode 493 asks: How many index pairs (i, j) have i 2 * nums[j]?
Brute force is O(n²): only run that on arrays as small as your willpower after 10 interview rejections. The real play? Modified merge sort counts reverse pairs in O(n log n) without melting your laptop.

// Classic brute force (seriously, don't):
int count = 0;
for (int i = 0; i < nums.length; i++) {
    for (int j = i + 1; j < nums.length; j++) {
        if (nums[i] > 2L * nums[j]) count++;
    }
}
// Works, but you'll spend more time here than a database lock at 5pm.

🧠 How Devs Usually Mess This Up

First instinct: “Hey, this is basically an inversion count, let me copy-paste that code and swap a sign!” Sorry, pal—negative numbers, double-multiplication, and array corruption turn that dream into a carnival of bugs. Others try to bravely tweak merge logic or sort too eagerly, breaking the sorted contract and ending up with arrays uglier than 1980s Java Swing apps.

🔍 What’s Actually Going On

Imagine sorting and merging like you’re at a buffet line—half the people pour soup, half pour cereal. You need to check, for each soup person (nums[i]), how many cereal folks (nums[j]) are less than half their size (well, technically, nums[i] > 2 * nums[j]). Since both sides are sorted, you can use pointers for a synchronized two-person judging panel—swooping through the right half for every left-side guest and tallying their conquests in O(n).

It’s merge sort, but with a counting twist: mid-way through the merge, you secretly log every left > 2*right pairing. That’s your DSA party trick. You work recursively, pulling in counts from left, right, and this pivotal merge step—then let merge sort do what merge sort does best… merge.

🛠️ PseudoCode

• Split the array until you reach single elements (merge sort’s warmup dance).
• During each merge, for every left element, walk a right pointer forwards as long as nums[i] > 2 * nums[j] is satisfied.
  

  // For left i, escalate j rightwards
  while (j <= right && nums[i] > 2L * nums[j]) {
      j++;
  }
  count += (j - (mid + 1));

• Proceed with the boring old merge—keep order, keep your job.
• Add up counts: left, right, and cross-merges, then bubble results up like the world’s least fun champagne tower.

💻 The Code

public class ReversePairs {
    public int reversePairs(int[] nums) {
        if (nums == null || nums.length < 2) return 0;
        return mergeSort(nums, 0, nums.length - 1);
    }
    
    private int mergeSort(int[] nums, int left, int right) {
        if (left >= right) return 0;
        int mid = left + (right - left) / 2;
        int count = mergeSort(nums, left, mid)
            + mergeSort(nums, mid + 1, right);
        int j = mid + 1;
        for (int i = left; i <= mid; i++) {
            while (j <= right && nums[i] > 2L * nums[j]) j++;
            count += (j - (mid + 1));
        }
        // Merge time
        int[] tmp = new int[right - left + 1];
        int i = left, k = 0;
        j = mid + 1;
        while (i <= mid && j <= right)
            tmp[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= right) tmp[k++] = nums[j++];
        System.arraycopy(tmp, 0, nums, left, tmp.length);
        return count;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Java Integer Overflow: Always cast to long before the multiplication, or you’ll be debugging integer wrath for days.
• Don’t overwrite arrays mid-merge—sorted order is sacred; break it and your next count is basically a lottery.
• Brute force is O(n²); optimized is O(n log n). Your interviewer will quietly judge which you use.

🧠 Interviewer Brain-Tattoo

“Knowing when to bring merge sort’s secret weapon is the difference between DSA survival and hackathon meltdown.”