Watch 10 video solutions for 4Sum, a medium level problem involving Array, Two Pointers, Sorting. This walkthrough by take U forward has 237,042 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 109Problem Overview: Given an integer array nums and a target value, return all unique quadruplets [a,b,c,d] such that a + b + c + d = target. The result must not contain duplicate quadruplets, which means careful handling of repeated values after sorting or during lookup.
Approach 1: Sort and Two-pointer Technique (Time: O(n^3), Space: O(1) extra)
Sort the array first, which enables efficient duplicate handling and the classic two‑pointer pattern. Fix the first two numbers using nested loops (i and j). For the remaining part of the array, place two pointers: left = j + 1 and right = n - 1. Compute the current sum of the four numbers. If the sum matches the target, store the quadruplet and move both pointers while skipping duplicates. If the sum is smaller, move left forward; if larger, move right backward. Sorting reduces the search space and makes duplicate elimination straightforward. This method relies heavily on concepts from Sorting and Two Pointers techniques.
Approach 2: Hash Map with Two Sum Reduction (Time: O(n^3), Space: O(n))
This approach reduces the 4Sum problem into repeated 2Sum searches using a hash map. Fix two indices (i and j) and compute the remaining target target2 = target - nums[i] - nums[j]. Now scan the rest of the array while maintaining a hash set of seen values. For each element x, check if target2 - x already exists in the set. If it does, a valid quadruplet is found. Insert the current value into the set and continue scanning. Duplicate filtering is handled by sorting the quadruplet or skipping repeated values. This approach trades additional memory for simpler lookups and uses fast O(1) average hash operations. The method builds directly on fundamentals from Array traversal and hash-based lookups.
Recommended for interviews: The sorted two-pointer solution is what most interviewers expect. It demonstrates pattern recognition (reducing 4Sum to a controlled search after sorting) and shows you understand duplicate handling and pointer movement. Mentioning the hash-map reduction shows awareness of alternative strategies, but the two-pointer approach is typically considered the cleanest and most optimal for this problem.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort + Two Pointers | O(n^3) | O(1) extra | Best general solution. Efficient duplicate handling and expected in interviews. |
| Hash Map with Two Sum Reduction | O(n^3) | O(n) | Useful when you prefer hash lookups over pointer manipulation. |