29. 4Sum

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

Problem Statement

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Constraints: - 1 <= nums.length <= 200 - -10^9 <= nums[i] <= 10^9 - -10^9 <= target <= 10^9

---

🎨 Visual Understanding

The Problem Visualized

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

All possible quadruplets that sum to 0:
[-2, -1, 1, 2]  → -2 + -1 + 1 + 2 = 0 ✓
[-2, 0, 0, 2]   → -2 + 0 + 0 + 2 = 0 ✓
[-1, 0, 0, 1]   → -1 + 0 + 0 + 1 = 0 ✓

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

Progression: Two Sum → 3Sum → 4Sum

Two Sum: Find TWO numbers that sum to target
  Strategy: HashMap or Two Pointers
  Time: O(n)

3Sum: Find THREE numbers that sum to target
  Strategy: Fix ONE + Two Pointers for remaining TWO
  Time: O(n²)

4Sum: Find FOUR numbers that sum to target
  Strategy: Fix TWO + Two Pointers for remaining TWO
  Time: O(n³)

Pattern: Fix (n-2) numbers, use Two Pointers for last 2

Key Observation - Convert 4Sum to 3Sum

For each pair of numbers, find two other numbers using Two Pointers:

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

Fix i=0 (-2), j=1 (-1): Find two numbers that sum to -(-2-1) = 3
  → Remaining: [0, 0, 1, 2]
  → Found: 1 + 2 = 3 ✓  Quadruplet: [-2, -1, 1, 2]

Fix i=0 (-2), j=2 (0): Find two numbers that sum to -(-2+0) = 2
  → Remaining: [0, 1, 2]
  → Found: 0 + 2 = 2 ✓  Quadruplet: [-2, 0, 0, 2]

Fix i=1 (-1), j=2 (0): Find two numbers that sum to -(-1+0) = 1
  → Remaining: [0, 1, 2]
  → Found: 0 + 1 = 1 ✓  Quadruplet: [-1, 0, 0, 1]

This is: 4Sum = Fix TWO + Find TWO (2Sum with pointers)

---

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Core Logic:

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

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

Why This Fails Requirements: - Time complexity O(n⁴) - Extremely slow for larger arrays - Set operations add overhead - Not acceptable for interviews

Implementation

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

    // Try all possible quadruplets
    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++) {
                    long sum = (long) nums[i] + nums[j] + nums[k] + nums[l];
                    if (sum == target) {
                        List<Integer> quad = Arrays.asList(nums[i], nums[j], nums[k], nums[l]);
                        Collections.sort(quad);
                        result.add(quad);
                    }
                }
            }
        }
    }

    return new ArrayList<>(result);
}

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

---

✅ Approach 2: Sort + Two Pointers (Optimal)

The Breakthrough Insight 💡

Core Logic:

Extend 3Sum approach by adding one more fixed number:

1. SORT the array first
2. FIX first number (outer loop i)
3. FIX second number (inner loop j)
4. Use TWO POINTERS for remaining two numbers
5. SKIP duplicates at FOUR levels

Key insight: Fix two numbers nums[i] and nums[j],
             then find two numbers that sum to target - nums[i] - nums[j]

Visual Explanation:

nums = [-2, -1, 0, 0, 1, 2], target = 0

i=0 (-2), j=1 (-1): Need sum = 0-(-2)-(-1) = 3
     [-2, -1, 0, 0, 1, 2]
       i   j  L        R

     0 + 2 = 2 < 3 → L++
     0 + 2 = 2 < 3 → L++
     1 + 2 = 3 ✓   Found: [-2, -1, 1, 2]

i=0 (-2), j=2 (0): Need sum = 0-(-2)-0 = 2
     [-2, -1, 0, 0, 1, 2]
       i      j  L     R

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

Strategy: Fix i and j, use two pointers (left, right) to find last two

Four Levels of Duplicate Skipping:

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

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

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

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

