3Sum

• Difficulty: Unknown
• Primary pattern: Arrays & Strings
• Tags: Array, Two Pointers, Sorting
• Time taken: 11:37
• LeetCode Link

Key Idea

• Brute force you traverse through the list
• Correct way is to use dynamic left and right pointers on a sorted list. If a list is sorted, when summing, use the sum to determine whether you need to go left or right, until there is no further index

Solution

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        # Sort first so we can use two pointers
        nums.sort()
        output_list = []

        # Fix one number at a time
        for i in range(len(nums) - 2):
            # Skip duplicate fixed numbers
            # Example: if nums[i] is same as nums[i - 1],
            # we already handled this starting number before
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            # Two pointers for the remaining part of the list
            left_pointer = i + 1
            right_pointer = len(nums) - 1
            while left_pointer < right_pointer:
                current_sum = nums[i] + nums[left_pointer] + nums[right_pointer]
                if current_sum == 0:
                    output_list.append([
                        nums[i],
                        nums[left_pointer],
                        nums[right_pointer]
                    ])
                    # Move both pointers after finding a valid triplet
                    left_pointer += 1
                    right_pointer -= 1
                    # Skip duplicate left values
                    while left_pointer < right_pointer and nums[left_pointer] == nums[left_pointer - 1]:
                        left_pointer += 1
                    # Skip duplicate right values
                    while left_pointer < right_pointer and nums[right_pointer] == nums[right_pointer + 1]:
                        right_pointer -= 1
                elif current_sum < 0:
                    # Sum is too small, need a bigger number
                    left_pointer += 1
                else:
                    # Sum is too large, need a smaller number
                    right_pointer -= 1
        return output_list

Complexity

• Time: O(n2)
• Space: O(1)