LeetCode 15: 3sum — Step-by-Step Visual Trace

#leetcode #python #algorithms

Medium — Two Pointers | Array | Sorting

The Problem

Find all unique triplets in an array that sum to zero. Each triplet must contain three distinct elements and no duplicate triplets should be returned.

Approach

Sort the array first, then use a fixed pointer for the first element and two pointers (left and right) to find pairs that sum to the negative of the first element. Skip duplicate values to ensure unique triplets.

Time: O(n²) · Space: O(1)

Code

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        n = len(nums)

        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left, right = i + 1, n - 1

            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]

                if current_sum == 0:
                    result.append([nums[i], nums[left], nums[right]])

                    # Skip duplicates
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1

                    left += 1
                    right -= 1
                elif current_sum < 0:
                    left += 1
                else:
                    right -= 1

        return result