Leetcode Problem 15 3Sum.txt

15. 3Sum
Given an array nums of n integers, are there elements a, b, c in nums 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.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

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



Hint to solve: Sort the array and use two pointer algorithm for quadratic time complexity.


class Solution(object):
    
    def threeSum(self, nums):
        result = []
        if len(nums) < 3:
            return result
        
        #sort the array to use the two pointer algorithm
        #will take nlogn time
        nums.sort()
        
        for i in range(len(nums)-2):
            #i==0 will cover the case when we have exactly 3 input values
            #We don't want repeated numbers hence incrementing i until this condition is reached
            if i == 0 or nums[i-1] < nums[i]:
                start = i+1
                end = len(nums) - 1

                while start < end:
                    total = nums[i] + nums[start] + nums[end]

                    if total == 0:
                        result.append([nums[i],nums[start], nums[end]])

                    if total < 0:
                        currStart = start
                        #We don't want repeated elements in the result
                        while(nums[currStart] == nums[start] and start < end):
                            start += 1
                    else:
                        currEnd = end
                        #We don't want repeated elements in the result
                        while(nums[currEnd] == nums[end] and start < end):
                            end -= 1
                            
        return result