Problem editorial

4Sum

MediumTwo PointersArrayTwo PointersSorting

Editorial

Core insight

4Sum · Two Pointers

Core Insight for 4Sum

The transition from a brute force $O(N^4)$ to an optimal $O(N^3)$ solution relies on sorting the array first. Sorting establishes a monotonic relationship between the index and the value.

The key insight is that if we fix the first two numbers (nums[i] and nums[j]), the problem transforms into finding two other numbers (nums[left] and nums[right]) in the remaining sorted subarray that sum to a new target: remaining_target = target - nums[i] - nums[j].

Visual Description: Imagine the sorted array laid out on a number line.

We place two "anchors" (indices i and j) at the beginning.
We place a left pointer immediately after j and a right pointer at the very end of the array.
We calculate the sum of the values at these four positions.
Because the array is sorted, we have deterministic control:
- If the sum is less than the target, we know we need a larger value. Since nums[right] is already the maximum available, we must move left to the right to increase the sum.
- If the sum is greater than the target, we need a smaller value. We move right to the left to decrease the sum.
- If the sum matches, we record the quadruplet and move both pointers inward, skipping any identical values to ensure uniqueness.

This logic allows us to find the correct pair in linear time $O(N)$ for every fixed pair of i and j, rather than quadratic time $O(N^2)$ .

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 18: 4Sum Solution & Explanation

Problem Overview

TL;DR: Sort the input array, fix the first two numbers using nested loops, and use the converging two-pointer technique to find the remaining two numbers that complete the target sum.

The 4Sum problem asks us to find all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] within an integer array that sum up to a specific target. The indices must be distinct, and the result must not contain duplicate sets of values.

This is a direct extension of the 3Sum problem and a classic application of array manipulation techniques found in LeetCode 18. It serves as an excellent test of a candidate's ability to optimize brute-force logic into a manageable polynomial time complexity suitable for interviews.

Brute Force Approach for 4Sum

The naive approach to solving 4Sum involves iterating through every possible combination of four numbers in the array to check if their sum equals the target.

Naive Algorithm

Initialize a set to store unique quadruplets (to handle duplicates).
Create four nested loops with indices i, j, k, and l.
For each combination, check if nums[i] + nums[j] + nums[k] + nums[l] == target.
If true, sort the quadruplet and add it to the set.
Convert the set to a list and return.

Pseudo-code

text

sort(nums)
results = Set()
for i from 0 to n-4:
    for j from i+1 to n-3:
        for k from j+1 to n-2:
            for l from k+1 to n-1:
                if nums[i] + nums[j] + nums[k] + nums[l] == target:
                    results.add({nums[i], nums[j], nums[k], nums[l]})
return list(results)

Why this fails

Time Complexity: $O(N^4)$
With $N$ up to 200, $N^4$ results in $1.6 \times 10^9$ operations. In standard competitive programming and interview environments, the operation limit is typically around $10^8$ per second. This approach will result in a Time Limit Exceeded (TLE) error. Furthermore, managing duplicates using a Hash Set adds significant overhead compared to handling them logically during iteration.

Algorithm Strategy: Two Pointer Patterns

Sort the Array: This is a prerequisite for the two-pointer technique. It also clusters duplicates together, making it easy to skip them.
First Loop (Index i): Iterate from 0 to n-4.
- If nums[i] is the same as the previous element nums[i-1], skip it to avoid duplicate quadruplets.
Second Loop (Index j): Iterate from i+1 to n-3.
- If nums[j] is the same as nums[j-1] (and j > i+1), skip it.
Two Pointers (Indices left and right):
- Set left = j + 1 and right = n - 1.
- While left < right:
  - Calculate sum = nums[i] + nums[j] + nums[left] + nums[right].
  - Check against target.
  - Adjust pointers based on the comparison (move left forward if sum is too low, right backward if sum is too high).
  - When a match is found, record it. Then, increment left and decrement right, ensuring we skip over any subsequent duplicate values for both pointers to maintain uniqueness.

Execution Flow

