The O(n) Club: Find K Pairs with Smallest Sums — Now with 93% Less Suffering

The O(n) Club: Find K Pairs with Smallest Sums — Now with 93% Less Suffering

⚡ TL;DR

Find k pairs with the smallest sums by using a min-heap—skip the RAM meltdown from brute-force pairing and just track the frontier. Fast, neat, and the only way your machine will forgive you.

// Classic brute force (do NOT put this on your resume)
List<int[]> pairs = new ArrayList<>();
for (int u : nums1)
  for (int v : nums2)
    pairs.add(new int[]{u, v});
pairs.sort(Comparator.comparingInt(a -> a[0] + a[1]));
return pairs.subList(0, k);

🧠 How Devs Usually Mess This Up

By trying every possible pair, you create a memory bonfire—congratulations, your heap is now a landfill. Others try shoveling every pair into a heap. Still O(mn) time and O(mn) space. Boom. Recruiter calls lost in a heap, too.

🔍 What’s Actually Going On

Take two sorted arrays. Imagine each as a queue at a coffee shop. Instead of pairing everyone with everyone (“world peace” but for sums), just pair the front-runners: nums1[i] with nums2[0] for i up to k. Always pick the sum-min pair off the heap, then nudge the pointer along nums2 for that i. Voila: no wasted memory, no caffeine jitters.

🛠️ PseudoCode

• Push initial candidates: For each nums1[i] where i < k, pair with nums2[0] and heapify the sum.

  for i = 0 to min(nums1.length, k) - 1:
      heap.offer([nums1[i] + nums2[0], i, 0]);

• Pop smallest sum: Yank smallest off heap, add [nums1[i], nums2[j]] to answer.

  while (result.size() < k && !heap.isEmpty()):
      [sum, i, j] = heap.poll();
      result.add([nums1[i], nums2[j]]);

• Expand just one step: Push [nums1[i], nums2[j+1]] if j + 1 in bounds.

  if (j + 1 < nums2.length):
      heap.offer([nums1[i] + nums2[j + 1], i, j + 1]);

💻 The Code

import java.util.*;
 public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
    List<int[]> result = new ArrayList<>();
    if (nums1.length == 0 || nums2.length == 0 || k == 0) return result;
    PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    for (int i = 0; i < Math.min(nums1.length, k); i++) {
        heap.offer(new int[]{nums1[i] + nums2[0], i, 0});
    }
    while (k-- > 0 && !heap.isEmpty()) {
        int[] curr = heap.poll();
        int i = curr[1], j = curr[2];
        result.add(new int[]{nums1[i], nums2[j]});
        if (j + 1 < nums2.length) {
            heap.offer(new int[]{nums1[i] + nums2[j + 1], i, j + 1});
        }
    }
    return result;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Don’t blindly push both indices; only move right for nums2 so you don’t double-dip.
• If k > total pairs, just give every possible pair—no existential crises, please.
• Arrays too big for O(mn)? Use the heap or you’ll find out what a swap file is.
• Time is O(k log k), space is O(k). Your laptop’s fan, and your interviewer, will smile.

🧠 Interviewer Brain-Tattoo

“Not every problem needs a brute-force bicep. Heapify the frontier, and let the rest of the pairs sleep.” 🍩