The O(n) Club: 4Sum — When Just One More Loop Feels Like a Crime

The O(n) Club: 4Sum — When Just One More Loop Feels Like a Crime

⚡ TL;DR

Find four numbers in your array that make a target sum. Yes, you could hammer out four for-loops—if you enjoy timeouts and fan mail from your CPU. Or be smart: sort the thing, double-loop, then two-pointer like a pro, skipping repeats so your output isn’t a dumpster fire.

// Brute force (please don't):
for (int i = 0; i < n; i++)
  for (int j = i+1; j < n; j++)
    for (int k = j+1; k < n; k++)
      for (int l = k+1; l < n; l++)
        if (nums[i]+nums[j]+nums[k]+nums[l] == target)
          addQuadruplet();
// TLE: The Legacy Experience
  

🧠 How Devs Usually Mess This Up

Most devs get stars in their eyes, nest four shiny for-loops, and hit submit. Reality check: brute force works if your input is your cat’s age, but real test cases turn your solution slower than Windows Update. Don’t even talk about deduplication—half of you skip it and drown in quadruplets that only differ in order. And if you’re reusing indices? Might as well submit your lunch order to LeetCode too.

🔍 What’s Actually Going On

4Sum is 3Sum’s bigger, meaner sibling—four unique indices, same number only once, output everything exactly once (interviewer’s OCD demands it). It’s not about brute force, it’s about choreography: sort the array, do two outer loops to fix the first two numbers, then let your left and right pointers dance toward each other, hunting for the perfect sum. All while skipping repeat numbers along the way, because another [1,0,-1,0] doesn’t make anyone happy.

🛠️ PseudoCode

• Sort nums so duplicate skipping is actually possible and your pointers make sense.
• Loop i from 0 to n-4:
  

  if (i > 0 && nums[i] == nums[i-1]) continue; // no repeats

• Loop j from i+1 to n-3:
  

  if (j > i+1 && nums[j] == nums[j-1]) continue; // no repeats

• Set left = j+1, right = n-1; while (left < right):
• If sum == target: add quadruplet, skip over repeated left/right values
• If sum < target: left++
• If sum > target: right–
• Repeat until you’ve found every unique group of four

💻 The Code

import java.util.*;
 public class FourSum {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length < 4) return result;
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1, right = n - 1;
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++; right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return result;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Duplicates Out of Control: Skip. Those. Duplicates. Or your solution comes out looking like an all-you-can-eat quadruplet buffet.
• Integer Overflow: Guess what, a couple billion here or there and you’ve got bug soup (long sum please).
• Array Too Short: Less than four numbers? Save everyone grief, just return early.
• Time Sadness: O(n³). Still chunky, but three loops beats four. Sorting keeps the pointers and duplicate-skipping honest.
• Index vs. Value: Never use the same index twice. Unique indices or code jail.

🧠 Interviewer Brain-Tattoo

“Want the job? Win the deduplication dance-off. 4Sum: Where brute force cries and two pointers party.”