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):

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