A complete visual walkthrough of the sorted two-pointer approach — generalizing 3Sum with an extra layer of iteration.
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < na, b, c, and d are distinct.nums[a] + nums[b] + nums[c] + nums[d] == targetYou may return the answer in any order.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [2,2,2,2,2], target = 8 Output: [[2,2,2,2]]
Constraints:
1 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109The most straightforward approach: try every combination of four distinct indices and check if they sum to the target.
for a in 0..n for b in a+1..n for c in b+1..n for d in c+1..n if nums[a]+nums[b]+nums[c]+nums[d] == target add([nums[a], nums[b], nums[c], nums[d]])
for a := 0; a < n; a++ { for b := a+1; b < n; b++ { for c := b+1; c < n; c++ { for d := c+1; d < n; d++ { if nums[a]+nums[b]+nums[c]+nums[d] == target { result = append(result, []int{nums[a], nums[b], nums[c], nums[d]}) } } } } }
for a in 0..n for b in a+1..n for c in b+1..n for d in c+1..n if nums[a]+nums[b]+nums[c]+nums[d] == target add([nums[a], nums[b], nums[c], nums[d]])
for a in 0..n { for b in (a+1)..n { for c in (b+1)..n { for d in (c+1)..n { if nums[a]+nums[b]+nums[c]+nums[d] == target { result.push(vec![nums[a], nums[b], nums[c], nums[d]]); } } } } }
for a in 0..n for b in a+1..n for c in b+1..n for d in c+1..n if nums[a]+nums[b]+nums[c]+nums[d] === target add([nums[a], nums[b], nums[c], nums[d]])
This runs in O(n4) time. For n = 200 that is 2004 = 1.6 billion operations. We also need a set to avoid duplicate quadruplets, making it even slower.
Can we do better? If you have solved 2Sum and 3Sum, the pattern is clear: sort the array, fix the outer elements with loops, and use two pointers for the innermost pair. Each level of "fixing" removes one power from the exponent.
The key idea is a layered reduction. Just as 3Sum reduced to 2Sum by fixing one element, 4Sum reduces to 3Sum by fixing one more. After sorting, we can skip duplicates at every level.
Why sorting is essential: Sorting enables two things at once. First, the two-pointer technique works because the array is monotonic. Second, duplicate skipping becomes trivial — identical adjacent values can be skipped with a simple comparison. Sorting costs O(n log n), which is dominated by O(n³).
Each level skips over values that are the same as the previous iteration to avoid generating the same quadruplet more than once.
if (i > 0 && nums[i] == nums[i-1]) continue;if (j > i+1 && nums[j] == nums[j-1]) continue;while (left < right && nums[left] == nums[left+1]) left++;while (left < right && nums[right] == nums[right-1]) right--;Let's walk through nums = [1, 0, -1, 0, -2, 2] with target = 0. First, sort the array:
With i=0 (value -2) and j=1 (value -1), we need left+right to sum to 3. Two pointers scan from both ends.
With i=0 (value -2) and j=2 (value 0), we need left+right to sum to 2.
With i=1 (value -1) and j=2 (value 0), we need left+right to sum to 1.
Result: 3 unique quadruplets found. Notice how duplicate skipping ensures we never process the same combination twice, even though the value 0 appears at two different indices.
Several tricky scenarios can trip up a naive implementation.
nums.length < 4, there are no quadruplets to form. Return an empty list immediately.
int (e.g., nums = [109, 109, 109, 109]). Cast to long before adding: (long)nums[i] + nums[j] + nums[left] + nums[right].
[0, 0, 0, 0, 0, 0] with target 0 should produce exactly one quadruplet [0, 0, 0, 0]. Without proper duplicate skipping, you would get many copies.
nums = [1,2,3,4], target = 100.
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { Arrays.sort(nums); // Sort to enable two-pointer + dedup List<List<Integer>> result = new ArrayList<>(); // First element: index i for (int i = 0; i < nums.length - 3; i++) { // Skip duplicate values for i if (i > 0 && nums[i] == nums[i - 1]) continue; // Second element: index j for (int j = i + 1; j < nums.length - 2; j++) { // Skip duplicate values for j if (j > i + 1 && nums[j] == nums[j - 1]) continue; // Two pointers for the remaining pair int left = j + 1, right = nums.length - 1; while (left < right) { // Use long to prevent integer overflow! long sum = (long) nums[i] + nums[j] + nums[left] + nums[right]; if (sum == target) { // Found a valid quadruplet result.add(Arrays.asList( nums[i], nums[j], nums[left], nums[right] )); // Skip duplicates for left pointer while (left < right && nums[left] == nums[left + 1]) left++; // Skip duplicates for right pointer while (left < right && nums[right] == nums[right - 1]) right--; // Move both inward past the match left++; right--; } else if (sum < target) { left++; // Need a larger sum } else { right--; // Need a smaller sum } } } } return result; } }
func fourSum(nums []int, target int) [][]int { sort.Ints(nums) // Sort to enable two-pointer + dedup result := [][]int{} n := len(nums) // First element: index i for i := 0; i < n-3; i++ { // Skip duplicate values for i if i > 0 && nums[i] == nums[i-1] { continue } // Second element: index j for j := i + 1; j < n-2; j++ { // Skip duplicate values for j if j > i+1 && nums[j] == nums[j-1] { continue } // Two pointers for the remaining pair left, right := j+1, n-1 for left < right { // Use int64 to prevent integer overflow! sum := int64(nums[i]) + int64(nums[j]) + int64(nums[left]) + int64(nums[right]) if sum == int64(target) { // Found a valid quadruplet result = append(result, []int{ nums[i], nums[j], nums[left], nums[right], }) // Skip duplicates for left pointer for left < right && nums[left] == nums[left+1] { left++ } // Skip duplicates for right pointer for left < right && nums[right] == nums[right-1] { right-- } // Move both inward past the match left++ right-- } else if sum < int64(target) { left++ // Need a larger sum } else { right-- // Need a smaller sum } } } } return result }
def four_sum(nums: list[int], target: int) -> list[list[int]]: nums.sort() # Sort to enable two-pointer + dedup result: list[list[int]] = [] # First element: index i for i in range(len(nums) - 3): # Skip duplicate values for i if i > 0 and nums[i] == nums[i - 1]: continue # Second element: index j for j in range(i + 1, len(nums) - 2): # Skip duplicate values for j if j > i + 1 and nums[j] == nums[j - 1]: continue # Two pointers for the remaining pair left, right = j + 1, len(nums) - 1 while left < right: # Python ints have arbitrary precision — no overflow total = nums[i] + nums[j] + nums[left] + nums[right] if total == target: # Found a valid quadruplet result.append([ nums[i], nums[j], nums[left], nums[right] ]) # Skip duplicates for left pointer while (left < right and nums[left] == nums[left + 1]): left += 1 # Skip duplicates for right pointer while (left < right and nums[right] == nums[right - 1]): right -= 1 # Move both inward past the match left += 1 right -= 1 elif total < target: left += 1 # Need a larger sum else: right -= 1 # Need a smaller sum return result
impl Solution { pub fn four_sum(nums: Vec<i32>, target: i32) -> Vec<Vec<i32>> { let mut nums = nums; nums.sort(); // Sort to enable two-pointer + dedup let mut result: Vec<Vec<i32>> = Vec::new(); let n = nums.len(); // First element: index i for i in 0..n.saturating_sub(3) { // Skip duplicate values for i if i > 0 && nums[i] == nums[i-1] { continue; } // Second element: index j for j in (i+1)..n.saturating_sub(2) { // Skip duplicate values for j if j > i+1 && nums[j] == nums[j-1] { continue; } // Two pointers for the remaining pair let (mut left, mut right) = (j+1, n-1); while left < right { // Use i64 to prevent integer overflow! let sum = nums[i] as i64 + nums[j] as i64 + nums[left] as i64 + nums[right] as i64; if sum == target as i64 { // Found a valid quadruplet result.push(vec![nums[i], nums[j], nums[left], nums[right]]); // Skip duplicates for left pointer while left < right && nums[left] == nums[left+1] { left += 1; } // Skip duplicates for right pointer while left < right && nums[right] == nums[right-1] { right -= 1; } // Move both inward past the match left += 1; right -= 1; } else if sum < target as i64 { left += 1; // Need a larger sum } else { right -= 1; // Need a smaller sum } } } } result } }
function fourSum(nums: number[], target: number): number[][] { nums.sort((a, b) => a - b); // Sort to enable two-pointer + dedup const result: number[][] = []; // First element: index i for (let i = 0; i < nums.length - 3; i++) { // Skip duplicate values for i if (i > 0 && nums[i] === nums[i - 1]) continue; // Second element: index j for (let j = i + 1; j < nums.length - 2; j++) { // Skip duplicate values for j if (j > i + 1 && nums[j] === nums[j - 1]) continue; // Two pointers for the remaining pair let left = j + 1, right = nums.length - 1; while (left < right) { // Sum is safe — JS numbers are 64-bit floats const sum = nums[i] + nums[j] + nums[left] + nums[right]; if (sum === target) { // Found a valid quadruplet result.push([ nums[i], nums[j], nums[left], nums[right] ]); // Skip duplicates for left pointer while (left < right && nums[left] === nums[left + 1]) left++; // Skip duplicates for right pointer while (left < right && nums[right] === nums[right - 1]) right--; // Move both inward past the match left++; right--; } else if (sum < target) { left++; // Need a larger sum } else { right--; // Need a smaller sum } } } } return result; }
The long cast is critical. Without it, nums[i] + nums[j] + nums[left] + nums[right] can overflow a 32-bit integer. Casting the first operand to long promotes the entire expression to 64-bit arithmetic.
Enter an array and target, then step through the algorithm to see how i, j, left, and right move through the sorted array.
The outer two loops contribute O(n2), and the inner two-pointer scan is O(n), giving O(n3) total. Sorting is O(n log n), dominated by the cubic term. Space is O(1) excluding the output list — the sort is in-place and we only use pointer variables.
Four nested loops try every combination of four distinct indices. Each loop iterates up to n times, giving n4 total comparisons. Only loop variables and the result list are used, so auxiliary space is O(1).
Fix two elements with O(n2) nested loops, then use a hash map for O(1) lookups to find the fourth element. The hash map stores up to n values, giving O(n) space. Duplicate handling adds complexity compared to the two-pointer approach.
Two outer loops fix two elements in O(n2), then two pointers converge from both ends of the remaining subarray in O(n). Sorting costs O(n log n), dominated by the O(n3) main phase. In-place sort and pointer variables keep space at O(1).
Each additional "k" in k-Sum adds one O(n) loop. 2Sum = O(n), 3Sum = O(n2), 4Sum = O(n3). The pattern is: sort the array, fix k-2 elements with nested loops, then use two pointers for the last pair. The two-pointer technique always shaves one power of n from the brute force.
Review these before coding to avoid predictable interview regressions.
Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.
Usually fails on: A valid pair can be skipped when only one side should move.
Fix: Move exactly one pointer per decision branch based on invariant.