class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        '''
        Classic example of over engineering 😑.
            
        - Time complexity: `nlog(n) + nk - k^2 : O( n^2 )`.
        Where, `n` and `k` are total number of integers and negative integers respectively in given array, and `0 <= k <= n`.

        - Space complexity: `O( log(n) )`.
        Assuming, output array is not considered.
        '''
        nums.sort()
        mid = bisect.bisect_left(nums, 0)
        end = bisect.bisect_right(nums, -1*min(nums[0]+nums[1],nums[0]))-1
        output = []
        for end in range(end, mid-1, -1):
            if end < len(nums)-1 and nums[end+1] == nums[end]:
                continue
            start = bisect.bisect_left(nums, -nums[end] -nums[end-1])
            while start < mid:
                target = -nums[end] - nums[start]
                if target < nums[start]:
                    break
                if nums[bisect.bisect_right(nums, target, start+2, end)-1] == target:
                    output.append( [nums[start], target, nums[end]] )
                while start < mid and nums[start] == nums[start+1]:
                    start+=1
                start += 1
        if mid < len(nums)-2 and nums[mid+2] == 0:
            output.append([0,0,0])
        return output

class Solution:
    '''
    Time Complexity: O(n^2)
    Space Complexity: O(n^2)
    Where n is the length of nums. The n^2 is the set, live alongside the list it builds:
    223.0 MB peak against 99.5 MB for the duplicate skipping version at n=3000.
    Pitfalls: bisect.bisect is bisect_right, so m counts elements <= 0 and range(m) stops one past the last of them. An earlier draft had m+1 to be safe, which let i reach n, harmless only because nums[i] is read inside a while that is already false there. Hoist nums[i] out of the inner loop and it dies with IndexError on [-3,-2,-1].

    [two-pointer-both-ends] with the mirror loop deleted and the bound added, so the 14m 38s
    belongs to that attempt. A triplet's smallest element cannot be positive, so i stops at the
    last non-positive, 0.285s to 0.019s on all-positive n=3000. One line, if nums[i] > 0: break,
    measures identical.

    Still owed is the duplicate skipping the set stands in for, already written in Java here.
    [sort-two-pointer] skips i on nums[i-1] == nums[i] and walks left past its repeats with no
    set, 0.113s to 0.007s at n=3000 from +-100. The right end bound is the other, and
    [sort-binary-search] already does it. Brute force clean over 5000 random arrays plus all
    negative, positive, zero and single zero inputs, worst case 0.435s at n=3000.
    '''
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        n = len(nums)
        m = bisect.bisect(nums, 0)
        output = set()

        for i in range(m):
            l = i+1
            r = n-1
            while l<r:
                val = nums[i] + nums[l] + nums[r]
                if val == 0:
                    output.add((nums[i], nums[l], nums[r]))
                    l += 1
                    r -= 1
                elif val > 0:
                    r -= 1
                else:
                    l += 1

        return [list(x) for x in output]

public List<List<Integer>> threeSum(int[] nums) {
    int len = nums.length;
    Arrays.sort(nums);
    List<List<Integer>> out = new ArrayList<>();

    for (int i=0; i<len; i++) {
        if (i > 0 && nums[i-1] == nums[i]) { continue; }
        int left = i+1;
        int right = len-1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if ( sum == 0 ) {
                out.add(Arrays.asList(nums[i], nums[left], nums[right]));
                left++;
                while (left <= right && nums[left-1] == nums[left]) {
                    left++;
                }
            } else if (sum > 0) {
                right--;
            } else {
                left++;
            }
        }
    }
    return out;
}

class Solution:
    '''
    Time Complexity: O(n^2)
    Space Complexity: O(n^2)
    Where n is the length of nums. Optimal bounds, paid twice.
    Pitfalls: The second loop is dead code and the set is what hides it, swap it for a list and the duplicates print. The first loop alone matches brute force over 3000 random arrays and every n=3000 stress case, in half the time.
    Do not use in interview: Sorted, every triplet has one smallest element, so fixing each index as the smallest and scanning the suffix reaches all of them once. The mirror loop is written in place of that argument, and on 3Sum the argument is the problem. Use [sort-two-pointer] instead.

    Solved unaided in 14m 38s. Correct O(n^2) fast then optimise, which was the right plan. Ran
    it in my head with no dry run though, so the belief that one left to right loop would miss
    triplets never got tested and the mirror loop went in to cover for it.
    '''
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        output = set()
        n = len(nums)

        for i in range(n):
            l = i+1
            r = n-1
            while l<r:
                val = nums[i] + nums[l] + nums[r]
                if val == 0:
                    output.add((nums[i], nums[l], nums[r]))
                    l += 1
                    r -= 1
                elif val > 0:
                    r -= 1
                else:
                    l += 1

        for i in range(n-1,-1,-1):
            r = i-1
            l = 0
            while l<r:
                val = nums[i] + nums[l] + nums[r]
                if val == 0:
                    output.add((nums[l], nums[r], nums[i]))
                    l += 1
                    r -= 1
                elif val > 0:
                    r -= 1
                else:
                    l += 1

        return [list(x) for x in output]