25. 3Sum

🔗 LeetCode Problem: 15. 3Sum
📊 Difficulty: Medium
🏷️ Topics: Array, Two Pointers, Sorting

Problem Statement

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints: - 3 <= nums.length <= 3000 - -10^5 <= nums[i] <= 10^5

---

🎨 Visual Understanding

The Problem Visualized

Input: nums = [-1, 0, 1, 2, -1, -4]

Question: Find all unique triplets that sum to 0

Possible triplets:
[-1, 0, 1]   → -1 + 0 + 1 = 0 ✓
[-1, -1, 2]  → -1 + -1 + 2 = 0 ✓
[0, 1, -1]   → Same as [-1, 0, 1] (duplicate)
[2, -1, -1]  → Same as [-1, -1, 2] (duplicate)

Answer: [[-1, 0, 1], [-1, -1, 2]]

Key Observation - Convert 3Sum to 2Sum

For each number, find two other numbers that sum to its negative:

Array: [-4, -1, -1, 0, 1, 2]  (sorted)

Fix -4: Find two numbers that sum to +4
  → Check remaining array: [-1, -1, 0, 1, 2]
  → No pair sums to 4

Fix -1: Find two numbers that sum to +1
  → Check remaining array: [-1, 0, 1, 2]
  → Found: -1 + 2 = 1 ✓  Triplet: [-1, -1, 2]
  → Found: 0 + 1 = 1 ✓   Triplet: [-1, 0, 1]

Fix 0: Find two numbers that sum to 0
  → Check remaining array: [1, 2]
  → No pair sums to 0

This is essentially: 3Sum = Fix ONE + Find TWO (2Sum problem)

Why Sorting Helps

Original: [-1, 0, 1, 2, -1, -4]
Sorted:   [-4, -1, -1, 0, 1, 2]

Benefits:
1. Easy to skip duplicates
2. Can use two pointers technique
3. Can optimize (if nums[i] > 0, break)
4. Negatives first, positives last

---

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Core Logic:

Try all possible combinations of three numbers:
1. Use three nested loops
2. Check if sum equals 0
3. Store triplets in set to avoid duplicates
4. Return unique triplets

Why This Works: - Checks every possible triplet - Set automatically handles duplicates - Guaranteed to find all solutions

Why This Fails Requirements: - Time complexity O(n³) - Too slow for larger arrays - Set operations add overhead - Not optimal for interviews

Implementation

public List<List<Integer>> threeSum(int[] nums) {
    Set<List<Integer>> result = new HashSet<>();
    int n = nums.length;

    // Try all possible triplets
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    List<Integer> triplet = Arrays.asList(nums[i], nums[j], nums[k]);
                    Collections.sort(triplet);
                    result.add(triplet);
                }
            }
        }
    }

    return new ArrayList<>(result);
}

⏰ Time: O(n³) - three nested loops
💾 Space: O(n) - for storing results and set

---

✅ Approach 2: Sort + Two Pointers (Optimal)

The Breakthrough Insight 💡

Core Logic:

Convert 3Sum to 2Sum problem:

1. SORT the array first
2. FIX one number (outer loop)
3. Use TWO POINTERS to find two other numbers
4. SKIP duplicates at all three levels

Key insight: For fixed number nums[i], 
             find two numbers that sum to -nums[i]

Why Sorting is Critical:

Sorted array enables:
1. Two pointers technique
2. Easy duplicate skipping
3. Early termination optimization
4. O(n) search for each fixed number

Visual Explanation:

nums = [-4, -1, -1, 0, 1, 2]  (sorted)

i=0: Fix -4, target = +4
     [-4, -1, -1, 0, 1, 2]
       i   L           R

     Use two pointers on remaining array
     Find pairs that sum to 4

i=1: Fix -1, target = +1
     [-4, -1, -1, 0, 1, 2]
           i   L       R

     -1 + 2 = 1 ✓  Found: [-1, -1, 2]
     Move both pointers

     0 + 1 = 1 ✓   Found: [-1, 0, 1]

Strategy: Fix i, use two pointers (left, right) to find pairs

Three Levels of Duplicate Skipping:

Level 1: Skip duplicate i values
         if (i > 0 && nums[i] == nums[i-1]) continue;

Level 2: Skip duplicate left values (after finding triplet)
         while (left < right && nums[left] == nums[left+1]) left++;

Level 3: Skip duplicate right values (after finding triplet)
         while (left < right && nums[right] == nums[right-1]) right--;

