100 Days to crack FAANG interview Day 5 — Three Sum

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.

Problem Statement:

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]]

Approach

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 time complexity is O(n³) as we are using 3 for-loops, making it inefficient for large inputs
• The problem statement states that the result should not contain duplicates which is not guaranteed by our initial implementation. We address the duplicates issue by checking if the triplet already exists in the result array before inserting. But this would increase the running time further.

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.

Code Implementation

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.

Optimisation

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.

Final Code

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!