The O(n) Club: Merge Sorted Arrays — Why Going Backwards Is Forwards Thinking

The O(n) Club: Merge Sorted Arrays — Why Going Backwards Is Forwards Thinking

⚡ TL;DR

Trying to merge two already sorted arrays (LeetCode 88) without an accidental data ritual sacrifice? Don’t write over your own numbers! The trick: start at the end and work your way back. That means three pointers, lots of moving backwards, and zero trips to debugging hell.

// Java: merge nums2 into nums1, in-place
int i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
    nums1[k--] = (i >= 0 && nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];
}

🧠 How Devs Usually Mess This Up

So, you bravely charge in, trying to merge from the start like any other two-pointer problem. Oops. You overwrite untouched data in nums1 faster than a caffeinated intern rewriting prod. Result: half your numbers vanish, and you spend lunch inventing new curse words for zero-based indexing. Trust me—if you merge forward, you’re actually merging disaster.

🔍 What’s Actually Going On

Imagine nums1 as a fancy buffet where the last few trays are empty, waiting for new food (a.k.a nums2). If you start serving from the beginning, you dump soup on the salad—total chaos. Instead, grab the biggest dish from the end, put it in the last spot, and repeat. Tada! No destroyed appetizers, just a beautifully merged feast.

🛠️ PseudoCode

• Set up pointers:

  i = m - 1; // End of real nums1 items
  j = n - 1; // End of nums2
  k = m + n - 1; // End of space in nums1

  Think: three chefs filling the buffet, all moonwalking backward.

• While nums2 still has leftovers:

  while (j >= 0) {...}

  Keep mixing until every nums2 value has a spot in nums1, no matter who runs out first.

• Choose the bigger number from nums1[i] or nums2[j]:

  if (i >= 0 && nums1[i] > nums2[j])
      nums1[k--] = nums1[i--];
  else
      nums1[k--] = nums2[j--];

  Yes, it’s a giant sorting battle. Largest number wins, goes to the buffet’s end, and everyone takes a step back.

• No need to copy nums1 leftovers:

  If nums2 is exhausted but nums1’s leftovers remain, congrats—your buffet was already sorted. Do nothing, eat dessert.

💻 The Code

// Java - Merge nums2 into nums1 in-place
public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1;
    int j = n - 1;
    int k = m + n - 1;
    while (j >= 0) {
        if (i >= 0 && nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Zero-length arrays: If nums2 is empty, just smile and walk away. If nums1 has no real items, just overwrite with nums2’s values.
• Pointer party fouls: Off-by-one mistakes happen more often here than in pizza orders. Triple check your index math.
• Copy ALL nums2 items, not just until nums1 runs dry: Otherwise, ghost numbers haunt your output. That’s why we loop until j < 0.
• Complexity: Runs in (m+n) steps, O(1) space. Supermodel efficiency on a factorial diet.

🧠 Interviewer Brain-Tattoo

“Merge from the end, avoid the trend (of overwriting all your actual data).” Tattoo that on your pseudocode.