LeetCode Problem 18

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Sorting

Solution

LeetCode 18 - 4Sum

Problem Statement

We are given an integer array nums and an integer target. The goal is to find every unique quadruplet of numbers in the array whose sum equals the target value.

A quadruplet consists of four elements:

nums[a], nums[b], nums[c], nums[d]

where all four indices are distinct. The output should contain only unique quadruplets, meaning different index combinations that produce the same four values should appear only once.

The order of quadruplets in the final answer does not matter, and the order of elements inside each quadruplet also does not matter as long as duplicates are avoided.

The input size is relatively moderate, with nums.length <= 200. This is large enough that a naive brute-force solution becomes impractical, because checking every possible quadruplet grows very quickly as the array size increases.

The values inside the array and the target can range from -10^9 to 10^9. This means:

• Negative numbers are allowed
• Positive numbers are allowed
• Large integer sums are possible
• We must be careful about duplicate handling

Several edge cases are important:

• Arrays with fewer than four elements cannot produce any quadruplet
• Arrays with many repeated values can easily create duplicate answers
• Arrays containing only identical numbers should still return only one valid quadruplet if appropriate
• Large positive and negative values may create overflow concerns in some languages
• Multiple valid quadruplets may exist

The problem guarantees only that the input is a valid integer array and target value. It does not guarantee uniqueness, sorting, or any special structure in the input.

Problem Understanding

The problem asks us to search through the array and identify every unique set of four numbers whose sum equals the target.

For example, given:

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

we need to find all groups of four numbers that sum to zero.

One valid group is:

[-2, -1, 1, 2]

because:

-2 + -1 + 1 + 2 = 0

Another valid group is:

[-2, 0, 0, 2]

The key challenge is avoiding duplicates. Since the array may contain repeated values, different index combinations can generate the same quadruplet values. We must return each unique quadruplet only once.

This problem is an extension of the classic 2Sum and 3Sum problems. The natural progression is:

• 2Sum uses hashing or two pointers
• 3Sum fixes one number and solves 2Sum
• 4Sum fixes two numbers and solves 2Sum

The optimal solution leverages sorting and the two-pointer technique to reduce complexity significantly.

Approaches

Brute Force Approach

The brute-force solution checks every possible quadruplet.

We can use four nested loops:

• The first loop chooses the first element
• The second loop chooses the second element
• The third loop chooses the third element
• The fourth loop chooses the fourth element

For every quadruplet, we calculate the sum and compare it with the target.

If the sum matches the target, we add the quadruplet to the result set. To avoid duplicates, we would need an additional mechanism such as a hash set containing sorted tuples.

This approach is correct because it exhaustively checks every possible combination of four indices. However, it is extremely slow.

With n = 200, the number of combinations becomes:

O(n^4)

which is too expensive.

Key Insight for the Optimal Solution

The crucial observation is that once the array is sorted, we can reduce the problem complexity using the two-pointer technique.

Instead of trying all four elements independently:

• Fix the first number
• Fix the second number
• Use two pointers to find the remaining two numbers

After sorting:

• If the current sum is too small, move the left pointer rightward
• If the current sum is too large, move the right pointer leftward
• If the sum matches the target, record the quadruplet and skip duplicates

Sorting enables efficient duplicate elimination and allows the two-pointer search to work correctly.

This reduces the complexity from O(n^4) to O(n^3).

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^4)	O(1) or O(k)	Checks every quadruplet explicitly
Optimal	O(n^3)	O(1) excluding output	Uses sorting and two pointers

Algorithm Walkthrough

Optimal Algorithm

1. Sort the array.

Sorting is essential because it allows us to:

• Use the two-pointer technique
• Skip duplicates efficiently
• Make pointer movement decisions based on sum comparisons

2. Iterate through the array with index i.

This selects the first number of the quadruplet.

Skip duplicate values for i to avoid generating repeated quadruplets. 3. For each i, iterate with index j.

This selects the second number of the quadruplet.

Again, skip duplicate values for j. 4. Initialize two pointers.

Set:

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

These pointers search for the remaining two numbers. 5. Compute the current sum.