Implementation

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

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

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

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

        for (int j = i + 1; j < n - 2; j++) {
            // Skip duplicates for second number
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }

            // Two pointers for remaining two numbers
            int left = j + 1;
            int right = n - 1;

            while (left < right) {
                // Use long to avoid integer overflow
                long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];

                if (sum == target) {
                    // Found a quadruplet!
                    result.add(Arrays.asList(nums[i], nums[j], 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 three nested loops
💾 Space: O(1) - excluding result storage (or O(log n) for sorting)

---

🔍 Step-by-Step Execution

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

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


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

left = 2, right = 5

Loop iteration 1:
  sum = -2 + (-1) + 0 + 2 = -1
  -1 < 0 → sum too small → left++

Loop iteration 2:
  left = 3, right = 5
  sum = -2 + (-1) + 0 + 2 = -1
  -1 < 0 → sum too small → left++

Loop iteration 3:
  left = 4, right = 5
  sum = -2 + (-1) + 1 + 2 = 0
  0 == 0 → FOUND QUADRUPLET!

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

  Skip duplicates for left and right
  Move both: left = 5, right = 4
  left >= right → STOP


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

left = 3, right = 5

Loop iteration 1:
  sum = -2 + 0 + 0 + 2 = 0
  0 == 0 → FOUND QUADRUPLET!

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

  Skip duplicates for left and right
  Move both: left = 4, right = 4
  left >= right → STOP


Iteration i=0, j=3: nums[i]=-2, nums[j]=0
═══════════════════════════════════════════════════════════════════
Skip! nums[3] == nums[2] (both are 0)


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

left = 5, right = 5
left >= right → STOP (need at least 2 elements)


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

left = 3, right = 5

Loop iteration 1:
  sum = -1 + 0 + 0 + 2 = 1
  1 > 0 → sum too large → right--

Loop iteration 2:
  left = 3, right = 4
  sum = -1 + 0 + 0 + 1 = 0
  0 == 0 → FOUND QUADRUPLET!

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

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


Iteration i=1, j=3: Skip (duplicate j)
Iteration i=1, j=4: Only 1 element left
Iteration i=2: Similar process, no new quadruplets
Iteration i=3: Out of bounds


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

Another Example: nums = [2, 2, 2, 2, 2], target = 8

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

Iteration i=0, j=1: nums[0]=2, nums[1]=2
═══════════════════════════════════════════════════════════════════
Fixed: 2, 2
Target for 2Sum: 8 - 2 - 2 = 4
left = 2, right = 4

sum = 2 + 2 + 2 + 2 = 8 ✓
Quadruplet: [2, 2, 2, 2]
Add to result: [[2, 2, 2, 2]]

Skip duplicates:
All remaining elements are 2
Move both pointers

Iteration i=0, j=2: Skip (nums[2] == nums[1])
Iteration i=0, j=3: Skip (nums[3] == nums[1])
Iteration i=1: Skip (nums[1] == nums[0])
...

Result: [[2, 2, 2, 2]]

---

🔍 Edge Cases

Case 1: Minimum array size
Input: nums = [1, 2, 3, 4], target = 10
Output: [[1, 2, 3, 4]]
Explanation: 1 + 2 + 3 + 4 = 10

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

Case 3: No valid quadruplet
Input: nums = [1, 2, 3, 4], target = 100
Output: []

Case 4: Multiple duplicates
Input: nums = [-3, -1, 0, 2, 4, 5], target = 0
Output: [[-3,-1,0,4]]

Case 5: All negative numbers
Input: nums = [-5, -4, -3, -2], target = -14
Output: [[-5,-4,-3,-2]]

Case 6: Large target
Input: nums = [1000000000, 1000000000, 1000000000, 1000000000], target = 4000000000
Output: [[1000000000, 1000000000, 1000000000, 1000000000]]
Note: Need to use long to avoid overflow!

Case 7: Negative target
Input: nums = [-2, -1, 0, 1, 2], target = -2
Output: [[-2,-1,0,1]]

Case 8: Small array no solution
Input: nums = [0, 0, 0], target = 1
Output: []
Explanation: Only 3 elements, need 4

---

Common Mistakes

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

Mistake 2: Integer overflow
❌ Wrong: 
    int sum = nums[i] + nums[j] + nums[left] + nums[right];
✓ Right: 
    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
Reason: Sum can exceed Integer.MAX_VALUE with large numbers

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

Mistake 4: Wrong duplicate check for j
❌ Wrong: 
    if (j > 0 && nums[j] == nums[j - 1]) continue;
✓ Right: 
    if (j > i + 1 && nums[j] == nums[j - 1]) continue;
Reason: j should skip duplicates relative to i+1, not 0

Mistake 5: Not skipping duplicates after finding quadruplet
❌ 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 quadruplets

Mistake 6: Wrong loop boundaries
❌ Wrong: 
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {...}
    }
✓ Right: 
    for (int i = 0; i < n - 3; i++) {
        for (int j = i + 1; j < n - 2; j++) {...}
    }
Reason: Need room for 4 elements total

Mistake 7: Using HashSet instead of proper duplicate skipping
❌ Wrong: 
    Set<List<Integer>> result = new HashSet<>();
    // ... add quadruplets to set
    return new ArrayList<>(result);
✓ Right: 
    List<List<Integer>> result = new ArrayList<>();
    // Skip duplicates properly at all four levels
Reason: Inefficient, wastes memory when sorting works

Mistake 8: Comparing with wrong target
❌ Wrong: 
    long remaining = target - nums[i];
    // Then compare sum with remaining
✓ Right: 
    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
    if (sum == target) {...}
Reason: Should compare total sum with target directly

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(n⁴)
  Space: O(n)
  Use: Only for understanding, never 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

4Sum Problem = Fix TWO numbers + Find TWO others (2Sum with pointers)

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

Formula for each i, j:
nums[i] + nums[j] + nums[left] + nums[right] = target

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

Important: Use LONG to avoid integer overflow!

🎯 Pattern Recognition

Problem Type: Finding K-Sum Combinations
Core Pattern: Sort + Fix (k-2) + Two Pointers for last 2

General Pattern:
2Sum: Two Pointers → O(n)
3Sum: Fix 1 + Two Pointers → O(n²)
4Sum: Fix 2 + Two Pointers → O(n³)
kSum: Fix (k-2) + Two Pointers → O(n^(k-1))

When to Apply:
✓ Need to find k numbers with specific sum
✓ Array can be sorted
✓ Need to avoid duplicates
✓ Looking for O(n^(k-1)) solution

Key Techniques:
→ Sort array first
→ Fix (k-2) elements with nested loops
→ Use two pointers for last 2 elements
→ Skip duplicates at all k levels
→ Use long for large numbers (overflow prevention)

Related Problems:
- Two Sum (LC 1) - Foundation
- 3Sum (LC 15) - Extension
- 3Sum Closest (LC 16) - Variant
- kSum (generalized)

🧠 Interview Strategy

Step 1: "Need to find quadruplets that sum to target"
Step 2: "Extend 3Sum approach: fix two, use two pointers"
Step 3: "Sort array, skip duplicates at four levels"
Step 4: "Use long to avoid integer overflow"
Step 5: "O(n³) time, O(1) space"

Key Points to Mention:
- Extension of 3Sum pattern
- Fix two numbers, two pointers for rest
- Four levels of duplicate skipping
- Integer overflow prevention with long
- O(n³) time complexity
- No need for HashSet with proper duplicate skipping

---

📝 Quick Revision Notes

🎯 Core Concept:

Extend 3Sum pattern: fix TWO numbers, find two others using two pointers. Must sort first, skip duplicates at four levels, and use long to avoid overflow.

⚡ Quick Implementation:

public List<List<Integer>> fourSum(int[] a, int target) {
    HashSet<List<Integer>> res = new HashSet<>();
    int len = a.length;

    // // Approach 1 - brute force
    // for(int i = 0; i < len - 3; i++) {
    //     for(int j = i + 1; j < len - 2; j++) {
    //         for(int k = j + 1; k < len - 1; k++) {
    //             for(int l = k + 1; l < len; l++) {
    //                 int sum = a[i] + a[j] + a[k] + a[l];

    //                 if(sum == target) {
    //                     List<Integer> list = Arrays.asList(a[i], a[j], a[k], a[l]);
    //                     Collections.sort(list);
    //                     res.add(list);
    //                 }
    //             }
    //         }
    //     }
    // }

    // Approach 2 - sorting and two pointer approach
    Arrays.sort(a);
    for(int i = 0; i < len - 3; i++) {
        for(int j = i + 1; j < len - 2; j++) {
            int left = j + 1;
            int right = len - 1;

            while (left < right) {
                // long needed for some edge test cases. Otherwise int is enough
                long sum = (long) a[i] + a[j] + a[left] + a[right];

                if(sum == target) {
                    res.add(Arrays.asList(a[i], a[j], a[left], a[right]));
                    left++;
                    right--;
                } else if (sum < target) {                        
                    left++; // you need to increase the value. So move left.
                    // skip duplicates
                    while(left < right && a[left] == a[left - 1]) {
                        left++;
                    }
                } else {
                    right--; // you need to decrease the value. So move right.
                    // skip duplicates
                    while(left < right && a[right] == a[right + 1]) {
                        right--;
                    }
                }
            }
        }
    }

    return new ArrayList<>(res);
}

🔑 Key Insights:

• Pattern: Fix TWO → Find TWO with pointers
• Sort first: Enable two pointers and duplicate skipping
• Four levels of duplicate skipping:
• Level 1: if (i > 0 && nums[i] == nums[i-1]) continue;
• Level 2: if (j > i+1 && nums[j] == nums[j-1]) continue;
• Level 3: while (left < right && nums[left] == nums[left+1]) left++;
• Level 4: while (left < right && nums[right] == nums[right-1]) right--;
• Integer overflow: Use long sum = (long) nums[i] + ...
• Pointer movement: sum < target → left++, sum > target → right--
• Time: O(n³), Space: O(1) excluding output
• Loop boundaries: i < n-3, j < n-2 (need room for 4 elements)
• j duplicate check: Compare with j-1 only if j > i+1

🎪 Memory Aid:

"SORT, FIX TWO, FIND TWO, SKIP FOUR times, use LONG!"
Think: "3Sum + one more loop = 4Sum"

---

Related Patterns

• Two Sum (LC 1)
• 3Sum (LC 15)
• 3Sum Closest (LC 16)
• Two Sum II - Input Array Is Sorted (LC 167)

---

Happy practicing! 🎯