__init__.py

from typing import List


def three_sum(nums: List[int]) -> List[List[int]]:
    """
    Complexity Analysis:
    We assume that n is the length of the input array

    Time Complexity: O(nlog(n)) + O(n^2) = O(n^2) the O(nlog(n)) is due to sorting, overall, the time complexity is O(n²).
    This is due to the nested loops in the algorithm. We perform n iterations of the outer loop, and each iteration
    takes O(n) time to use the two-pointer technique.

    Space Complexity: O(n²) as no extra space is taken up. We need to store all distinct triplets that sum to 0, which
    can be at most O(n²) triplets.

    Args:
        nums (list): input list of integers
    Return:
        list: list of lists of integers
    """
    result = []
    # Time Complexity: O(nlog(n)) sorting in place. This may incur space complexity of O(n) due to Python's timesort
    # using temporary storage to handle the in place sorting
    nums.sort()

    for idx, num in enumerate(nums):
        # Increment to avoid duplicates
        if idx > 0 and num == nums[idx - 1]:
            continue

        left, right = idx + 1, len(nums) - 1

        while left < right:
            total = num + nums[left] + nums[right]
            if total > 0:
                right -= 1
            elif total < 0:
                left += 1
            else:
                # add the triplet
                result.append([num, nums[left], nums[right]])

                # move the left pointer to avoid duplicates while it is still less than the right
                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

    return result


def three_number_sum(array: List[int], target_sum: int) -> List[List[int]]:
    if not array:
        return []

    # Sort the array and store the result in nums to avoid side effects to the caller of this
    # function. This incurs a a time complexity of O(n (log(n))) and a space complexity of O(n)
    # where n is the number of elements in the array
    nums = sorted(array)
    n = len(nums)
    result = []

    for idx, num in enumerate(nums):
        left = idx + 1
        right = n - 1

        while left < right:
            total = num + nums[left] + nums[right]
            if total == target_sum:
                result.append([num, nums[left], nums[right]])
                # move the left pointer to avoid duplicates while it is still less than the right
                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 total > target_sum:
                right -= 1
            else:
                left += 1

    return result