4Sum

Q: What is the time complexity of 4Sum?

O(n³). The two loops pick about n²/2 pairs (i, j) , and each gets one two-pointer sweep of at most n steps; the O(n log n) sort is small next to that.

Q: How do you generalize 4Sum to kSum?

Write kSum(nums, target, k) on a sorted list. For k = 2 it runs the two-pointer sweep. For a larger k it loops over the first value, skips repeats, and calls itself with k-1 and target - nums[i] on the values to the right. Each level adds a factor of n, so kSum costs O(n^(k-1)).

Q: Can 4Sum be solved in O(n²)?

You can group the n²/2 pair sums in a hash map and match each pair with pairs summing to target minus its own. That is fast when few pairs share a sum, but one sum can hold O(n²) pairs, so the worst case is no better than O(n³).

MediumTwo pointers Sorting

+10

You get a list of integers nums and an integer target. Return every quadruplet [a, b, c, d] whose four values sit at four different positions of nums and add up to target. Write each quadruplet with its values in non-decreasing order. If the same four values can be picked from different positions, the quadruplet still appears once. Sort the answer by first value, then second, then third. When no quadruplet works, return an empty list.

Function

fourSum(nums: integer-array, target: integer) → integer-2d-array

numsinteger-array: the numbers to pick from, at least one
targetinteger: the sum each quadruplet must reach
Returnsinteger-2d-array: the distinct quadruplets with sum target, each one sorted, the list sorted too; an empty list if there are none

Constraints

1 ≤ nums.length ≤ 200
-10⁸ ≤ nums[i] ≤ 10⁸
-10⁹ ≤ target ≤ 10⁹
The sum of any four values lies between -4 × 10⁸ and 4 × 10⁸, so it fits in a 32-bit integer.
Quadruplets that hold the same four values count as one.

Examples

Input: nums = [3, -1, 0, 2, -2, 1, -3]target = 1
Output: [[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]
Explanation: Each of the four quadruplets adds up to 1, for example -3 + (-1) + 2 + 3. The two that start with -3 come first, ordered by their second value: -1 before 0.

Input: nums = [4, 4, 4, 4, 4, 4]target = 16
Output: [[4, 4, 4, 4]]
Explanation: All 15 choices of four positions out of six give four 4s adding up to 16, so [4, 4, 4, 4] appears once.

Input: nums = [1, 5, 2, 9]target = 3
Output: []
Explanation: The only choice is all four numbers, and 1 + 5 + 2 + 9 = 17, not 3, so the answer is an empty list.

Follow-up

Count the sets of four positions whose values add up to target, rather than the distinct quadruplets. The second example has 15. Can you do it in O(n²)?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Checking every set of four positions costs O(n⁴), and repeated values build the same quadruplet many times. Apply the 3Sum reduction one level deeper: sort, fix the first two values with two loops, find the last pair with two pointers, and skip repeated values at every level.

Try every set of four

Correct, but does not finish on the largest tests

Intuition

Sort first, so positions i < j < k < l hold values in non-decreasing order and each quadruplet comes out written the right way. Four nested loops reach every choice of four positions. To avoid repeats, a loop moves on when its next position holds the value it tried a step earlier. On six 4s each loop tries only its first position, so [4, 4, 4, 4] comes out once instead of 15 times.

For 200 numbers there are 64,684,950 sets of four, and the count grows about 16 times when n doubles.

Algorithm

Sort nums.
Nest four loops over i < j < k < l, each starting one past the loop around it.
In every loop, pass over a position that is not the loop's first and holds the same value as the position before it.
Record [nums[i], nums[j], nums[k], nums[l]] when the four add up to target. The loops produce them in sorted order.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # same second value as the round before
            for k in range(j + 1, n - 1):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                for l in range(k + 1, n):
                    if l > k + 1 and nums[l] == nums[l - 1]:
                        continue  # same fourth value as the round before
                    if nums[i] + nums[j] + nums[k] + nums[l] == target:
                        quads.append([nums[i], nums[j], nums[k], nums[l]])
    return quads

Sort, two loops, two pointers

Intuition

Fix nums[i] and nums[j], and what is left is a pair question: find two values right of j that add up to target - nums[i] - nums[j]. On a sorted list one sweep answers it. Start lo at j+1 and hi at the last index. A sum below target moves lo right; a sum above it moves hi left.

Each move drops a value that is in no answer. If the sum is too small, even the largest value left, nums[hi], is not enough for nums[lo], so nums[lo] can go. A sum that is too large drops nums[hi] for the mirror reason. One pair (i, j) needs at most n moves, so the n²/2 pairs cost O(n³).

On the first example, with i on -3 and j on -1, lo moves from 0 past 1 to 2, where -3 + (-1) + 2 + 3 = 1.

Algorithm

Sort nums.
For each i, skip it when i > 0 and nums[i] equals nums[i-1].
For each j after i, skip it when j > i+1 and nums[j] equals nums[j-1].
Set lo = j+1 and hi = n-1. While lo < hi, compare the four values' sum with target: below it move lo right, above it move hi left.
On a match, record the quadruplet, move both pointers, then advance lo while it holds the value it used.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # this second value was already handled
            lo, hi = j + 1, n - 1
            while lo < hi:
                total = nums[i] + nums[j] + nums[lo] + nums[hi]
                if total < target:
                    lo += 1
                elif total > target:
                    hi -= 1
                else:
                    quads.append([nums[i], nums[j], nums[lo], nums[hi]])
                    lo += 1
                    hi -= 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1
    return quads

Pitfalls and edge cases

Skipping j whenever nums[j] equals nums[j-1]. At j = i+1 that compares with the value i uses, so [2, 2, 2, 2, 2] with target 8 loses [2, 2, 2, 2].
Copying 3Sum's early exit nums[i] > target. With [-5, -4, -3, -2, -1] and target -10 the loop stops at -5 and misses [-4, -3, -2, -1].
Lists shorter than four. With one or two numbers n-3 is negative: 0..<(n - 3) traps in Swift, and n - 3 on a Rust usize underflows. Return an empty list first.
Collecting quadruplets in a hash set and returning them unsorted.

Frequently asked questions3

What is the time complexity of 4Sum?

O(n³). The two loops pick about n²/2 pairs (i, j), and each gets one two-pointer sweep of at most n steps; the O(n log n) sort is small next to that.

How do you generalize 4Sum to kSum?

Write kSum(nums, target, k) on a sorted list. For k = 2 it runs the two-pointer sweep. For a larger k it loops over the first value, skips repeats, and calls itself with k-1 and target - nums[i] on the values to the right. Each level adds a factor of n, so kSum costs O(n^(k-1)).

Can 4Sum be solved in O(n²)?

You can group the n²/2 pair sums in a hash map and match each pair with pairs summing to target minus its own. That is fast when few pairs share a sum, but one sum can hold O(n²) pairs, so the worst case is no better than O(n³).

def fourSum(nums, target):
    # Write code here

Test #1

Test #2

Test #3

Arguments

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

Expected Output

[[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]