Find Unique Zero-Sum Triplets

Given an integer array, return every distinct triplet of values whose sum is zero. Each triplet must use three different array indices. Return duplicate value-triplets only once. Implement `three_sum(nums: int[]) -> int[][]`. ### Constraints & Assumptions - `0 <= len(nums) <= 3000`; values range from -1,000,000 through 1,000,000. - Sort values within each returned triplet in ascending order. Sort the outer list lexicographically to make the output deterministic. - Equal values may be used when they come from different indices. For example, three zeros require at least three zero elements. - You may reorder the input or sort a copy. Return values, not indices. ### Examples ```text nums = [-1,0,1,2,-1,-4] result = [[-1,-1,2],[-1,0,1]] ``` ```text nums = [0,0,0,0] result = [[0,0,0]] ``` Explain how the algorithm avoids reusing an index and suppresses duplicate triplets. Give its time and auxiliary-space complexity, distinguishing output storage and any sorted copy from the search state. ```hint Make the remaining sum monotone After fixing one value in sorted order, consider how moving either endpoint of the remaining search interval changes the pair sum. ```