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 4Sum problem asks you to find all unique quadruplets in an array that add up to a given target. A common strategy begins by sorting the array, which helps manage duplicates and enables efficient pointer movement.
After sorting, fix the first two numbers using nested loops. For the remaining part of the array, apply the two-pointer technique to search for the remaining two numbers that complete the target sum. By adjusting the left and right pointers based on the current sum, you can systematically explore valid combinations while skipping duplicates to ensure unique quadruplets.
This approach significantly improves performance compared to brute force. The typical solution runs in O(n^3) time after sorting, with O(1) extra space (excluding the result). Careful handling of duplicate elements and pointer movement is key to producing correct and efficient results.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force (4 nested loops) | O(n^4) | O(1) |
| Sorting + Two Pointers | O(n^3) | O(1) |
take U forward
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.
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.
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5public
Java's solution utilizes Arrays.sort for quick sorting and ArrayList for dynamic storage of resulting quadruplets. The algorithm detects target-compliant sums while traversing the array with nested loops, preventing duplicate evaluations.
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.
Time Complexity: O(n^2), considering the use of a hash map.
Space Complexity: O(n), for storing intermediate and potential pairs.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, 4Sum and its variations frequently appear in coding interviews at top tech companies. Interviewers use it to test understanding of sorting, two-pointer techniques, and handling duplicates in combination problems.
The optimal approach typically involves sorting the array and then fixing two elements with nested loops while using a two-pointer technique for the remaining pair. This reduces the search space efficiently and avoids duplicates. The time complexity is usually O(n^3).
Sorting allows the two-pointer technique to work efficiently and helps skip duplicate values. It ensures that quadruplets are generated in an ordered manner, making it easier to avoid repeated combinations.
Most efficient solutions rely primarily on arrays along with the two-pointer technique after sorting. While hash sets can be used to track duplicates in some variations, the classic approach works directly on the sorted array.
JavaScript harnesses object maps in place of hash maps to find pairs and tracks the current indices by avoiding passing over redundant pairs. The algorithm refines runtime via systematic exemptions.