Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

3Sum challenge

Sharing is caring!

Problem statement
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = \left[-1, 0, 1, 2, -1, -4\right],

A solution set is: \left[ \left[-1, 0, 1\right], \left[-1, -1, 2\right] \right]

Solution
The idea behind the presented algorithm is to sort the array in ascending order first. Once the array is sorted we can iterate over the elements using two loops which gives us an \mathcal{O}(n^2) time complexity.

Since we need to find three elements a, b, c such that a + b + c = 0, we will use the outer iteration to fix a = nums[i]. For the rest of the elements b and c we will use an inner-loop with two pointers:
• A incrementing pointer, l, starting at i + 1
• A decrementing pointer, r, starting at len(nums)

If the sum = nums[i] + nums[l] + nums[r] is equal to 0, we have found ourselves a valid pair.If sum \textless 0 we have to increment nums[i] + nums[l] + nums[r]. We do this by increasing l (remember our array is sorted). If sum \textgreater 0 we need to decrement sum by moving r to the left.

We will also do some skipping of adjacent elements that are equal in order to avoid duplicate pairs.

Full code

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums = sorted(nums)
        
        ans = []
        for i in range(0,len(nums)-1):
            if i==0 or (nums[i-1]!=nums[i]):
                l = i + 1
                r = len(nums) - 1
                while r > l:
                    s = nums[i] + nums[l] + nums[r]
                    if s == 0:
                        ans.append([nums[i], nums[l], nums[r]])
                        l += 1
                        r -= 1

                        # Skip duplicates
                        while l nums[r] --> we need to increase l (in order to decrease |nums[i] + nums[l]| 
                        # since nums[r] would only get smaller if we were to decrease r)
                        l += 1
                    else:
                        r -= 1
        return ans

def main():
    solution = Solution()
    print(solution.threeSum([-1,0,1,2,-1,-4]))
    print(solution.threeSum([0,0,0,0]))

if __name__ == "__main__": main()