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: 4Sum asks you to find all unique quadruplets [a, b, c, d] in an array such that their sum equals a given target. The main challenge is avoiding duplicate quadruplets while keeping the algorithm efficient. A naive four‑nested‑loop solution works but is far too slow for typical constraints.
Approach 1: Sort and Two-pointer Technique (Time: O(n^3), Space: O(1) extra)
Start by sorting the array. Sorting makes duplicate handling straightforward and enables the two-pointer pattern. Fix the first element with index i, then fix the second element with index j. The remaining two numbers are found using two pointers: one starting at j + 1 and the other at the end of the array. Compute the sum of the four elements and move pointers inward depending on whether the sum is smaller or larger than the target. Skip duplicates for i, j, and the pointer values to ensure each quadruplet appears once.
This approach works because sorting allows efficient pruning and duplicate elimination. Instead of checking every possible quadruple explicitly, the two-pointer step finds matching pairs in linear time. Overall complexity becomes O(n^3) after the O(n log n) sort. This pattern frequently appears in problems related to Two Pointers, Sorting, and advanced Array search techniques.
Approach 2: Hash Map with Two Sum Reduction (Time: O(n^3), Space: O(n))
This method reduces the 4Sum problem into repeated 2Sum searches. Iterate through pairs of indices (i, j) as the first two numbers. For the remaining portion of the array, compute the required complement target - nums[i] - nums[j]. A hash map or set tracks numbers seen while scanning the rest of the array, allowing constant‑time lookup for the complement pair.
Each iteration effectively becomes a classic 2Sum search using hashing. The key advantage is simpler pointer logic and direct complement lookups. However, handling duplicates becomes more complex, and the extra hash structure increases memory usage to O(n). Runtime still reaches O(n^3) because the outer two loops remain.
Recommended for interviews: The sorted two‑pointer solution is the expected approach. Interviewers want to see that you recognize the pattern: extend the 3Sum technique by fixing two indices and applying two pointers for the remaining pair. The brute-force four-loop idea shows baseline understanding, but the O(n^3) two-pointer optimization demonstrates stronger algorithmic thinking and familiarity with common array patterns.
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.
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.
Time Complexity: O(n^2), considering the use of a hash map.
Space Complexity: O(n), for storing intermediate and potential pairs.
We notice that the problem requires us to find non-repeating quadruplets. Therefore, we can first sort the array, which makes it easy to skip duplicate elements.
Next, we enumerate the first two elements of the quadruplet, nums[i] and nums[j], where i \lt j. During the enumeration process, we skip duplicate nums[i] and nums[j]. Then, we use two pointers k and l to point to the two ends behind nums[i] and nums[j]. Let x = nums[i] + nums[j] + nums[k] + nums[l], we compare x with target and perform the following operations:
x \lt target, then update k = k + 1 to get a larger x;x \gt target, then update l = l - 1 to get a smaller x;(nums[i], nums[j], nums[k], nums[l]) is found. Add it to the answer, then we update the pointers k and l, and skip all duplicate elements to prevent the answer from containing duplicate quadruplets, and continue to find the next quadruplet.The time complexity is O(n^3), and the space complexity is O(log n). Here, n is the length of the array.
Python
Java
C++
Go
TypeScript
JavaScript
C#
PHP
| 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. |
| Sorting + Double Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort + Two Pointers | O(n^3) | O(1) | Best general solution. Efficient duplicate handling and common interview pattern. |
| Hash Map with Two Sum Reduction | O(n^3) | O(n) | Useful when using hash-based complement lookup or extending the Two Sum pattern. |
4 Sum | Brute - Better - Optimal with Codes • take U forward • 368,179 views views
Watch 9 more video solutions →Practice 4Sum with our built-in code editor and test cases.
Practice on FleetCode