Input: nums = [1, 0, -1, 0, -2, 2], target = 0
Sort: nums becomes [-2, -1, 0, 0, 1, 2].
Outer Loop (i=0): nums[i] = -2.
Inner Loop (j=1): nums[j] = -1.
- Target for remaining two: 0 - (-2) - (-1) = 3.
- Pointers: left at index 2 (val 0), right at index 5 (val 2).
- Check: -2 + -1 + 0 + 2 = -1. Sum < Target.
- Action: Move left to index 3 (val 0).
- Check: -2 + -1 + 0 + 2 = -1. Sum < Target.
- Action: Move left to index 4 (val 1).
- Check: -2 + -1 + 1 + 2 = 0. Match found!
- Record: [-2, -1, 1, 2].
- Move pointers inward. Loop ends.
Inner Loop (j=2): nums[j] = 0.
- Target for remaining two: 0 - (-2) - 0 = 2.
- Pointers: left at index 3 (val 0), right at index 5 (val 2).
- Check: -2 + 0 + 0 + 2 = 0. Match found!
- Record: [-2, 0, 0, 2].
- Move pointers inward. Loop ends.
Outer Loop (i=1): nums[i] = -1.
- Logic repeats... finds [-1, 0, 0, 1].
Termination: All loops complete. Return unique quadruplets.

Proof of Correctness

The correctness relies on the sorted property of the array. For any fixed pair (i, j), the remaining problem is to find (left, right) such that nums[left] + nums[right] == required_sum. The two-pointer approach is proven to find all such pairs in a sorted array because:

If sum < target, nums[left] is insufficient even with the largest possible remaining number (nums[right]). Therefore, nums[left] cannot be part of the solution with any index $\le$ right. We safely discard left.
If sum > target, nums[right] is too large even with the smallest possible remaining number (nums[left]). We safely discard right.
By skipping duplicates explicitly after processing a valid quadruplet or when advancing loops, we guarantee that the output set contains only unique combinations.

Pattern Reuse Notes

The Two Pointers - Converging pattern is highly versatile for array problems involving sums or areas.

LeetCode 11: Container With Most Water - Uses converging pointers to maximize area, moving the pointer corresponding to the shorter height.
LeetCode 15: 3Sum - The direct predecessor to 4Sum. Fix one number, find two.
LeetCode 16: 3Sum Closest - Similar to 3Sum, but instead of looking for an exact match, you track the minimum difference from the target.
LeetCode 167: Two Sum II - Input Array Is Sorted - The base case for this entire family of problems. 4Sum reduces to 3Sum, which reduces to this problem.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 18

cpp

1class Solution {
2public:
3    vector<vector<int>> fourSum(vector<int>& nums, int target) {
4        vector<vector<int>> result;
5        int n = nums.size();
6        if (n < 4) return result;
7        
8        sort(nums.begin(), nums.end());
9        
10        for (int i = 0; i < n - 3; i++) {
11            // Skip duplicates for the first number
12            if (i > 0 && nums[i] == nums[i - 1]) continue;
13            
14            for (int j = i + 1; j < n - 2; j++) {
15                // Skip duplicates for the second number
16                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
17                
18                int left = j + 1;
19                int right = n - 1;
20                
21                while (left < right) {
22                    // Use long long to prevent integer overflow
23                    long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
24                    
25                    if (sum == target) {
26                        result.push_back({nums[i], nums[j], nums[left], nums[right]});
27                        
28                        // Skip duplicates for left and right pointers
29                        while (left < right && nums[left] == nums[left + 1]) left++;
30                        while (left < right && nums[right] == nums[right - 1]) right--;
31                        
32                        left++;
33                        right--;
34                    } else if (sum < target) {
35                        left++;
36                    } else {
37                        right--;
38                    }
39                }
40            }
41        }
42        return result;
43    }
44};

Java Solution for LeetCode 18

java

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    public List<List<Integer>> fourSum(int[] nums, int target) {
7        List<List<Integer>> result = new ArrayList<>();
8        if (nums == null || nums.length < 4) return result;
9        
10        Arrays.sort(nums);
11        int n = nums.length;
12        
13        for (int i = 0; i < n - 3; i++) {
14            // Skip duplicates for the first number
15            if (i > 0 && nums[i] == nums[i - 1]) continue;
16            
17            for (int j = i + 1; j < n - 2; j++) {
18                // Skip duplicates for the second number
19                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
20                
21                int left = j + 1;
22                int right = n - 1;
23                
24                while (left < right) {
25                    // Cast to long to avoid integer overflow
26                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
27                    
28                    if (sum == target) {
29                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
30                        
31                        // Skip duplicates for the pointers
32                        while (left < right && nums[left] == nums[left + 1]) left++;
33                        while (left < right && nums[right] == nums[right - 1]) right--;
34                        
35                        left++;
36                        right--;
37                    } else if (sum < target) {
38                        left++;
39                    } else {
40                        right--;
41                    }
42                }
43            }
44        }
45        return result;
46    }
47}

Python Solution for LeetCode 18

python

1class Solution:
2    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
3        nums.sort()
4        n = len(nums)
5        result = []
6        
7        for i in range(n - 3):
8            # Skip duplicates for the first number
9            if i > 0 and nums[i] == nums[i - 1]:
10                continue
11                
12            for j in range(i + 1, n - 2):
13                # Skip duplicates for the second number
14                if j > i + 1 and nums[j] == nums[j - 1]:
15                    continue
16                
17                left, right = j + 1, n - 1
18                
19                while left < right:
20                    current_sum = nums[i] + nums[j] + nums[left] + nums[right]
21                    
22                    if current_sum == target:
23                        result.append([nums[i], nums[j], nums[left], nums[right]])
24                        
25                        # Skip duplicates for pointers
26                        while left < right and nums[left] == nums[left + 1]:
27                            left += 1
28                        while left < right and nums[right] == nums[right - 1]:
29                            right -= 1
30                            
31                        left += 1
32                        right -= 1
33                    elif current_sum < target:
34                        left += 1
35                    else:
36                        right -= 1
37                        
38        return result

AI Coach Insight

For 4Sum, focus on explaining why the structure works, not just naming Two Pointers.

Complexity Analysis

Time Complexity: $O(N^3)$

Sorting takes $O(N \log N)$ .
We have two nested loops running $O(N^2)$ times.
Inside the nested loops, the two-pointer operation runs in $O(N)$ time.
Total complexity is $O(N^2 \times N) = O(N^3)$ . Given $N=200$ , $200^3 = 8,000,000$ , which easily fits within time limits.

Space Complexity: $O(1)$ or $O(N)$

Space complexity depends on the sorting implementation. Python's Timsort uses $O(N)$ , while C++ std::sort (Introsort) uses $O(\log N)$ stack space.
We ignore the space required for the output list as per standard complexity analysis conventions. We do not use any auxiliary data structures like Hash Maps.

Related Patterns

Pattern: Two Pointer Patterns
Subpattern: Two Pointers - Converging (Sorted Array Target Sum)

This problem fits the Two Pointer pattern because, once the array is sorted, the problem of finding elements that sum to a target can be solved by manipulating pointers from both ends of a subarray. Specifically, fixing numbers reduces the problem dimension: 4Sum becomes 3Sum, which becomes 2Sum, solvable efficiently with converging pointers.

Common Mistakes & FAQ

Why does my solution fail specific test cases involving large numbers?
- Mistake: Not handling Integer Overflow.
- Reason: The constraints allow nums[i] to be $10^9$ . Four such numbers can sum to $4 \times 10^9$ , which exceeds the maximum value of a signed 32-bit integer ( $2.14 \times 10^9$ ).
- Consequence: The sum wraps around to a negative number, causing incorrect comparisons. Always use long long (C++) or long (Java) for the sum calculation. Python handles large integers automatically.
Why does my output contain duplicate quadruplets?
- Mistake: Failing to skip duplicates for i, j, or the left/right pointers.
- Reason: The problem requires unique quadruplets. If the input is [2, 2, 2, 2, 2] and target is 8, simply moving pointers one step at a time without checking nums[index] == nums[index-1] will generate multiple identical lists.
- Consequence: Wrong Answer on LeetCode.
Why do I get TLE (Time Limit Exceeded)?
- Mistake: Using the brute force $O(N^4)$ approach or not moving pointers correctly.
- Reason: $N=200$ is small, but $N^4$ is massive.
- Consequence: The solution is too slow for the online judge.
Why is my pointer logic failing?
- Mistake: Not sorting the array at the start.
- Reason: The "Two Pointers - Converging" pattern strictly relies on the array being sorted to make decisions about moving left or right.
- Consequence: The algorithm behaves randomly and produces incorrect results.

Practise 4Sum and the problems around it

4Sum is a Two Pointers problem, in the Converging (Sorted Array Target Sum) subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

4Sum · Two Pointers

Core Insight for 4Sum

The transition from a brute force $O(N^4)$ to an optimal $O(N^3)$ solution relies on sorting the array first. Sorting establishes a monotonic relationship between the index and the value.

Visual Description: Imagine the sorted array laid out on a number line.

We place two "anchors" (indices i and j) at the beginning.
We place a left pointer immediately after j and a right pointer at the very end of the array.
We calculate the sum of the values at these four positions.
Because the array is sorted, we have deterministic control:
- If the sum is less than the target, we know we need a larger value. Since nums[right] is already the maximum available, we must move left to the right to increase the sum.
- If the sum is greater than the target, we need a smaller value. We move right to the left to decrease the sum.
- If the sum matches, we record the quadruplet and move both pointers inward, skipping any identical values to ensure uniqueness.

This logic allows us to find the correct pair in linear time $O(N)$ for every fixed pair of i and j, rather than quadratic time $O(N^2)$ .

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 18: 4Sum Solution & Explanation

Problem Overview

TL;DR: Sort the input array, fix the first two numbers using nested loops, and use the converging two-pointer technique to find the remaining two numbers that complete the target sum.

Brute Force Approach for 4Sum

The naive approach to solving 4Sum involves iterating through every possible combination of four numbers in the array to check if their sum equals the target.

Naive Algorithm

Initialize a set to store unique quadruplets (to handle duplicates).
Create four nested loops with indices i, j, k, and l.
For each combination, check if nums[i] + nums[j] + nums[k] + nums[l] == target.
If true, sort the quadruplet and add it to the set.
Convert the set to a list and return.

Pseudo-code

text

sort(nums)
results = Set()
for i from 0 to n-4:
    for j from i+1 to n-3:
        for k from j+1 to n-2:
            for l from k+1 to n-1:
                if nums[i] + nums[j] + nums[k] + nums[l] == target:
                    results.add({nums[i], nums[j], nums[k], nums[l]})
return list(results)

Why this fails

Algorithm Strategy: Two Pointer Patterns

Sort the Array: This is a prerequisite for the two-pointer technique. It also clusters duplicates together, making it easy to skip them.
First Loop (Index i): Iterate from 0 to n-4.
- If nums[i] is the same as the previous element nums[i-1], skip it to avoid duplicate quadruplets.
Second Loop (Index j): Iterate from i+1 to n-3.
- If nums[j] is the same as nums[j-1] (and j > i+1), skip it.
Two Pointers (Indices left and right):
- Set left = j + 1 and right = n - 1.
- While left < right:
  - Calculate sum = nums[i] + nums[j] + nums[left] + nums[right].
  - Check against target.
  - Adjust pointers based on the comparison (move left forward if sum is too low, right backward if sum is too high).
  - When a match is found, record it. Then, increment left and decrement right, ensuring we skip over any subsequent duplicate values for both pointers to maintain uniqueness.

Execution Flow

Input: nums = [1, 0, -1, 0, -2, 2], target = 0
Sort: nums becomes [-2, -1, 0, 0, 1, 2].
Outer Loop (i=0): nums[i] = -2.
Inner Loop (j=1): nums[j] = -1.
- Target for remaining two: 0 - (-2) - (-1) = 3.
- Pointers: left at index 2 (val 0), right at index 5 (val 2).
- Check: -2 + -1 + 0 + 2 = -1. Sum < Target.
- Action: Move left to index 3 (val 0).
- Check: -2 + -1 + 0 + 2 = -1. Sum < Target.
- Action: Move left to index 4 (val 1).
- Check: -2 + -1 + 1 + 2 = 0. Match found!
- Record: [-2, -1, 1, 2].
- Move pointers inward. Loop ends.
Inner Loop (j=2): nums[j] = 0.
- Target for remaining two: 0 - (-2) - 0 = 2.
- Pointers: left at index 3 (val 0), right at index 5 (val 2).
- Check: -2 + 0 + 0 + 2 = 0. Match found!
- Record: [-2, 0, 0, 2].
- Move pointers inward. Loop ends.
Outer Loop (i=1): nums[i] = -1.
- Logic repeats... finds [-1, 0, 0, 1].
Termination: All loops complete. Return unique quadruplets.

Proof of Correctness

If sum < target, nums[left] is insufficient even with the largest possible remaining number (nums[right]). Therefore, nums[left] cannot be part of the solution with any index $\le$ right. We safely discard left.
If sum > target, nums[right] is too large even with the smallest possible remaining number (nums[left]). We safely discard right.
By skipping duplicates explicitly after processing a valid quadruplet or when advancing loops, we guarantee that the output set contains only unique combinations.

Pattern Reuse Notes

The Two Pointers - Converging pattern is highly versatile for array problems involving sums or areas.

LeetCode 11: Container With Most Water - Uses converging pointers to maximize area, moving the pointer corresponding to the shorter height.
LeetCode 15: 3Sum - The direct predecessor to 4Sum. Fix one number, find two.
LeetCode 16: 3Sum Closest - Similar to 3Sum, but instead of looking for an exact match, you track the minimum difference from the target.
LeetCode 167: Two Sum II - Input Array Is Sorted - The base case for this entire family of problems. 4Sum reduces to 3Sum, which reduces to this problem.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 18

