3Sum

Links

Go to the solution
Go to the question on LeetCode

My Thoughts

What I Learned
I learned how to apply the two-pointer algorithm in a new way and use it in a more challenging problem.

How I Can Improve
Consistently studying my algorithms and improving my ability to recognize patterns in those problems will help me improve my coding skills.

Algorithm Description

Two Pointer Algorithm - If a list is sorted and we place a pointer at the extreme values (max and min), we can iterate one pointer at a time to approach the solution.

In this problem, we use the two-pointer algorithm on the elements between our ith + 1 element and the end of the list. So our search interval for the two pointer algorithm is [i+1:len(nums)]

Visual Examples
The two-pointer algorithm being performed on a list, click to view

Solution Statistics

Time Complexity
O(n²) - We are iterating through each element in the list (n) when executing the for loop and then iterating through at worse n-2 elements during each iteration of that for loop, resulting in the O(n²) time complexity. Since our logic results in a worse time complexity than sorting the list (O(n log n)), we ignore it and go with the larger complexity.

Space Complexity
O(1) - Python’s built-in sorting has an O(1) space complexity, and we are only creating four variables that do not depend on the size of the input list, resulting in the O(1) space complexity.

Runtime Beats
81.71% of other submissions

Memory Beats
76.26% of other sumbissions

Solution

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        trip = []

        # Sorting the list allows us to use the two pointer algorithm on the remaining 
        # elements after selecting the first element
        nums.sort()
        
        for i, n in enumerate(nums):

            # To avoid duplicates and refine our time complexity, we can check these conditions
            # Essentially skipping numbers we have already checked
            if i > 0 and n == nums[i-1]:
                continue


            # Perform two sum with the target being 0
            p0,p1 = i+1, len(nums) - 1

            while p0 < p1:

                # Assign the sum to tot and check its value
                tot = nums[p0] + nums[p1] + n

                if tot > 0:
                    p1 -=1
                
                elif tot < 0:
                    p0 += 1
                
                else:
                    trip.append([n,nums[p0],nums[p1]])
                    p0 +=1

                    # Another method to avoid duplicates and refine our time complexity
                    # Essentially skipping numbers we have already checked and
                    # ensuring we properly increment to the next element
                    while nums[p0] == nums[p0-1] and p0 < p1:
                        p0 += 1

        return trip