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.
1#include <stdio.h>
2#include <stdlib.h>
3
4void swap(int *a, int *b) {
5 int
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.
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.
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.