The current quadruplet sum is:

nums[i] + nums[j] + nums[left] + nums[right]

6. Compare the sum with the target.

• If the sum is smaller than the target, move left forward to increase the sum
• If the sum is larger than the target, move right backward to decrease the sum
• If the sum equals the target, record the quadruplet

7. Skip duplicates after finding a valid quadruplet.

Move the pointers past repeated values so the same quadruplet is not added again. 8. Continue until left >= right.

Once the pointers cross, all valid pairs for the current (i, j) combination have been explored.

Why it works

The algorithm works because sorting creates a monotonic structure.

For fixed indices i and j:

• Moving left rightward always increases or preserves the sum
• Moving right leftward always decreases or preserves the sum

This guarantees that every valid pair is discovered exactly once.

Duplicate skipping ensures uniqueness because repeated values are ignored after their first occurrence at each level of iteration.

Python Solution

from typing import List

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        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

                left = j + 1
                right = n - 1

                while left < right:
                    current_sum = (
                        nums[i]
                        + nums[j]
                        + nums[left]
                        + nums[right]
                    )

                    if current_sum < target:
                        left += 1

                    elif current_sum > target:
                        right -= 1

                    else:
                        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

        return result

The implementation begins by sorting the array. This is the foundation of the two-pointer strategy and duplicate handling.

The outer loop selects the first element of the quadruplet. Before processing, the code checks whether the current value is the same as the previous value. If so, it skips the iteration to avoid duplicate quadruplets.

The second loop selects the second element using the same duplicate-skipping logic.

After fixing the first two elements, the remaining two elements are found using two pointers.

The left pointer starts immediately after j, while the right pointer starts at the end of the array.

The algorithm computes the four-number sum:

current_sum = nums[i] + nums[j] + nums[left] + nums[right]

If the sum is too small, the left pointer moves rightward. If the sum is too large, the right pointer moves leftward.

When the sum matches the target, the quadruplet is added to the result list. Then both pointers move inward, and duplicate values are skipped to prevent repeated answers.

Finally, the result list is returned.

Go Solution

package main

import "sort"

func fourSum(nums []int, target int) [][]int {
	sort.Ints(nums)

	result := [][]int{}
	n := len(nums)

	for i := 0; i < n-3; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}

		for j := i + 1; j < n-2; j++ {
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}

			left := j + 1
			right := n - 1

			for left < right {
				currentSum := nums[i] +
					nums[j] +
					nums[left] +
					nums[right]

				if currentSum < target {
					left++

				} else if currentSum > target {
					right--

				} else {
					result = append(result, []int{
						nums[i],
						nums[j],
						nums[left],
						nums[right],
					})

					left++
					right--

					for left < right &&
						nums[left] == nums[left-1] {
						left++
					}

					for left < right &&
						nums[right] == nums[right+1] {
						right--
					}
				}
			}
		}
	}

	return result
}

The Go implementation follows the same logic as the Python version.

One important consideration in Go is integer overflow. Since the constraints allow values up to 10^9, summing four integers may exceed the 32-bit integer range on some systems. Go's int type is typically 64-bit on modern platforms, which is sufficient here, but using int64 would be safer in production systems with strict portability requirements.

The result is stored as a slice of integer slices:

[][]int

Go does not distinguish between nil and empty slices in a problematic way for LeetCode submissions, so returning an empty slice is acceptable.

Worked Examples

Example 1

Input:

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

Step 1: Sort the array

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

Iteration Trace

i	j	left	right	Values	Sum	Action
0	1	2	5	[-2,-1,0,2]	-1	Move left
0	1	3	5	[-2,-1,0,2]	-1	Move left
0	1	4	5	[-2,-1,1,2]	0	Add result
0	2	3	5	[-2,0,0,2]	0	Add result
0	3	duplicate				Skip
1	2	3	5	[-1,0,0,2]	1	Move right
1	2	3	4	[-1,0,0,1]	0	Add result

Final result:

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

Example 2

Input:

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

Step 1: Sort the array

[2,2,2,2,2]

Iteration Trace