cpp

1class Solution {
2public:
3    vector<vector<int>> fourSum(vector<int>& nums, int target) {
4        vector<vector<int>> result;
5        int n = nums.size();
6        if (n < 4) return result;
7        
8        sort(nums.begin(), nums.end());
9        
10        for (int i = 0; i < n - 3; i++) {
11            // Skip duplicates for the first number
12            if (i > 0 && nums[i] == nums[i - 1]) continue;
13            
14            for (int j = i + 1; j < n - 2; j++) {
15                // Skip duplicates for the second number
16                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
17                
18                int left = j + 1;
19                int right = n - 1;
20                
21                while (left < right) {
22                    // Use long long to prevent integer overflow
23                    long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
24                    
25                    if (sum == target) {
26                        result.push_back({nums[i], nums[j], nums[left], nums[right]});
27                        
28                        // Skip duplicates for left and right pointers
29                        while (left < right && nums[left] == nums[left + 1]) left++;
30                        while (left < right && nums[right] == nums[right - 1]) right--;
31                        
32                        left++;
33                        right--;
34                    } else if (sum < target) {
35                        left++;
36                    } else {
37                        right--;
38                    }
39                }
40            }
41        }
42        return result;
43    }
44};

Java Solution for LeetCode 18

java

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    public List<List<Integer>> fourSum(int[] nums, int target) {
7        List<List<Integer>> result = new ArrayList<>();
8        if (nums == null || nums.length < 4) return result;
9        
10        Arrays.sort(nums);
11        int n = nums.length;
12        
13        for (int i = 0; i < n - 3; i++) {
14            // Skip duplicates for the first number
15            if (i > 0 && nums[i] == nums[i - 1]) continue;
16            
17            for (int j = i + 1; j < n - 2; j++) {
18                // Skip duplicates for the second number
19                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
20                
21                int left = j + 1;
22                int right = n - 1;
23                
24                while (left < right) {
25                    // Cast to long to avoid integer overflow
26                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
27                    
28                    if (sum == target) {
29                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
30                        
31                        // Skip duplicates for the pointers
32                        while (left < right && nums[left] == nums[left + 1]) left++;
33                        while (left < right && nums[right] == nums[right - 1]) right--;
34                        
35                        left++;
36                        right--;
37                    } else if (sum < target) {
38                        left++;
39                    } else {
40                        right--;
41                    }
42                }
43            }
44        }
45        return result;
46    }
47}

Python Solution for LeetCode 18

python

1class Solution:
2    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
3        nums.sort()
4        n = len(nums)
5        result = []
6        
7        for i in range(n - 3):
8            # Skip duplicates for the first number
9            if i > 0 and nums[i] == nums[i - 1]:
10                continue
11                
12            for j in range(i + 1, n - 2):
13                # Skip duplicates for the second number
14                if j > i + 1 and nums[j] == nums[j - 1]:
15                    continue
16                
17                left, right = j + 1, n - 1
18                
19                while left < right:
20                    current_sum = nums[i] + nums[j] + nums[left] + nums[right]
21                    
22                    if current_sum == target:
23                        result.append([nums[i], nums[j], nums[left], nums[right]])
24                        
25                        # Skip duplicates for pointers
26                        while left < right and nums[left] == nums[left + 1]:
27                            left += 1
28                        while left < right and nums[right] == nums[right - 1]:
29                            right -= 1
30                            
31                        left += 1
32                        right -= 1
33                    elif current_sum < target:
34                        left += 1
35                    else:
36                        right -= 1
37                        
38        return result

Core Insight for 4Sum

LeetCode 18: 4Sum Solution & Explanation

Problem Overview

Brute Force Approach for 4Sum

Naive Algorithm

Pseudo-code

Why this fails

Algorithm Strategy: Two Pointer Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 18

Java Solution for LeetCode 18

Python Solution for LeetCode 18

Practise 4Sum and the problems around it

Related problems

Core Insight for 4Sum

LeetCode 18: 4Sum Solution & Explanation

Problem Overview

Brute Force Approach for 4Sum

Naive Algorithm

Pseudo-code

Why this fails

Algorithm Strategy: Two Pointer Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 18

Java Solution for LeetCode 18

Python Solution for LeetCode 18

Practise 4Sum and the problems around it

Related problems