Implementation

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    int n = nums.length;

    // Edge case: need at least 3 numbers
    if (n < 3) return result;

    // Step 1: Sort the array
    Arrays.sort(nums);

    // Step 2: Fix first number, find other two with two pointers
    for (int i = 0; i < n - 2; i++) {
        // Skip duplicates for first number
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        // Optimization: if smallest number > 0, no triplet possible
        if (nums[i] > 0) {
            break;
        }

        // Two pointers for remaining two numbers
        int left = i + 1;
        int right = n - 1;
        int target = -nums[i];  // We need two numbers that sum to -nums[i]

        while (left < right) {
            int sum = nums[left] + nums[right];

            if (sum == target) {
                // Found a triplet!
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                // Skip duplicates for left pointer
                while (left < right && nums[left] == nums[left + 1]) {
                    left++;
                }
                // Skip duplicates for right pointer
                while (left < right && nums[right] == nums[right - 1]) {
                    right--;
                }

                // Move both pointers
                left++;
                right--;

            } else if (sum < target) {
                // Sum too small, need larger number
                left++;
            } else {
                // Sum too large, need smaller number
                right--;
            }
        }
    }

    return result;
}

⏰ Time: O(n²) - O(n log n) for sorting + O(n²) for two nested loops
💾 Space: O(1) - excluding result storage (or O(log n) for sorting)

---

🔍 Step-by-Step Execution

Example: nums = [-1, 0, 1, 2, -1, -4]

Step 0: Sort the array
═══════════════════════════════════════════════════════════════════
Original: [-1, 0, 1, 2, -1, -4]
Sorted:   [-4, -1, -1, 0, 1, 2]


Iteration i=0: nums[i] = -4
═══════════════════════════════════════════════════════════════════
Fixed number: -4
Target for 2Sum: -(-4) = 4
Remaining array: [-1, -1, 0, 1, 2]

left = 1, right = 5

Loop iteration 1:
  sum = nums[1] + nums[5] = -1 + 2 = 1
  1 < 4 → sum too small → left++

Loop iteration 2:
  left = 2, right = 5
  sum = nums[2] + nums[5] = -1 + 2 = 1
  1 < 4 → sum too small → left++

Loop iteration 3:
  left = 3, right = 5
  sum = nums[3] + nums[5] = 0 + 2 = 2
  2 < 4 → sum too small → left++

Loop iteration 4:
  left = 4, right = 5
  sum = nums[4] + nums[5] = 1 + 2 = 3
  3 < 4 → sum too small → left++

Loop iteration 5:
  left = 5, right = 5
  left >= right → STOP

No triplet found with -4


Iteration i=1: nums[i] = -1
═══════════════════════════════════════════════════════════════════
Fixed number: -1
Target for 2Sum: -(-1) = 1
Remaining array: [-1, 0, 1, 2]

left = 2, right = 5

Loop iteration 1:
  sum = nums[2] + nums[5] = -1 + 2 = 1
  1 == 1 → FOUND TRIPLET!

  Triplet: [-1, -1, 2]
  Add to result: [[-1, -1, 2]]

  Skip duplicates for left:
    nums[2] = -1, nums[3] = 0 (different) → no skip
  Skip duplicates for right:
    nums[5] = 2, nums[4] = 1 (different) → no skip

  Move both: left = 3, right = 4

Loop iteration 2:
  left = 3, right = 4
  sum = nums[3] + nums[4] = 0 + 1 = 1
  1 == 1 → FOUND TRIPLET!

  Triplet: [-1, 0, 1]
  Add to result: [[-1, -1, 2], [-1, 0, 1]]

  Skip duplicates...
  Move both: left = 4, right = 3

Loop iteration 3:
  left = 4, right = 3
  left >= right → STOP


Iteration i=2: nums[i] = -1
═══════════════════════════════════════════════════════════════════
Skip! nums[2] == nums[1] (both are -1)
This prevents duplicate triplets


Iteration i=3: nums[i] = 0
═══════════════════════════════════════════════════════════════════
Fixed number: 0
Target for 2Sum: 0
Remaining array: [1, 2]

left = 4, right = 5

Loop iteration 1:
  sum = nums[4] + nums[5] = 1 + 2 = 3
  3 > 0 → sum too large → right--

Loop iteration 2:
  left = 4, right = 4
  left >= right → STOP

No triplet found with 0


Iteration i=4: nums[i] = 1
═══════════════════════════════════════════════════════════════════
Optimization: nums[4] = 1 > 0 → BREAK
(No triplets possible with all positive numbers)


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: [[-1, -1, 2], [-1, 0, 1]]
═══════════════════════════════════════════════════════════════════

Another Example: nums = [0, 0, 0]

Step 0: Sort
nums = [0, 0, 0]  (already sorted)

Iteration i=0: nums[0] = 0
═══════════════════════════════════════════════════════════════════
Fixed: 0, Target: 0
left = 1, right = 2

sum = 0 + 0 = 0 ✓
Triplet: [0, 0, 0]
Add to result: [[0, 0, 0]]

Skip duplicates:
nums[1] = 0, nums[2] = 0 (same) → left++
left = 2, right = 1 → STOP

