LeetCode 18: 4Sum

Problem Statement

LeetCode 18, 4Sum, is a medium-level challenge where you’re given an integer array nums and a target integer target. Your task is to find all unique quadruplets (sets of four numbers) in the array that sum to the target and return them as a list of lists. The array can contain positive and negative integers, and the solution must avoid duplicate quadruplets.

Constraints

1 <= nums.length <= 200: Array length ranges from 1 to 200 elements.
-10^9 <= nums[i] <= 10^9: Each element is between -10^9 and 10^9.
-10^9 <= target <= 10^9: Target value ranges from -10^9 to 10^9.

Example

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Explanation: These quadruplets sum to 0 and are unique.

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
Explanation: Only [2,2,2,2] sums to 8.

Input: nums = [1,2,3], target = 0
Output: []
Explanation: Too few elements for a quadruplet.

Understanding the Problem

Imagine you’re given an array like [1,0,-1,0,-2,2] and a target of 0. You need to find four numbers that add up to 0, such as [-2,-1,1,2]. The challenge is to identify all such unique sets without duplicates, even with repeated numbers in the array. A brute force approach checking every combination would be too slow (O(n⁴)), so we’ll use a Two-Pointer Technique after sorting to make it efficient, building on the logic of 3Sum.

Solution: Two-Pointer Technique

Explanation

Sort the array first, then fix two numbers and use two pointers to find the remaining pair summing to the target minus the fixed pair. This reduces the problem to a series of two-sum searches, optimized with sorting and duplicate skipping.

Here’s a visual for [1,0,-1], target 0 (simplified to 3Sum for clarity, extended to 4Sum):

Sorted: [-1,0,1]
Fix -1, 0, target 1
Left: 1, Right: 1 → Sum = 1 (match)

For 4Sum, we fix two numbers and apply this logic.

Handle Edge Case.

If array length is less than 4, return an empty list.

Sort the Array.

Sorting helps manage duplicates and pointer movement.

Fix Two Numbers.

Use two nested loops to select the first two numbers.

Use Two Pointers.

For each pair, set left and right pointers for the remaining two.
Calculate sum, add quadruplet if it matches target, adjust pointers otherwise.

Skip Duplicates.

Avoid duplicate quadruplets by skipping identical values.

Return Result.

Return the list of unique quadruplets.

Step-by-Step Example

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

We have [1,0,-1,0,-2,2] and want quadruplets summing to 0.

Goal: Find all unique quadruplets that add to 0.
Result for Reference: [[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]].
Start: Sort array to [-2,-1,0,0,1,2]. Result list empty.
Step 1: Check length.

6 ≥ 4, proceed.

Step 2: Fix first at -2 (index 0).

Fix second at -1 (index 1).
Target = 0 - (-2 + -1) = 3.
Left at 2 (0), right at 5 (2).
Sum = 0 + 2 = 2 < 3, left to 3 (0).
Sum = 0 + 2 = 2 < 3, left to 4 (1).
Sum = 1 + 2 = 3, matches target.
Add [-2,-1,1,2], left to 5 (2), right to 4 (1), stop.

Step 3: Fix first at -2, second at 0 (index 2).

Target = 0 - (-2 + 0) = 2.
Left at 3 (0), right at 5 (2).
Sum = 0 + 2 = 2, matches.
Add [-2,0,0,2], left to 4 (1), right to 4, stop.

Step 4: Fix first at -2, second at 0 (index 3).

Duplicate second 0, skip.

Step 5: Fix first at -1 (index 1).

Fix second at 0 (index 2).
Target = 0 - (-1 + 0) = 1.
Left at 3 (0), right at 5 (2).
Sum = 0 + 2 = 2 > 1, right to 4 (1).
Sum = 0 + 1 = 1, matches.
Add [-1,0,0,1], left to 4 (1), right to 3 (0), stop.

Step 6: Later pairs (e.g., -1,0 at 3) repeat or exceed target, skip.
Step 7: Positive pairs (e.g., 0,1) exceed target, stop.
Finish: Return [[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]].

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

