4Sum
Med#0018Time: O(n^4)Space: O(k), where k is the number of unique quadruplets found. This is for the `HashSet`.20 companies
Prompt
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, anddare distinct.nums[a] + nums[b] + nums[c] + nums[d] == target
You 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 <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This is the most straightforward but least efficient approach. It involves iterating through every possible combination of four distinct elements in the array and checking if their sum equals the target.
Algorithm
- Sort the input array
nums. - Create a
HashSetto store unique quadruplets. - Use a loop for
ifrom0ton-4. - Inside, use a loop for
jfromi+1ton-3. - Inside, use a loop for
kfromj+1ton-2. - Inside, use a loop for
lfromk+1ton-1. - Check if
(long) nums[i] + nums[j] + nums[k] + nums[l] == target. - If the condition is true, add the list
(nums[i], nums[j], nums[k], nums[l])to theHashSet. - After the loops, return a new
ArrayListcreated from theHashSet.
Walkthrough
The algorithm iterates through all possible combinations of four distinct indices i, j, k, and l using four nested loops. For each combination, it checks if the sum of the elements at these indices equals the target. To handle permutations of the same set of numbers as a single unique quadruplet (e.g., [-1, 0, 0, 1] is the same as [0, -1, 1, 0]), we can sort the input array first. This ensures that when we find a valid quadruplet (nums[i], nums[j], nums[k], nums[l]) where i < j < k < l, it is in a canonical sorted order. We then add this quadruplet to a HashSet to automatically handle any duplicates that might arise from different combinations of indices yielding the same values (e.g., if the input has duplicate numbers). Finally, the content of the set is converted to a list and returned. It's important to use a long for the sum to prevent potential integer overflow.
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { int n = nums.length; Set<List<Integer>> resultSet = new HashSet<>(); Arrays.sort(nums); for (int i = 0; i < n - 3; i++) { for (int j = i + 1; j < n - 2; j++) { for (int k = j + 1; k < n - 1; k++) { for (int l = k + 1; l < n; l++) { long sum = (long) nums[i] + nums[j] + nums[k] + nums[l]; if (sum == target) { resultSet.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l])); } } } } } return new ArrayList<>(resultSet); }}Complexity
Time
O(n^4)
Space
O(k), where k is the number of unique quadruplets found. This is for the `HashSet`.
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely inefficient.
Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
This is an efficient approach that leverages sorting to avoid redundant calculations and to easily find the required pairs. It reduces the problem to a 3-Sum problem for each element, which is then further reduced to a 2-Sum problem solved efficiently with two pointers.
Algorithm
- Sort the input array
nums. - Initialize an empty list
result. - Iterate through the array with index
ifrom0ton-4. Skip duplicates. - Inside, iterate with index
jfromi+1ton-3. Skip duplicates. - Initialize two pointers,
left = j + 1andright = n - 1. - While
left < right:- Calculate the
sumofnums[i],nums[j],nums[left], andnums[right]. - If
sum == target, add the quadruplet toresult. Then, moveleftandrightpointers inward, skipping any duplicate values. - If
sum < target, incrementleft. - If
sum > target, decrementright.
- Calculate the
- Return the
resultlist.
Walkthrough
The first and most crucial step is to sort the input array nums. Sorting allows us to:
- Use the two-pointer technique to find pairs with a specific sum in linear time.
- Easily skip duplicate elements to ensure the uniqueness of the resulting quadruplets without needing an extra
Set.
The overall algorithm works by fixing the first two numbers of the quadruplet and then finding the other two.
- We use a main loop to iterate through the array and pick the first number,
nums[i]. - A nested loop picks the second number,
nums[j]. - For each pair
(nums[i], nums[j]), our goal is to find two other numbersnums[left]andnums[right]in the rest of the array (from indexj+1ton-1). - This is a classic 2-Sum problem on a sorted subarray, which we solve using the two-pointer approach. We initialize
left = j + 1andright = n - 1. - We then move these pointers inward based on their sum compared to the required sum, until
leftcrossesright. - To avoid duplicate quadruplets, we add checks. After finding a valid quadruplet, we advance the
leftandrightpointers past any subsequent duplicate elements. Similarly, in the outer loops foriandj, we skip iterations where the current element is the same as the previous one. - A critical detail is to use
longfor the sum to prevent integer overflow.
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> result = new ArrayList<>(); if (nums == null || nums.length < 4) { return result; } int n = nums.length; Arrays.sort(nums); for (int i = 0; i < n - 3; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip duplicates for i // Early exit optimizations if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break; if ((long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue; for (int j = i + 1; j < n - 2; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) continue; // Skip duplicates for j // Early exit optimizations if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break; if ((long) nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) continue; int left = j + 1; int right = n - 1; while (left < right) { long sum = (long) nums[i] + nums[j] + nums[left] + nums[right]; if (sum == target) { result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); left++; right--; while (left < right && nums[left] == nums[left - 1]) left++; while (left < right && nums[right] == nums[right + 1]) right--; } else if (sum < target) { left++; } else { right--; } } } } return result; }}Complexity
Time
O(n^3)
Space
O(log n) or O(n) for sorting, depending on the implementation. O(1) auxiliary space otherwise (not counting the output list).
Trade-offs
Pros
Much more efficient than the brute-force approach.
Passes the time limits for typical constraints.
Avoids using extra space for a
Setby handling duplicates smartly within the loops.
Cons
The implementation is more complex than the brute-force approach.
Requires careful handling of pointer movements and duplicate-skipping logic.
Solutions
Solution
public class Solution { public IList < IList < int >> FourSum(int[] nums, int target) { int n = nums.Length; var ans = new List < IList < int >> (); if (n < 4) { return ans; } Array.Sort(nums); for (int i = 0; i < n - 3; ++i) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } for (int j = i + 1; j < n - 2; ++j) { if (j > i + 1 && nums[j] == nums[j - 1]) { continue; } int k = j + 1, l = n - 1; while (k < l) { long x = (long) nums[i] + nums[j] + nums[k] + nums[l]; if (x < target) { ++k; } else if (x > target) { --l; } else { ans.Add(new List < int > { nums[i], nums[j], nums[k++], nums[l--] }); while (k < l && nums[k] == nums[k - 1]) { ++k; } while (k < l && nums[l] == nums[l + 1]) { --l; } } } } } return ans; }}class Solution { public List < List < Integer >> fourSum ( int [] nums , int target ) { int n = nums . length ; List < List < Integer >> ans = new ArrayList <>(); if ( n < 4 ) { return ans ; } Arrays . sort ( nums ); for ( int i = 0 ; i < n - 3 ; ++ i ) { if ( i > 0 && nums [ i ] == nums [ i - 1 ]) { continue ; } for ( int j = i + 1 ; j < n - 2 ; ++ j ) { if ( j > i + 1 && nums [ j ] == nums [ j - 1 ]) { continue ; } int k = j + 1 , l = n - 1 ; while ( k < l ) { long x = ( long ) nums [ i ] + nums [ j ] + nums [ k ] + nums [ l ]; if ( x < target ) { ++ k ; } else if ( x > target ) { -- l ; } else { ans . add ( List . of ( nums [ i ], nums [ j ], nums [ k ++], nums [ l --])); while ( k < l && nums [ k ] == nums [ k - 1 ]) { ++ k ; } while ( k < l && nums [ l ] == nums [ l + 1 ]) { -- l ; } } } } } return ans ; } } // // general solution, k-sum // https://leetcode.com/problems/4sum/solution/ // below kSum() divide-and-conquer idea is good, but not passing Online-Judge class Solution { public List < List < Integer >> fourSum ( int [] nums , int target ) { Arrays . sort ( nums ); return kSum ( nums , target , 0 , 4 ); } public List < List < Integer >> kSum ( int [] nums , int target , int start , int k ) { List < List < Integer >> res = new ArrayList <>(); if ( start == nums . length || nums [ start ] * k > target || target > nums [ nums . length - 1 ] * k ) return res ; if ( k == 2 ) return twoSum ( nums , target , start ); for ( int i = start ; i < nums . length ; ++ i ) if ( i == start || nums [ i - 1 ] != nums [ i ]) // 'i == start' is key, since it could be in a following recurion of [1,1,1] where start is 3rd '1' for ( List < Integer > set : kSum ( nums , target - nums [ i ], i + 1 , k - 1 )) { res . add ( new ArrayList <>( Arrays . asList ( nums [ i ]))); res . get ( res . size () - 1 ). addAll ( set ); } return res ; } public List < List < Integer >> twoSum ( int [] nums , int target , int start ) { List < List < Integer >> res = new ArrayList <>(); int lo = start , hi = nums . length - 1 ; while ( lo < hi ) { int sum = nums [ lo ] + nums [ hi ]; if ( sum < target || ( lo > start && nums [ lo ] == nums [ lo - 1 ])) ++ lo ; else if ( sum > target || ( hi < nums . length - 1 && nums [ hi ] == nums [ hi + 1 ])) -- hi ; else res . add ( Arrays . asList ( nums [ lo ++], nums [ hi --])); } return res ; } } public class Four_Sum { public static void main ( String [] args ) { Four_Sum out = new Four_Sum (); Solution s = out . new Solution (); // SolutionForLoop s= out.new SolutionForLoop(); List < List < Integer >> result = s . fourSum ( new int []{ 1 , 0 , - 1 , 0 , - 2 , 2 }, 0 ); for ( List < Integer > each : result ) { String one = "" ; for ( int e : each ) { one = one + " " + e ; } System . out . println ( one ); } } // time: O(NlogN) // space: O(1) public class Solution { public List < List < Integer >> fourSum ( int [] nums , int target ) { List < List < Integer >> list = new ArrayList <>(); if ( nums . length < 4 ) { return list ; } Arrays . sort ( nums ); // improved based on 3-sum int layer4 = 0 ; while ( layer4 < nums . length ) { // @note: below is causing me trouble when convert for to while // in while, here "layer4" is never updated for case like {0,0,0,0} // if(layer4 > 0 && nums[layer4] == nums[layer4 - 1]) continue; if ( layer4 > 0 && nums [ layer4 ] == nums [ layer4 - 1 ]) { layer4 ++; } // hold one pointer, other two pointer moving int ancher = layer4 + 1 ; while ( ancher < nums . length ) { int i = ancher + 1 ; int j = nums . length - 1 ; while ( i < j ) { int sum = nums [ layer4 ] + nums [ ancher ] + nums [ i ] + nums [ j ]; if ( sum == target ) { // @note: Arrays.asList() list . add ( Arrays . asList ( nums [ layer4 ], nums [ ancher ], nums [ i ], nums [ j ])); // @note: dont forget move pointers i ++; j --; // @note: optimization. above i,j is updated already, compare with previous position while ( i < j && nums [ i ] == nums [ i - 1 ]) { i ++; } while ( j > i && nums [ j ] == nums [ j + 1 ]) { j --; } } else if ( sum < target ) { i ++; // @note: same here, possibly updated already, note i-1 or i+1 while ( i < j && nums [ i ] == nums [ i - 1 ]) { i ++; } } else { j --; // @note: same here, possibly updated already, note i-1 or i+1 while ( j > i && j + 1 < nums . length && nums [ j ] == nums [ j + 1 ]) { j --; } } } ancher ++; // optimize for 2nd pointer while ( ancher > layer4 && ancher < nums . length && nums [ ancher ] == nums [ ancher - 1 ]) { ancher ++; } } layer4 ++; // optimize for 2nd pointer while ( layer4 < nums . length && nums [ layer4 ] == nums [ layer4 - 1 ]) { layer4 ++; } } return list ; } } }/** * @param {number[]} nums * @param {number} target * @return {number[][]} */ var fourSum = function (nums, target) { const n = nums.length; const ans = []; if (n < 4) { return ans; } nums.sort((a, b) => a - b); for (let i = 0; i < n - 3; ++i) { if (i > 0 && nums[i] === nums[i - 1]) { continue; } for (let j = i + 1; j < n - 2; ++j) { if (j > i + 1 && nums[j] === nums[j - 1]) { continue; } let [k, l] = [j + 1, n - 1]; while (k < l) { const x = nums[i] + nums[j] + nums[k] + nums[l]; if (x < target) { ++k; } else if (x > target) { --l; } else { ans.push([nums[i], nums[j], nums[k++], nums[l--]]); while (k < l && nums[k] === nums[k - 1]) { ++k; } while (k < l && nums[l] === nums[l + 1]) { --l; } } } } } return ans; };class Solution { public: vector < vector < int >> fourSum ( vector < int >& nums , int target ) { int n = nums . size (); vector < vector < int >> ans ; if ( n < 4 ) { return ans ; } sort ( nums . begin (), nums . end ()); for ( int i = 0 ; i < n - 3 ; ++ i ) { if ( i && nums [ i ] == nums [ i - 1 ]) { continue ; } for ( int j = i + 1 ; j < n - 2 ; ++ j ) { if ( j > i + 1 && nums [ j ] == nums [ j - 1 ]) { continue ; } int k = j + 1 , l = n - 1 ; while ( k < l ) { long long x = ( long long ) nums [ i ] + nums [ j ] + nums [ k ] + nums [ l ]; if ( x < target ) { ++ k ; } else if ( x > target ) { -- l ; } else { ans . push_back ({ nums [ i ], nums [ j ], nums [ k ++ ], nums [ l -- ]}); while ( k < l && nums [ k ] == nums [ k - 1 ]) { ++ k ; } while ( k < l && nums [ l ] == nums [ l + 1 ]) { -- l ; } } } } } return ans ; } };# k-sum class Solution : def fourSum ( self , nums : List [ int ], target : int ) -> List [ List [ int ]]: nums . sort () return self . kSum ( nums , target , 0 , 4 ) def kSum ( self , nums : List [ int ], target : int , start : int , k : int ) -> List [ List [ int ]]: res = [] if start == len ( nums ) or nums [ start ] * k > target or target > nums [ - 1 ] * k : return res if k == 2 : return self . twoSum ( nums , target , start ) for i in range ( start , len ( nums )): if i == start or nums [ i - 1 ] != nums [ i ]: # here is a hidden matching target==0 # if not matching target, then kSum() will return empty list for sset in self . kSum ( nums , target - nums [ i ], i + 1 , k - 1 ): # if kSum(k-1) return empty, it will not execute this line res . append ([ nums [ i ] ] + sset ) # put nums[i] in a list return res def twoSum ( self , nums : List [ int ], target : int , start : int ) -> List [ List [ int ]]: res = [] lo , hi = start , len ( nums ) - 1 while lo < hi : s = nums [ lo ] + nums [ hi ] if s < target or ( lo > start and nums [ lo ] == nums [ lo - 1 ]): lo += 1 elif s > target or ( hi < len ( nums ) - 1 and nums [ hi ] == nums [ hi + 1 ]): hi -= 1 else : res . append ([ nums [ lo ], nums [ hi ]]) # continue searching, could be multiple answers lo += 1 hi -= 1 return res ######### class Solution : def fourSum ( self , nums : List [ int ], target : int ) -> List [ List [ int ]]: n = len ( nums ) ans = [] if n < 4 : return ans nums . sort () for i in range ( n - 3 ): if i and nums [ i ] == nums [ i - 1 ]: continue for j in range ( i + 1 , n - 2 ): if j > i + 1 and nums [ j ] == nums [ j - 1 ]: continue k , l = j + 1 , n - 1 while k < l : x = nums [ i ] + nums [ j ] + nums [ k ] + nums [ l ] if x < target : k += 1 elif x > target : l -= 1 else : ans . append ([ nums [ i ], nums [ j ], nums [ k ], nums [ l ]]) k , l = k + 1 , l - 1 while k < l and nums [ k ] == nums [ k - 1 ]: k += 1 while k < l and nums [ l ] == nums [ l + 1 ]: l -= 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.