three_sum.py

from typing import List


class Solution:
    """LeetCode #15 - 3Sum (Medium)
    https://leetcode.com/problems/3sum/

    Return all *unique* triplets [nums[i], nums[j], nums[k]] with distinct
    indices that sum to zero. The tricky part is not finding triplets - it is
    not reporting the same triplet twice.
    """

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        """Sort first, then reduce every step to Two Sum II on the remainder.

        Key insight: fix one number `nums[i]`; the other two must add up to
        -nums[i]. On a sorted array that inner search is the O(n) two-pointer
        scan from #167, so the whole thing costs O(n^2) instead of O(n^3).

        Sorting also makes deduplication easy: equal values sit next to each
        other, so "skip a value identical to the previous one" is enough to
        guarantee unique triplets - no set of tuples needed.

        Time:  O(n^2)     - O(n log n) sort + n iterations of an O(n) scan.
        Space: O(1) extra - ignoring the output and the sort's internals.
        """
        nums.sort()
        n = len(nums)
        result = []

        for i in range(n - 2):
            # Array is sorted: once the smallest of the three is positive,
            # every remaining triplet is positive too.
            if nums[i] > 0:
                break
            # Skip a repeated anchor - it would rebuild the same triplets.
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left, right = i + 1, n - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]

                if total < 0:
                    left += 1                  # too small -> need a bigger value
                elif total > 0:
                    right -= 1                 # too big -> need a smaller value
                else:
                    result.append([nums[i], nums[left], nums[right]])
                    left += 1
                    # Move past duplicates of the value we just used, otherwise
                    # the next iteration would record the identical triplet.
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1

        return result