Welcome to Day 5 of my FAANG interview preparation journey! This is a medium-level problem. If you haven’t solved Two Sum (https://leetcode.com/problems/two-sum/) I recommend to try it first before attempting Three Sum.
Three Sum — https://leetcode.com/problems/3sum/
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example :
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
The brute-force approach is quite straightforward. Use 3 nested loops, and consider all triplets of the input array. If the sum of the triplets is 0, add it to the result list.
List<List<Integer>> result = new ArrayList<>();
for(int i=0; i< nums.length-2; i++) {
for(int j=i+1; j< nums.length-1; j++) {
for(int k=j+1; k<nums.length; k++) {
if(nums[i] + nums[j] + nums[k] == 0) {
result.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k])));
}
}
}
}
There are 2 issues with the above approach.
The way to improve the time complexity is to consider fewer triplets. One way to achieve this is by sorting the input array. And then, during the iteration through array, if the sum of the triplets exceeds 0, there is no need to consider the remaining elements in the loop. This check can be added in each for-loop.
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for(int i=0; i< nums.length-2; i++) {
if(nums[i] > 0) break;
for(int j=i+1; j< nums.length-1; j++) {
if(nums[i] + nums[j] > 0) break;
for(int k=j+1; k<nums.length; k++) {
if(nums[i] + nums[j] + nums[k] > 0) break;
if(nums[i] + nums[j] + nums[k] == 0) {
result.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k])));
}
}
}
}
This optimisation reduces the number of triplets we consider but the time complexity is still O(n³). For example, if the input array contains all negative numbers, we’d still need to consider all the triplets.
To address the duplicates issue, we just have to compare the newly generated triplet with the previously added triplet. Since the input array is sorted, the triplets will also be in sorted order. Therefore, we only need to compare the new triplet with only the last added triplet instead of all the existing triplets.
List<List<Integer>> result = new ArrayList<>();
List<Integer> prev = new ArrayList<>();
Arrays.sort(nums);
for(int i=0; i< nums.length-2; i++) {
if(nums[i] > 0) break;
if(i > 0 && nums[i] == nums[i-1]) continue; // adding nums[i] == nums[i-1] condition here to avoid duplicates
for(int j=i+1; j< nums.length-1; j++) {
if(nums[i] + nums[j] > 0) break;
for(int k=j+1; k<nums.length; k++) {
if(nums[i] + nums[j] + nums[k] > 0) break;
if(nums[i] + nums[j] + nums[k] == 0) {
//saving previously added triplet to avoid duplicates
if(prev.size() > 0 && prev.get(0) == nums[i] && prev.get(1) == nums[j]) continue;
prev = new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k]));
result.add(prev);
}
}
}
}
The code failed on submission due to “Time Limit Exceeded” error.
For a particular pair of indices (i,j) we don’t have to iterate through the entire array to find a triplet. Instead, we just need to check if -1 * (nums[i] + nums[j]) exists in the array. This can be achieved by storing the input integers in an HashMap. With this approach, the time complexity improves from O(n³) to O(n²) as we need only 2 nested for-loops. However, it increases the space complexity to O(n) to save the extra HashMap.
Additional check hm.get(-1 * (nums[i] + nums[j])) <= j is required to avoid getting the same element from the hashmap.
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> prev = new ArrayList<>();
HashMap<Integer, Integer> hm = new HashMap<>();
Arrays.sort(nums);
for(int i=0; i< nums.length; i++) {
hm.put(nums[i], i);
}
System.out.println(Arrays.toString(nums));
for(int i=0; i< nums.length-2; i++) {
if(nums[i] > 0) break;
if(i > 0 && nums[i] == nums[i-1]) continue;
for(int j=i+1; j< nums.length-1; j++) {
if(nums[i] + nums[j] > 0) break;
if(!hm.containsKey(-1 * (nums[i] + nums[j])) || hm.get(-1 * (nums[i] + nums[j])) <= j ) continue;
if(prev.size() > 0 && prev.get(0) == nums[i] && prev.get(1) == nums[j]) continue;
prev = new ArrayList<>(Arrays.asList(nums[i], nums[j], -1 * (nums[i] + nums[j])));
result.add(prev);
}
}
return result;
}
There is an alternate two-pointer approach which would further optimise without the need for an additional HashMap. Try implementing the solution using that approach.
Thanks for reading and any feedback is appreciated!
Visit https://100daysofcode.io/ for more content and resources to support your coding journey!
Blog|Youtube|Careers|Contact Us
Have Feedback or want to contribute? Email: hello[@]100DaysOfCode.io
100DaysOfCode@2024