3 Sum | Leetcode #15 | 100 Days of Code Day 10

Today we are going to solve 3 Sum – our first Medium Level Array problem from Coderefer DSA Sheet. If you are new to this blog, here’s the link for the same:

https://www.coderefer.com/blog/coderefer-dsa-sheet/

Problem Statement

Now let us understand the problem statement. You can read from the below link but here’s the brief: Given an Integer Array, you need to find all the triplets with different indices but if added should return zero.

https://leetcode.com/problems/3sum/description/

Solution

Now let us understand the solution. Here we need to keep two things in mind.

1. Can we convert 3 Sum to 2 Sum? We know that nums[i] + nums[j] + nums[k] should be 0. But what if we take one value to the right of (=)? This becomes nums[i] + nums[j] = -nums[k]. If you closely look, it becomes a 2 Sum problem where the sum of 2 numbers must be equal to a target number (here it is -nums[k]). Hence we were able to convert 3 sum to 2 sum
2. To avoid duplicate triplets. This can be done by skipping the processing of duplicate values. How can we do this? By sorting the array to make the duplicate values fall adjacent so that we can skip after processing first among them.

Now by keeping these two things in mind, let us solve the code. The code is commented wherever necessary. If you feel stuck anywhere, feel free to comment below so I can guide you.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> sol = new ArrayList<>();
        // To sort the values as we will consider skipping them if same, to avoid duplicates
        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]) {
                // comparing with previous. If both are same, 
                // then skip to avoid duplicate triplets
                continue;
            }
            Set<Integer> set = new HashSet<>(); // set because it can retreive in O(1)
            int target = -nums[i];
            for(int j = i+1; j < nums.length; j++) {
                int rem = target - nums[j];
                if(set.contains(rem)) { // here we are retrieving from set in O(1)
                    // we found our triplet. Hence adding to the sol
                    sol.add(Arrays.asList(nums[i], nums[j], rem));
                    if(j< nums.length-1 && nums[j] == nums[j+1]) {
                        // skipping duplicate values while considering for triplets
                        j++;
                    }
                } else {
                    set.add(nums[j]);
                }
            }
        }
        return sol;
    }
}

Time & Space Complexities

Here the time complexity is O(N^2) as we are iterating through the array twice using nested for loops.

Space complexity of using HashSet is O(N) and List of List is O(N^2). Hence the total Space Complexity is O(N) + O(N^2) ~= O(N^2).