Iteration i=1: Skip (nums[1] == nums[0])
Iteration i=2: Out of bounds

Result: [[0, 0, 0]]

---

🔍 Edge Cases

Case 1: Empty or small array
Input: nums = []
Output: []

Input: nums = [0]
Output: []

Input: nums = [0, 0]
Output: []

Case 2: All zeros
Input: nums = [0, 0, 0, 0]
Output: [[0, 0, 0]]
Explanation: Only one unique triplet

Case 3: All positive numbers
Input: nums = [1, 2, 3, 4]
Output: []
Explanation: No way to sum to 0

Case 4: All negative numbers
Input: nums = [-5, -4, -3, -2]
Output: []
Explanation: No way to sum to 0

Case 5: No valid triplet
Input: nums = [1, 2, -2, -1]
Output: []

Case 6: Many duplicates
Input: nums = [-1, -1, -1, 0, 1, 1, 1]
Output: [[-1, 0, 1]]
Explanation: Multiple -1s and 1s, but only one unique triplet

Case 7: Single triplet
Input: nums = [-1, 0, 1]
Output: [[-1, 0, 1]]

Case 8: Two different triplets
Input: nums = [-2, 0, 1, 1, 2]
Output: [[-2, 0, 2], [-2, 1, 1]]

---

Common Mistakes

Mistake 1: Not sorting the array first
❌ Wrong: 
    public List<List<Integer>> threeSum(int[] nums) {
        // Missing: Arrays.sort(nums);
        ...
    }
✓ Right: 
    Arrays.sort(nums);
Reason: Need sorted array for two pointers technique

Mistake 2: Not skipping duplicates for i
❌ Wrong: 
    for (int i = 0; i < n - 2; i++) {
        // Missing duplicate check
        int left = i + 1;
        ...
    }
✓ Right: 
    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        ...
    }
Reason: Will create duplicate triplets

Mistake 3: Not skipping duplicates after finding triplet
❌ Wrong: 
    if (sum == target) {
        result.add(...);
        left++;
        right--;
        // Missing: skip duplicates
    }
✓ Right: 
    if (sum == target) {
        result.add(...);
        while (left < right && nums[left] == nums[left + 1]) left++;
        while (left < right && nums[right] == nums[right - 1]) right--;
        left++;
        right--;
    }
Reason: Will create duplicate triplets

Mistake 4: Using HashSet to avoid duplicates
❌ Wrong: 
    Set<List<Integer>> result = new HashSet<>();
    // ... add triplets to set
    return new ArrayList<>(result);
✓ Right: 
    List<List<Integer>> result = new ArrayList<>();
    // Skip duplicates properly at all levels
Reason: Inefficient, wastes memory when sorting works

Mistake 5: Wrong loop boundaries
❌ Wrong: 
    for (int i = 0; i < n; i++) {
        int left = i + 1;
        int right = n - 1;
    }
✓ Right: 
    for (int i = 0; i < n - 2; i++) {
        int left = i + 1;
        int right = n - 1;
    }
Reason: Need room for at least 3 elements

Mistake 6: Not handling target correctly
❌ Wrong: 
    int target = nums[i];  // Wrong!
    if (nums[left] + nums[right] == target) {...}
✓ Right: 
    int target = -nums[i];
    if (nums[left] + nums[right] == target) {...}
Reason: Need two numbers that sum to -nums[i] to make total 0

Mistake 7: Forgetting early termination optimization
❌ Wrong: 
    for (int i = 0; i < n - 2; i++) {
        // No optimization
        ...
    }
✓ Right: 
    for (int i = 0; i < n - 2; i++) {
        if (nums[i] > 0) break;  // Optimization
        ...
    }
Reason: If smallest number > 0, no valid triplets possible

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(n³)
  Space: O(n)
  Use: Only for understanding, not for interviews

Approach 2: Sort + Two Pointers (RECOMMENDED)
  Time: O(n²)
  Space: O(1) excluding output
  Use: Optimal solution, best for interviews

🔑 The Core Insight

3Sum Problem = Fix ONE number + Find TWO others (2Sum problem)

Key Strategy:
1. SORT the array first
2. FIX one number (outer loop i)
3. Find two numbers that sum to -nums[i] using TWO POINTERS
4. SKIP duplicates at THREE levels

Formula for each i:
nums[i] + nums[left] + nums[right] = 0
→ Find: nums[left] + nums[right] = -nums[i]

Three Levels of Duplicate Skipping:
Level 1: Skip duplicate i values
Level 2: Skip duplicate left values after finding
Level 3: Skip duplicate right values after finding

🎯 Pattern Recognition

Problem Type: Finding Combinations with Target Sum
Core Pattern: Sort + Two Pointers

