In this blog, I will be explaining one of the classical questions asked in interviews. The link to the question is here.

The given problem states that we need to find three numbers from the array which sum to zero. If we fix one number, then this problem becomes the Two Sum problem. This problem is an advancement to the Two Sum problem. I highly recommend you to solve that problem before solving this.

Let’s start with the brute force solution🤓

Brute Force Solution

For simplicity, let’s assume the three elements be a, b, and c. Then, the requirement of the problem is a + b + c = 0. Also, let us take the size of the array to be N.

The brute force solution is to traverse the array three times, in the first loop fix one element and similarly for the second and the third loop. Inside the third loop, check if the elements sum to 0.  But this takes O(N^3). Ummn, the interviewer won’t like this. Let’s try to reduce it.

HashMap Based Approach

We know there’s always a trade-off between time and space. As you have guessed, Yes we are using extra space to reduce time complexity. So let’s store all the array elements in the HashMap with key as the array element and its frequency as the value.

So, now we will fix the first element a by traversing the array once, then again we will traverse the array again and fix the second element b, we will also decrease the frequency of a and b by 1 in hashmap to avoid duplicates, now since a+b+c=0, we have to search -(a+b) in the array which takes O(1) as values are stored in hashmap but some duplicate triplets can be added to the result here, so we will store the result in a set to avoid duplicate triplets.
One catch here is if the array doesn’t contain negative elements then no such triplet exists. This gives us a complexity of O(N*Nlog(M)) where M is the size of the set.

Yeah, we finally reduced the complexity 🥳 But now be ready for the interviewer’s favorite question is, can we do better?? Let’s see!


Have you checked out our discord group? We host live sessions for coding and system design every week on the server, have study kits that are based on multiple different patterns and topics. No sign up required, just join the discord


Two pointers Based Approach

For this approach, we need to sort the array first. Now, if we fix the first element a, we are left with the Two Sum problem of finding two elements b+c whose sum equals -a. We will be using two pointers approach to finding potential b and c. Since the array is sorted, we fix low to the element next to a in the array and high to the last array element. Now there are three conditions:

  1. If high + low = -a, then we got a triplet, add it to the output array, and increment low by 1 and decrement high by 1.
  2. If high + low < -a, then we need to increment low by 1.
  3. If high + low > -a, then decrement high by 1.

Certain checks that are to be done:

  • If the array doesn’t contain negative elements then no such triplet exists.
  • Skip the duplicate elements everywhere, i.e while traversing the array, incrementing low, and decrementing high to avoid the use of the set.

Example:

The given array is

Step 1:

Step 2:

Step 3:

Step 4:

Yay! Finally, we solved it in O(N^2) 🎯 time complexity where O(N) for traversing the array, O(N) for two-pointer approach, and O(N*log(N)) for sorting. So, O(N)* O(N) + O(N*log(N)) gives O(N*N). Also, note that we haven’t used any extra space here.


Have you checked out our discord group? We host live sessions for coding and system design every week on the server, have study kits that are based on multiple different patterns and topics. No sign up required, just join the discord


Here’s the code in C++.

vector<vector<int> > threeSum(vector<int>& nums) {
    if(nums.size() <=2) return {};
    vector<vector<int> > res;
    sort(nums.begin(), nums.end());
		int n = nums.size();
    for(int i =0; i < n;){
        int low = i+1,high = n-1;

        while(low < high){
            if(nums[i]+nums[low]+nums[high] == 0){
                res.push_back({nums[i],nums[low],nums[high]});
                low++;
                high--;
                while((low < high) && nums[low] == nums[low-1]) low++;
                while((low < high) && nums[high] == nums[high+1]) high--;

            }else if(nums[i]+nums[low]+nums[high]<0){
                low++;
                while(low < high) && nums[low] == nums[low-1]) low++;
            }else{
                high--;
                while((low < high) && nums[high] == nums[high+1]) high--;
            }
        }

        i++;
        while((i < n) && nums[i] == nums[i-1])
            i++;

    }
    return res;
}