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.
This approach employs sorting the array and fixing two pointers while searching for the other two via a two-pointer method. This reduces the dimensionality of the problem stepwise.
In this C solution, a simple bubble sort algorithm is used to sort the array. The quadruplets are found by applying two nested loops fixing two elements and then using the two-pointer technique on the remaining array to find pairs that sum up to the required target. Duplication is avoided by skipping identical elements during iteration.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^3), where n is the number of elements in the array due to three nested loops.
Space Complexity: O(1), excluding the space required for the output storage.
This method reduces the four-sum problem by first reducing it to a three-sum problem, and then a two-sum problem using hash maps.
This solution uses a hash map to store potential pairs and provides an immediate reference to check against the target. Developing all valid pairs without duplicates requires keeping unique property checks on loop iterations.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), considering the use of a hash map.
Space Complexity: O(n), for storing intermediate and potential pairs.
| Approach | Complexity |
|---|---|
| Approach 1: Sort and Two-pointer Technique | Time Complexity: O(n^3), where n is the number of elements in the array due to three nested loops. |
| Approach 2: Hash Map with Two Sum Reduction | Time Complexity: O(n^2), considering the use of a hash map. |
| 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. |
4 Sum | Brute - Better - Optimal with Codes • take U forward • 237,042 views views
Watch 9 more video solutions →Practice 4Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor