The O(n) Club: 3Sum Problem: How to Stop Triple Trouble Before It Starts

The O(n) Club: 3Sum Problem—How to Stop Triple Trouble Before It Starts

⚡ TL;DR

The mission: Find all unique triples in your array that sum to zero (with no repeats). Brute force? Sure, if you want runtime trauma and a new career. Here’s the code you should avoid (unless you like pain):

// Brute force pain factory:
for (int i = 0; i < nums.length; ++i) {
    for (int j = i + 1; j < nums.length; ++j) {
        for (int k = j + 1; k < nums.length; ++k) {
            if (nums[i] + nums[j] + nums[k] == 0) {
                // Prepare for duplicate drama
            }
        }
    }
}

🧠 How Devs Usually Mess This Up

Let’s check out the parade of classic 3Sum fails:

• Drowning in duplicates: Find a triplet, then find it again, and again, and again… Output looks like a party invite list for clones.
• Forget sorting: Jump into two-pointer logic too early and everything falls apart. Sorting isn’t optional—it’s your algorithmic coffee.
• Double-dipping indexes: Accidentally reuse the same index twice. Math says ‘no.’
• Not handling edge cases: Input length < 3, or everything’s zero. If the function can't handle it, the interviewer will handle you (ruthlessly).
• The Three-Loop Flex: Nothing says “I didn’t read the problem” like triple nested loops. Ouch.

🔍 What’s Actually Going On

Imagine you’re at a hackathon and desperately forming trios so your team adds up to a neutral zero: sort the crowd (array), anchor one die-hard coder, and move two pointers inward to assemble “zero drama” squads. The rules?

• Sort first: This is literally page one for a reason.
• Set an anchor: For every unique anchor, sweep the rest with left/right pointers seeking a pair that fits.
• Skip repeats: Once you’ve seen a triplet or a number, skip to the next fresh face. Life is short.
• Bail early: If your anchor is positive (and so is everyone after), nobody’s getting to zero. Go home.

🛠️ PseudoCode

• Sort the array: Arrays.sort(nums);
• For each i from 0 to nums.length - 3:
  • If i > 0 && nums[i] == nums[i-1], continue (anchor dupes = skip).
  • Let left = i+1, right = nums.length-1.
  • While left < right:
    • sum = nums[i] + nums[left] + nums[right]
    • If sum == 0: add triplet, left++ while same value, right-- while same value.
    • If sum < 0: left++
    • If sum > 0: right--

💻 The Code

import java.util.*;
 public class ThreeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length < 3) return result;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], 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 < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• [0,0,0,0] should give you one lonely [0,0,0], not the zero triplet apocalypse.
• Less than three numbers? Return empty. You need three to tango.
• Missed duplicate skips = copy-paste chaos in your output.
• Time: O(n²) after sort. Space: O(sort) for sorting, extra for output. Still way snappier than three nested loops!

🧠 Interviewer Brain-Tattoo

“Real devs sort, anchor, pointer, and skip duplicates. Fake devs write triple loops and wonder where their time went.”