Now, [2,2,2,2,2] with target 8.

Goal: Find quadruplets summing to 8.
Result for Reference: [[2,2,2,2]].
Start: Array is [2,2,2,2,2], result empty.
Step 1: Length 5 ≥ 4.
Step 2: Fix first at 2 (index 0).

Fix second at 2 (index 1).
Target = 8 - (2 + 2) = 4.
Left at 2 (2), right at 4 (2).
Sum = 2 + 2 = 4, matches.
Add [2,2,2,2], left to 3 (2), right to 3 (2), stop.

Step 3: Fix first at 2, second at 2 (index 2).

Duplicate, skip.

Step 4: Later pairs repeat, stop.
Finish: Return [[2,2,2,2]].

Code (Two-Pointer Technique)

Here’s the efficient Python code for LeetCode 18. It works in Python 3.6+. Test it on Replit!

def fourSum(nums: list[int], target: int) -> list[list[int]]:
    if len(nums) < 4:
        return []

    nums.sort()
    result = []

    for i in range(len(nums) - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        for j in range(i + 1, len(nums) - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue

            left = j + 1
            right = len(nums) - 1

            while left < right:
                curr_sum = nums[i] + nums[j] + nums[left] + nums[right]
                if curr_sum == target:
                    result.append([nums[i], nums[j], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif curr_sum < target:
                    left += 1
                else:
                    right -= 1

    return result

Alternative: Brute Force

Explanation

Check every possible quadruplet using four nested loops, adding matches to a set to avoid duplicates, then convert to a list. It’s simple but very slow.

Handle Edge Case.

If length < 4, return empty list.

Quadruple Loop.

Use four loops to pick all combinations.

Track Matches.

Add sums matching target to a set for uniqueness.

Return Result.

Convert set to list of lists.

Step-by-Step Example (Brute Force)

For nums = [1,0,-1], target = 0 (simplified):

Goal: Sum to 0.
Reference: [[1,0,-1]].
Start: Set for results.
Steps: Check [1,0,-1] = 0, add to set.
Finish: Return [[1,0,-1]].

Code (Brute Force)

Here’s the brute force Python code, less efficient but straightforward.

def fourSumBrute(nums: list[int], target: int) -> list[list[int]]:
    if len(nums) < 4:
        return []

    result_set = set()

    for i in range(len(nums) - 3):
        for j in range(i + 1, len(nums) - 2):
            for k in range(j + 1, len(nums) - 1):
                for l in range(k + 1, len(nums)):
                    if nums[i] + nums[j] + nums[k] + nums[l] == target:
                        result_set.add((nums[i], nums[j], nums[k], nums[l]))

    return [list(quad) for quad in result_set]

Complexity

Two-Pointer:

Time: O(n³) – Sorting O(n log n) + two-pointer scan O(n³).
Space: O(1) – Only result list.

Brute Force:

Time: O(n⁴) – Four nested loops.
Space: O(n) – Set for unique quadruplets.

Efficiency Notes

The two-pointer method is optimal, reducing time from O(n⁴) to O(n³) with sorting, making it practical for LeetCode 18.

Key Insights

Tips to master LeetCode 18:

Sort first to streamline pointer use and duplicate skipping
Fix two numbers to turn it into a two-sum problem
Skip duplicates at each step for uniqueness

Additional Example

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

Goal: Sum to 2.
Reference: [[-1,0,1,2]].
Steps: Sort [-1,0,1,2], fix -1,0, left 1, right 2, sum 2, match.
Result: [[-1,0,1,2]].

Edge Cases

Min Length: [1,2,3] – Returns [].
All Same: [1,1,1,1] – Returns [[1,1,1,1]] for target 4.
No Match: [1,2,3,4], target = 20 – Returns [].

Final Thoughts

The two-pointer technique is a clever way to solve LeetCode 18 in Python, efficient and clear. Check LeetCode 15: 3Sum for a related challenge!