4Sum: Extending Two Pointers to Four Elements

LeetCode 4Sum (problem 18) asks you to find all unique quadruplets that sum to a given target. If you have solved 3Sum, the structure will look familiar. You are adding one more outer loop and one more layer of duplicate skipping. The core engine is still two pointers on a sorted array.

The problem

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

• a, b, c, and d are distinct indices
• nums[a] + nums[b] + nums[c] + nums[d] == target

The result must not contain duplicate quadruplets.

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

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

Visualizing the approach

After sorting the array, you fix two elements with nested loops (indices i and j), then use two converging pointers (lo and hi) to search for the remaining pair. The blue pointer is i, purple is j, orange is lo, and green is hi.

This is the same pattern as 3Sum, but with one additional fixed pointer. The sorted order makes both the two-pointer scan and the duplicate skipping possible.

The approach

1. Sort the array. This costs O(n log n) and enables both the two-pointer technique and adjacent-element duplicate skipping.
2. Outer loop (i). Iterate i from 0 to n - 4. Skip duplicates: if nums[i] == nums[i - 1], continue.
3. Second loop (j). Iterate j from i + 1 to n - 3. Skip duplicates: if nums[j] == nums[j - 1] and j > i + 1, continue.
4. Two-pointer scan. Set lo = j + 1 and hi = n - 1. Compute the four-element sum. If it is less than the target, move lo right. If greater, move hi left. If equal, record the quadruplet and skip duplicates for both lo and hi before moving them inward.

The key insight: each level of nesting reduces the problem by one element. 4Sum becomes 3Sum with a fixed first element. 3Sum becomes 2Sum with a fixed second element. 2Sum on a sorted array is solved with two pointers in O(n).

Visual walkthrough

Let's trace through the algorithm on the sorted array [-2, -1, 0, 0, 1, 2] with target = 0. Blue is i, purple is j, orange is lo, green is hi.

Notice how the algorithm finds all three quadruplets by systematically fixing i and j, then scanning with two pointers. When j advances, it skips duplicate values just like i does. After finding a match, lo and hi both skip past duplicates before moving inward.

The code

Here is the complete Python solution:

def four_sum(nums, target):
    nums.sort()
    result = []
    n = len(nums)

    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

            lo, hi = j + 1, n - 1
            t = target - nums[i] - nums[j]

            while lo < hi:
                s = nums[lo] + nums[hi]
                if s < t:
                    lo += 1
                elif s > t:
                    hi -= 1
                else:
                    result.append([nums[i], nums[j], nums[lo], nums[hi]])
                    while lo < hi and nums[lo] == nums[lo + 1]:
                        lo += 1
                    while lo < hi and nums[hi] == nums[hi - 1]:
                        hi -= 1
                    lo += 1
                    hi -= 1

    return result

A few details worth noting:

• t = target - nums[i] - nums[j] reduces the four-element problem to a two-element search. Instead of checking if four values sum to target, you check if two values sum to t.
• The duplicate skip for j uses j > i + 1 as the guard, not j > 0. You only skip when j has advanced past its starting position relative to i.
• The inner duplicate-skip loops after a match work identically to 3Sum. Skip forward on lo, skip backward on hi, then move both one more step.

Complexity analysis

Time: O(n^3). Sorting is O(n log n). The two outer loops contribute O(n^2), and for each pair the two-pointer scan is O(n). Total: O(n log n) + O(n^3) = O(n^3).

Space: O(1) extra (ignoring the output list and the space used by the sorting algorithm). The two-pointer scan uses only a few variables. No hash maps or sets are needed.

Building blocks

The 4Sum solution is assembled from a small set of reusable building blocks:

k-Sum generalization

The pattern here generalizes to any k-Sum problem. For k elements summing to a target on a sorted array:

• If k == 2, use two pointers.
• If k > 2, fix one element and recursively solve (k-1)-Sum on the remaining subarray.

2Sum uses two pointers. 3Sum fixes one element and runs 2Sum. 4Sum fixes one element and runs 3Sum. You could write a recursive k_sum function that handles any value of k. The time complexity is O(n^(k-1)).

Duplicate skipping on sorted arrays

Every level of the nested loops needs its own duplicate skip. The pattern is always the same: after processing a value, advance the pointer past all identical consecutive values. This works because sorting groups duplicates together, making them adjacent.

The guard condition changes at each level. For i, it is i > 0. For j, it is j > i + 1. The principle is the same: only skip if the pointer has moved past its starting position for that loop level.

Edge cases

• No valid quadruplets. If the array has fewer than four elements, or no combination sums to the target, return an empty list. The loop bounds (n - 3 and n - 2) handle short arrays naturally.
• All same numbers. An array like [2, 2, 2, 2, 2] with target = 8 should return [[2, 2, 2, 2]] exactly once. The duplicate skipping at all four levels ensures no repeats.
• Negative target. The target is not restricted to zero. With nums = [1, 0, -1, 0, -2, 2] and target = -1, the valid quadruplets would differ. The algorithm handles negative targets without any modification because it compares sums directly rather than assuming a zero target.
• Integer overflow. In languages like C++ or Java, summing four large integers can overflow. Python handles arbitrary-precision integers natively, so this is not a concern in Python. In other languages, cast to a long before summing.

From understanding to recall

The 4Sum algorithm is not conceptually new if you already know 3Sum. It is one more outer loop and one more duplicate skip. But writing it correctly under pressure requires that all the pieces are automatic. The duplicate guard for j uses j > i + 1, not j > 1. The two-pointer remainder is target - nums[i] - nums[j], not target - nums[i]. These small details are easy to mix up.

The path to reliability: drill the building blocks separately. Practice 2Sum with two pointers until you can write it without thinking. Then 3Sum. By the time you reach 4Sum, the pattern is mechanical. Fix one more element, add one more duplicate skip, and run the same inner engine. You are not memorizing a new algorithm. You are extending a pattern you already own.

Related posts

• 3Sum: Sorting Plus Two Pointers - The direct prerequisite, one fewer nesting level
• Two Sum - The foundation of complement-based pair finding

---

Visual Learner? See how sorting algorithms work with our Quick Sort Visualization -- the first step in the 4Sum solution.