4Sum — LC 18 Two Loops Plus Two Pointers

Problem Statement#

Find all unique quadruplets [a, b, c, d] in nums that sum to target.

Constraints:

• 1 <= nums.length <= 200
• -10^9 <= nums[i], target <= 10^9

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

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

Why This Problem Matters#

LC 18 is the natural FAANG escalation from 3Sum (LC 15). Amazon, Google, and Meta all use it to test how well you generalize a known pattern. The skeleton — sort, outer loops, inner two pointers — is reusable for any kSum.

Recruiters watch for two things: clean duplicate skipping at every depth, and correct overflow-safe arithmetic. If you nail both, you have shown the interviewer you can scale a familiar idea without bugs.

The Core Insight#

Sort the array. Fix two indices i and j, then use two pointers left and right to find pairs summing to target - nums[i] - nums[j]. Skip duplicates at each of the four positions to keep results unique.

The k-loop generalization (kSum) recurses: kSum(target) calls (k-1)Sum(target - nums[i]). For k = 4 you can hardcode two outer loops which is faster in practice and easier to debug.

Visual Dry Run#

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

Solution (Optimal)#

class Solution:
    def fourSum(self, nums: list[int], target: int) -> list[list[int]]:
        nums.sort()
        n = len(nums)
        result = []
        for i in range(n - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, n - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                left, right = j + 1, n - 1
                while left < right:
                    s = nums[i] + nums[j] + nums[left] + nums[right]
                    if s == target:
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        left += 1
                        right -= 1
                        while left < right and nums[left] == nums[left - 1]:
                            left += 1
                        while left < right and nums[right] == nums[right + 1]:
                            right -= 1
                    elif s < target:
                        left += 1
                    else:
                        right -= 1
        return result

var fourSum = function(nums, target) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const result = [];
    for (let i = 0; i < n - 3; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        for (let j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) continue;
            let left = j + 1, right = n - 1;
            while (left < right) {
                const s = nums[i] + nums[j] + nums[left] + nums[right];
                if (s === target) {
                    result.push([nums[i], nums[j], nums[left], nums[right]]);
                    left++; right--;
                    while (left < right && nums[left] === nums[left - 1]) left++;
                    while (left < right && nums[right] === nums[right + 1]) right--;
                } else if (s < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return result;
};

Time: O(n^3) — two outer loops plus two pointers. Space: O(1) auxiliary, plus output.

Common Mistakes#

• Skipping duplicates only on i and forgetting j, left, right.
• Using i > 0 for j's skip condition; correct is j > i + 1.
• Integer overflow in languages with fixed-width ints — use 64-bit.
• Advancing only one pointer after a hit, leading to duplicate quadruplets.
• Missing the early termination opportunity when nums[i] * 4 > target and all remaining are positive.

Interview Tips#

• Mention sorting cost is O(n log n), dominated by O(n^3) inner work.
• Ask about overflow assumptions; in Java/C++ use long for the sum.
• Sketch kSum recursion as a generalization to show breadth.
• Add early break: if nums[i] * 4 > target and target positive, stop.

Follow-up Questions#

• Generalize to kSum — recursion plus two pointers at depth 2.
• Count of quadruplets only — same loop without record overhead.
• 4Sum II (LC 454) — split into two pair-sum hashmaps for O(n^2).
• Streaming variant — keep sorted multiset.
• Negative target with mostly positive numbers — pruning matters more.

Key Takeaways#

• Sort first; the entire algorithm depends on order.
• Fix two indices and run two pointers for the remaining pair.
• Skip duplicates at every one of the four positions.
• Time is O(n^3); space is O(1) excluding output.
• Use 64-bit arithmetic to avoid overflow on the four-element sum.
• Early break and prune for further speedup on adversarial inputs.
• The pattern extends to kSum via recursion.