When to Apply:
✓ Need to find pairs/triplets with specific sum
✓ Array can be sorted
✓ Need to avoid duplicates
✓ Looking for O(n²) or better solution

Key Techniques:
→ Sort array first
→ Fix one element, use two pointers for rest
→ Skip duplicates at all levels
→ Move pointers based on sum comparison

Related Problems:
- Two Sum (LC 1) - Foundation
- Two Sum II (LC 167) - Sorted array
- 3Sum Closest (LC 16) - Similar approach
- 4Sum (LC 18) - Extension
- 3Sum Smaller (LC 259) - Count variant

🧠 Interview Strategy

Step 1: "Need to find triplets that sum to zero"
Step 2: "Convert to 2Sum by fixing one number"
Step 3: "Sort array, use two pointers"
Step 4: "Skip duplicates at three levels"
Step 5: "Optimize: break if nums[i] > 0"

Key Points to Mention:
- O(n²) time complexity (O(n log n) sort + O(n²) search)
- O(1) space (excluding output)
- Handles duplicates efficiently
- No need for HashSet with proper duplicate skipping

---

📝 Quick Revision Notes

🎯 Core Concept:

Convert 3Sum to 2Sum: fix one number, find two others using two pointers. Must sort first and skip duplicates at three levels.

⚡ Quick Implementation:

public List<List<Integer>> threeSum(int[] a) {
    Set<List<Integer>> res = new HashSet<>();
    int len = a.length;
    // // Approach 1 - brute force
    // for(int i = 0; i < len; i++) {
    //     for(int j = i + 1; j < len; j++) {
    //         for(int k = j + 1; k < len; k++) {
    //             // indices should not be equal and sum is 0
    //             if(i != j && j != k && k != i && (a[i] + a[j] + a[k] == 0)) {
    //                 // Take indices as list and sort it 
    //                 // Add it to set to avoid duplicate results
    //                 List<Integer> temp = Arrays.asList(a[i], a[j], a[k]);
    //                 Collections.sort(temp);
    //                 res.add(temp);
    //             }
    //         }
    //     }
    // }

    // Approach 2 - using sorting and 2 pointers
    // Apply sorting so that we can use two pointers to move in either direction
    // This reduces to a 2-sum problem and will be used same for both 4sum and similar problems
    Arrays.sort(a);
    // keep one index constant at a time. Max it should go len - 2 as there 
    // are 3 pointers and all should not be at the same index.
    for(int i = 0; i < len - 2; i++) {
        // skip duplicates at place 1
        if(i > 0 && a[i] == a[i-1]) {
            continue;
        }
        // and move two pointers in the rest of the space
        int left = i + 1;
        int right = len - 1;
        int target = -a[i]; // deduces to 2-sum problem

        while (left < len && right >= 0 && left < right) {
            // Key insight: For fixed number a[i], find two numbers that sum to target
            int sum = a[left] + a[right];
            if(sum == target) {
                res.add(Arrays.asList(a[i], a[left], a[right]));
                // skip duplicates at place 2 (left pointer)
                while (left < right && a[left] == a[left + 1]) {
                    left++;
                }
                // skip duplicates at place 3 (right pointer)
                while (right > left && a[right] == a[right - 1]) {
                    right--;
                }
                // post skipping duplicates, move both pointers
                // Actually this is the main condition to move further. But, to skip
                // duplicates, above 2 loops are needed as in outer loop.
                left++;
                right--;
            } else if(sum < target) { // check Step-by-Step Execution
                // move left as we need to increase the sum and array is sorted
                left++;
            } else {
                // move right as we need to decrease the sum and array is sorted
                right--;
            }
        }
    }

    return new ArrayList<>(res);
}

🔑 Key Insights:

• Convert to 2Sum: Fix nums[i], find two numbers that sum to -nums[i]
• Sort first: Enables two pointers and duplicate skipping
• Three levels of duplicate skipping:
• Level 1: if (i > 0 && nums[i] == nums[i-1]) continue;
• Level 2: while (left < right && nums[left] == nums[left+1]) left++;
• Level 3: while (left < right && nums[right] == nums[right-1]) right--;
• Optimization: if (nums[i] > 0) break; (no triplets with all positive)
• Pointer movement: sum < target → left++, sum > target → right--
• Time: O(n²), Space: O(1) excluding output
• No HashSet needed: Proper duplicate skipping is sufficient
• Loop boundary: i < n - 2 (need room for 3 elements)

🎪 Memory Aid:

"SORT first, FIX one, FIND two, SKIP thrice!"
Think: "Fix ONE, use TWO pointers, avoid DUPLICATEs"

---

Related Patterns

• Two Sum (LC 1)
• Two Sum II - Input Array Is Sorted (LC 167)
• 3Sum Closest (LC 16)
• 4Sum (LC 18)
• 3Sum Smaller (LC 259)

---

Happy practicing! 🎯