Day 17: 3Sum: Two Pointers - leetcode - Python3

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.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

SOLUTION

class Solution:

    def threeSum(self, nums: List[int]) -> List[List[int]]:

        result: List[List[int]]= []

        nums.sort()

        for i, a in enumerate(nums):

            if i > 0 and a == nums[i-1]:

                continue

           

            l, r = i+1, len(nums)-1

            while l < r:

                sum: int= a + nums[l] + nums[r]

                if sum > 0:

                    r -=1

                elif sum <0:

                    l +=1

                else:

                    result.append([a,nums[l],nums[r]])

                    l += 1

                    while nums[l] == nums[l-1] and l < r:

                        l += 1

        return result

Time Complexity: O(n^2)

Space Complexity:O(n)

How it works:

• nums.sort(): This line sorts the list of integers.
• for i, a in enumerate(nums):: This loop iterates over the sorted list of integers.
• if i > 0 and a == nums[i-1]:: This condition checks if the current integer is the same as the previous integer. If it is, the function skips the current integer.
• l, r = i+1, len(nums)-1: This line sets the left and right pointers to the current integer and the end of the list, respectively.
• while l < r:: This loop iterates while the left pointer is less than the right pointer.
• sum: int= a + nums[l] + nums[r]:: This line calculates the sum of the three integers.
• if sum > 0:: This condition checks if the sum is greater than zero. If it is, the right pointer is decreased.
• elif sum <0:: This condition checks if the sum is less than zero. If it is, the left pointer is increased.
• else:: This block of code is executed if the sum is equal to zero.
• result.append([a,nums[l],nums[r]]):: This line adds the three integers to the list of results.
• l += 1:: This line increases the left pointer by one.
• while nums[l] == nums[l-1] and l < r:: This loop iterates while the current integer is the same as the previous integer and the left pointer is less than the right pointer.
• l += 1:: This line increases the left pointer by one.
• return result:: This line returns the list of results.