i	j	left	right	Values	Sum	Action
0	1	2	4	[2,2,2,2]	8	Add result
0	2	duplicate				Skip
1	duplicate					Skip

Final result:

[[2,2,2,2]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^3)	Two nested loops plus linear two-pointer scan
Space	O(1) excluding output	Uses only pointer variables after sorting

The sorting step costs:

O(n log n)

However, the dominant cost comes from the nested loops and two-pointer traversal.

For each pair (i, j), the two-pointer scan runs in linear time. Since there are approximately O(n^2) choices for (i, j), the total complexity becomes:

O(n^3)

The algorithm uses constant auxiliary space because it only stores indices and pointers. The result array itself is not counted in auxiliary space complexity.

Test Cases

from typing import List

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        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

                left = j + 1
                right = n - 1

                while left < right:
                    current_sum = (
                        nums[i]
                        + nums[j]
                        + nums[left]
                        + nums[right]
                    )

                    if current_sum < target:
                        left += 1

                    elif current_sum > target:
                        right -= 1

                    else:
                        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

        return result

solution = Solution()

# Provided example with multiple answers
assert sorted(solution.fourSum(
    [1, 0, -1, 0, -2, 2],
    0
)) == sorted([
    [-2, -1, 1, 2],
    [-2, 0, 0, 2],
    [-1, 0, 0, 1]
])

# All identical numbers
assert solution.fourSum(
    [2, 2, 2, 2, 2],
    8
) == [[2, 2, 2, 2]]

# No valid quadruplet
assert solution.fourSum(
    [1, 2, 3, 4],
    100
) == []

# Array smaller than four elements
assert solution.fourSum(
    [1, 2, 3],
    6
) == []

# Negative numbers
assert sorted(solution.fourSum(
    [-5, -4, -3, -2, -1],
    -10
)) == sorted([
    [-4, -3, -2, -1]
])

# Multiple duplicates
assert sorted(solution.fourSum(
    [0, 0, 0, 0, 0, 0],
    0
)) == sorted([
    [0, 0, 0, 0]
])

# Large positive and negative values
assert sorted(solution.fourSum(
    [1000000000, 1000000000, -1000000000, -1000000000],
    0
)) == sorted([
    [-1000000000, -1000000000, 1000000000, 1000000000]
])

# Mixed values with several valid answers
assert sorted(solution.fourSum(
    [-3, -1, 0, 2, 4, 5],
    2
)) == sorted([
    [-3, -1, 2, 4]
])

Test Summary

Test	Why
Standard example	Validates normal operation with multiple answers
All identical values	Ensures duplicate skipping works correctly
No solution	Verifies empty result handling
Fewer than four elements	Tests minimum size boundary
All negative values	Confirms negative sums are handled
Many duplicates	Ensures uniqueness logic is correct
Large integers	Tests potential overflow scenarios
Mixed positive and negative values	Validates general correctness

Edge Cases

Arrays With Many Duplicate Values

Duplicate handling is the most common source of bugs in this problem.

Consider:

[2,2,2,2,2]

Without careful duplicate skipping, the algorithm could generate the same quadruplet many times.

The implementation avoids this by:

• Skipping repeated i values
• Skipping repeated j values
• Skipping repeated left and right values after a match

This guarantees uniqueness.

Arrays Smaller Than Four Elements

If the array contains fewer than four numbers, no quadruplet can exist.

For example:

[1,2,3]

The loops naturally handle this because:

range(n - 3)

becomes empty when n < 4.

As a result, the algorithm safely returns an empty list without requiring special-case code.

Large Integer Values

The constraints allow values up to:

10^9

Summing four such values can exceed 32-bit integer limits.

Python handles large integers automatically, so overflow is not an issue there.

In Go, the standard int type is usually sufficient on modern systems, but developers should remain aware of overflow risks in languages with strict 32-bit integers.

Multiple Valid Quadruplets Sharing Numbers

Different valid quadruplets may reuse the same values but at different positions.

For example:

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

contains several overlapping solutions.

The algorithm correctly explores every valid (i, j) pair and uses two pointers to exhaust all remaining possibilities, ensuring no valid quadruplet is missed.