4Sum
MedPrompt
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.
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; }}Video 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.