[Google Interview] The 3 Sum Problem

Company Tags: Google, Adobe, Amazon, Apple, Bloomberg, Facebook, Oracle, Microsoft, Tesla

Problem Statement

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.

Note: that the solution set must not contain duplicate triplets.

Constraints:

1. 0 <= nums.length <= 3000
2. -105 <= nums[i] <= 105

Examples

Let’s have a look at some examples to improve our understanding of this problem.

Naïve Approach: Brute Force Algorithm

Approach: The simplest approach would be to use nested for loop. For this, we will traverse the array for each number. If we find the unique triplets that satisfy the conditions: nums[i] + nums[j] + nums[k] == 0, i != j, i != k, and j != k, then we can append the numbers into the list. Further, we will use the set to remove the duplicate triplets.

Now, let’s look at the code:

Solution:

def three_sum(nums):
    sets = []
    lst = []
    for i in range(0, len(nums)):
        for j in range(0, len(nums)):
            for k in range(0, len(nums)):
                if nums[i] + nums[j] + nums[k] == 0 and i != j and i != k and j != k:
                    lst = sorted([nums[i], nums[j], nums[k]])
                    if lst not in sets:
                        sets.append(sorted([nums[i], nums[j], nums[k]]))
    return sets

Test case Analysis: Let’s execute this code on our examples to check if it runs:

Yeah! It passed all the test cases.

Complexity Analysis: In this method, we have considered every number three times by using nested for loops. This means we have to traverse the list thrice which accounts for the time complexity of O(n^3).

Discussion: Though this approach is quite straightforward, it is a very slow solution in terms of time complexity and won’t be the best approach when it comes to answering this question in your interviews. Nevertheless, it is a good start that paves the way for us to reach the optimal solution.

Two Pointer Approach [An Efficient Solution]

Approach: This approach is more efficient as compared to the brute force solution. The idea here is that, as you have to find unique triplets such that nums[i] + nums[j] + nums[k] == 0, re-arranging them would mean nums[j] + nums[k] = – nums[i]. We, will use this to our advantage and proceed with our algorithm such that: 

We first, sort the given list and then work upon the sorted list using two pointers that point at the start and end elements of the list. Here, we can have three conditions:

1. nums[j] + nums[k] > - nums[i]. In this case we have to shift the end pointer towards the left.
2. nums[j] + nums[k] < - nums[i]. In this case we have to shift the start pointer towards right.
3. nums[j] + nums[k] = - nums[i]. In this case we found a triplet. Hence, we store this value and move the pointer accordingly to search for more triplets if any.

Note: sort() is a built-in method in Python that sorts a given list in ascending order by default.

The following diagram will help you to understand the approach mentioned above. Make a clear note of how the pointers shift accordingly based on the three conditions mentioned above and then the triplets get stored within the resultant list.

Solution:

def three_sum(nums):
    lst=[]
    nums.sort()
    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
 
        j = i + 1
        k = len(nums) - 1
 
        test_sum  = 0 - nums[i]
 
        while j < k:
            sum = nums[j] + nums[k]
 
            if sum < test_sum:
                j += 1
            elif sum > test_sum:
                k -= 1
            else:
                lst.append([nums[i], nums[j], nums[k]])
                j += 1
                while j < k and nums[j] == nums[j - 1]:
                    j += 1
 
    return lst

Test case Analysis: Let’s execute this code on our examples to check if it runs:

Yeah! It passed all the test cases.

Complexity Analysis: In this method, to get the value of nums[i] we use one loop that takes O(n) time. Further, inside that loop to get the value of sum nums[j] + nums[k] we used the two pointer approach that takes O(n) time. Hence, we have to undergo a nested loop which leads to a time complexity is O(n^2).

Bonus: Using Counters

It is never a bad idea to impress the interview panel with something extra from your bag of tricks. Hence, we will now have a look at another approach that is equally efficient if not more as the one we saw before. However, in this approach you need the help of the collections and bisect module in Python. Feel free to skip this if you are not very comfortable with it, however if you are able to understand the working principle of these modules then this method is well suited for you to solve this question.

Approach: The basic idea of this approach is to create all unique pairs possible and further find which of these pair’s compliments (negatives) are also present. Thus, in this approach, you have to first import the collections module and couple of funtions rom the bisect module into your program by using the following code:

Here, too we will check for one num and check if the sum exists for that pair. But instead of using two pointers, we will use a counter. The three cases that occur are:

1. If all the three numbers are the same then the only possible solution remains [0, 0, 0]
2. If two among the three numbers are the same,  we would have to check the counter and append them.
3. If all three numbers are different, then we will use the bisect method. 

Finally, for every value of our counter variable, we will append it in the list after checking whether it’s unique. Finally, return that list.

Note: We already discussed a quick recap of the bisect module in Python in the following interview question: [Interview Question] How To Search The Insert Position Of Target In A Sorted Array? Please, feel free to have a look at this if you need a quick refresher about the bisect module.

Let’s look at the code:-

Solution:

import collections
from bisect import bisect_left, bisect_right
def three_sum(nums):
    c = collections.Counter(nums)
    nums = sorted(c)
    lst = []
    for i, num in enumerate(nums):
        if num == 0:
            if c[num] > 2:
                lst.append([0, 0, 0])
        
        elif c[num] > 1 and -2 * num in c:
            lst.append([num, num, -2 * num])
            
        if num < 0:
            neg = -num
            left = bisect_left(nums, neg - nums[-1], i + 1)
            right = bisect_right(nums, neg / 2, left)
            for a in nums[left:right]:
                b = neg - a
                if b in c and a!=b:
                    lst.append([num, a, b])
    return lst

Test case Analysis: 

Let’s execute this code on our examples to check if it runs:

Yeah! It passed all the test cases.

Complexity Analysis: The time complexity of this method is O(n^2) as initializing a counter takes O(n) time and then to distinct it, it takes up O(n) time.

Conclusion

I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.

Recommended: Finxter Computer Science Academy

• One of the most sought-after skills on Fiverr and Upwork is web scraping. Make no mistake: extracting data programmatically from websites is a critical life skill in today’s world that’s shaped by the web and remote work.
• So, do you want to master the art of web scraping using Python’s BeautifulSoup?
• If the answer is yes – this course will take you from beginner to expert in Web Scraping.