LeetCode: Two Pointers

    def move_zeros(nums: list[int]) -> None:
        # `last_non_zero_found_at` tracks the position where the next non-zero
        # element should be placed, simulating a second pointer.
        last_non_zero_found_at = 0

        for current in range(len(nums)):
            if nums[current] != 0:
                nums[last_non_zero_found_at], nums[current] = nums[current], nums[last_non_zero_found_at]
                last_non_zero_found_at += 1

    # arr = [0, 1, 0, 3, 12] 
    # move_zeros(arr)  Output: [1, 3, 12, 0, 0]

    def is_palindrome(s: str) -> bool:
        left, right = 0, len(s) - 1
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    # Example:
    print(is_palindrome("radar"))  # Output: True
    print(is_palindrome("hello"))  # Output: False

    def longest_unique_substring(s: str) -> int:
        char_set = set()
        left = 0
        maxLength = 0

        for right in range(len(s)):
            while s[right] in char_set:
                char_set.remove(s[left])
                left += 1
            char_set.add(s[right])
            maxLength = max(maxLength, right - left + 1)
        
        return maxLength

    # Example:
    print(longest_unique_substring("abcabcbb"))  # Output: 3

    class ListNode:
        def __init__(self, value=0, next=None):
            self.value = value
            self.next = next

    def has_cycle(head: ListNode) -> bool:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

    # Example:
    # Construct a list with a cycle: 1 -> 2 -> 3 -> 4 -> 2 (cycle)
    node1 = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    node4 = ListNode(4)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node2
    print(has_cycle(node1))  # Output: True

    def move_zeros(nums):
        left, right = 0, 0
        while right < len(nums):
            if nums[right] != 0:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
            right += 1
        return nums

    # Example:
    print(move_zeros([0, 1, 0, 3, 12]))  # Output: [1, 3, 12, 0, 0]

    def merge_sorted_arrays(arr1, arr2):
        result = []
        i, j = 0, 0

        while i < len(arr1) and j < len(arr2):
            if arr1[i] < arr2[j]:
                result.append(arr1[i])
                i += 1
            else:
                result.append(arr2[j])
                j += 1
        
        result.extend(arr1[i:])
        result.extend(arr2[j:])
        return result

    # Example:
    print(merge_sorted_arrays([1, 3, 5], [2, 4, 6]))  # Output: [1, 2, 3, 4, 5, 6]

    def threeSum(nums):
        nums.sort()  # Step 1: Sort the array
        result = []

        for i in range(len(nums)):
            # Avoid duplicates for the first element
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            # Two-pointer approach
            left, right = i + 1, len(nums) - 1
            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]
                if current_sum == 0:
                    result.append([nums[i], nums[left], nums[right]])

                    # Move pointers and avoid duplicates
                    left += 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    right -= 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

                elif current_sum < 0:
                    left += 1  # Increase sum by moving left pointer rightward
                else:
                    right -= 1  # Decrease sum by moving right pointer leftward

        return result

    # Example usage:
    nums = [-1, 0, 1, 2, -1, -4]
    print(threeSum(nums))  # Output: [[-1, -1, 2], [-1, 0, 1]]

    def longestPalindrome(s: str) -> str:
        # Preprocess the string to handle even-length palindromes
        t = "#".join(f"^{s}$")
        n = len(t)
        p = [0] * n
        center = right = 0

        
        for i in range(1, n - 1):
            mirror = 2 * center - i  # Mirror of `i` with respect to `center`

            # If within bounds of the current right boundary
            if i < right:
                p[i] = min(right - i, p[mirror])

            # Expand around `i`
            while t[i + p[i] + 1] == t[i - p[i] - 1]:
                p[i] += 1

            # Update the center and right boundary if the palindrome is expanded
            if i + p[i] > right:
                center = i
                right = i + p[i]

        # Find the maximum length palindrome
        maxLen, centerIndex = max((n, i) for i, n in enumerate(p))
        start = (centerIndex - maxLen) // 2  # Convert index back to original string
        return s[start: start + maxLen]

    def isPalindrome(self, s: str) -> bool:

        # space complexity: list to store cleaned string of n length O(n)
        cleaned = []

        # simple way for alphaNum check
        def alphaNum(c):
            return (ord('A') <= ord(c) <= ord('Z') or 
                    ord('a') <= ord(c) <= ord('z') or 
                    ord('0') <= ord(c) <= ord('9'))

        # time complexity: iterate over string of n length O(n)
        for c in s:

            if alphaNum(c):
                if 'A' <= c <= 'Z':
                    cleaned.append(chr(ord(c) + 32))
                else:
                    cleaned.append(c)

        # time complexity: two pointer iteration of string of n length O(n)
        n = len(cleaned)
        for i in range(n // 2):
            if cleaned[i] != cleaned[n - i - 1]:
                return False

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return True

    def isPalindrome(self, s: str) -> bool:
        
        # space complexity: cleaned version string of n length O(n)
        cleaned = []

        # isAlphaNum check using ord()
        def isAlphaNum(c):
            return (ord('A') <= ord(c) <= ord('Z') or 
                    ord('a') <= ord(c) <= ord('z') or 
                    ord('0') <= ord(c) <= ord('9'))

        def isUpper(c):
            return ord('A') <= ord(c) <= ord('Z')

        def toLower(c):
            return chr(ord(c) + 32)

        # time complexity: iterate over string of n length O(n)
        for c in s:

            # skip until isAlphaNum char
            if isAlphaNum(c):
                
                # Convert to lowercase char
                if isUpper(c):
                    cleaned.append(toLower(c))
                else:
                    cleaned.append(c)

        # clean is now lowercase alphaNum
        # compare using left and right pointers
        # time complexity: iterate over list of n length O(n)
        left, right = 0, len(cleaned) - 1
        while left < right:
            if cleaned[left] != cleaned[right]:
                return False
            left += 1
            right -= 1

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return True

    def isPalindrome(self, s: str) -> bool:
        # space complexity: no additional space used for storage O(1)
        left, right = 0, len(s) - 1

        # isAlphaNum check using ord()
        def isAlphaNum(c):
            return (ord('A') <= ord(c) <= ord('Z') or 
                    ord('a') <= ord(c) <= ord('z') or 
                    ord('0') <= ord(c) <= ord('9'))

        def isUpper(c):
            return ord('A') <= ord(c) <= ord('Z')

        def toLower(c):
            return chr(ord(c) + 32)

        # time complexity: iteration over string of n length O(n)
        while left < right:
            
            # time complexity: move left and right to isAlphaNum char O(n)
            while left < right and not isAlphaNum(s[left]):
                left += 1
            while left < right and not isAlphaNum(s[right]):
                right -= 1

            # Convert left and right to lowercase char
            leftChar = s[left]
            rightChar = s[right]

            if isUpper(leftChar):
                leftChar = toLower(leftChar)
            if isUpper(rightChar):
                rightChar = toLower(rightChar)

            # Compare left and right char
            if leftChar != rightChar:
                return False

            # move pointers
            left += 1
            right -= 1

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return True

    def decode(self, encoded: str) -> List[str]:

        # space complexity: list of n strings O(n) each of n length O(n), leading to O(n^2)
        decoded = []
        left = 0

        # time complexity: iterate over representation of n strings O(n) each of n length O(n), leading to O(n^2)
        while left < len(encoded):

            # grab length prefix behind "#" delimiter
            right = left
            while encoded[right] != "#":
                right += 1

            # splicing the length of the string
            # INCORRECT: 
            # length is a string, cannot use it to index or add
            # need to use int()
            length = encoded[left:right]

            # skip delimiter, point to start of string
            right += 1

            # splicing the string of 'length' characters
            # time complexity: splice over string n length O(n) for n iterations O(n), leading to O(n^2)
            decoded.append(encoded[right:right + length])

            # skip string, point to start of next len
            left = right + length

        # overall: time complexity O(n^2)
        # overall: space complexity O(n^2)
        return decoded

    def encode(self, strs: List[str]) -> str:

        # Note: python strings are immutable so concatenation with += "" 
        # python creates new string time complexity o(n^2)
        # python list .append() modifies list in place by adding a single
        # element at end in O(1) operation
        # so doing .append() with a "".join() at the end is more efficient  

        # space complexity: for n strings O(n) store n characters O(n), leading to O(n^2)
        encoded = []

        # time complexity: iterate over list of n strings O(n)
        for s in strs:
            
            # lenDelim = len + delim
            lenDelim = str(len(s)) + "#"

            # append length and delimiter "5#"
            left = 0
            while left < len(lenDelim):
                encoded.append(lenDelim[left])
                left += 1
            
            # append string itself
            # time complexity: iterate over string of n length O(n), for n iterations, leading to O(n^2)
            left = 0
            while left < len(s):
                encoded.append(s[left])
                left += 1
        
        # overall: time complexity O(n^2)
        # overall: space complexity O(n^2)
        return ''.join(encoded)


    def decode(self, encoded: str) -> List[str]:

        # space complexity: list of n strings O(n) each of n length O(n), leading to O(n^2)
        decoded = []
        left = 0

        # time complexity: iterate over representation of n strings O(n) each of n length O(n), leading to O(n^2)
        while left < len(encoded):

            # grab length prefix behind "#" delimiter
            right = left
            while encoded[right] != "#":
                right += 1

            # splicing the length of the string
            length = int(encoded[left:right])

            # skip delimiter, point to start of string
            right += 1

            # splicing the string of 'length' characters
            # time complexity: splice over string n length O(n) for n iterations O(n), leading to O(n^2)
            decoded.append(encoded[right:right + length])

            # skip string, point to start of next len
            left = right + length

        # overall: time complexity O(n^2)
        # overall: space complexity O(n^2)
        return decoded

    def encode(self, strs: List[str]) -> str:

        # Note: python strings are immutable so concatenation with += "" 
        # python creates new string time complexity o(n^2)
        # python list .append() modifies list in place by adding a single
        # element at end in O(1) operation
        # so doing .append() with a "".join() at the end is more efficient  

        # space complexity: for n strings O(n) store n characters O(n), leading to O(n^2)
        encoded = []

        # time complexity: iterate over list of strings n length O(n)
        for s in strs:
            
            # lenDelim = len + delim
            lenDelim = str(len(s)) + "#"

            # append length and delimiter "5#"
            left = 0
            while left < len(lenDelim):
                encoded.append(lenDelim[left])
                left += 1
            
            # append string itself
            # time complexity: iterate over string of n length O(n), for n iterations, leading to O(n^2)
            left = 0
            while left < len(s):
                encoded.append(s[left])
                left += 1
        
        # overall: time complexity O(n^2)
        # overall: space complexity O(n^2)
        return ''.join(encoded)


    def decode(self, encoded: str) -> List[str]:

        # space complexity: list of n strings O(n) each of n length O(n), leading to O(n^2)
        decoded = []
        left = 0

        # time complexity: iterate over representation of n strings O(n) each of n length O(n), leading to O(n^2)
        while left < len(encoded):

            # grab length prefix behind "#" delimiter
            currLen = 0
            while encoded[left] != "#":

                # grabbing value while calculating base 10 of prev
                currLen = currLen * 10 + int(encoded[left]) 
                left += 1

            # skip delimiter, point to start of string
            left += 1  

            # extract substring of 'currLen' characters
            # time complexity: iterate over string n length O(n) for n iterations O(n), leading to O(n^2)
            substring = []
            for _ in range(currLen):

                # forming string
                substring.append(encoded[left])
                left += 1
            
            # left is pointing to start of next len

            # add string to decoded list of strings
            decoded.append(''.join(substring))


        # overall: time complexity O(n^2)
        # overall: space complexity O(n^2)
        return decoded

    def twoSumII(self, numbers: List[int], target: int) -> List[int]:

        # time complexity: iteration of O(n)
        for i in range(len(numbers)): 

            # time complexity: iteration of O(n^2)
            for j in range(i + 1, len(numbers)): 

                # time complexity: sum and comparison operations take constant O(1)
                if numbers[i] + numbers[j] == target:
                    return [i + 1, j + 1]  # Convert to 1-indexed

        # overall: time complexity O(n^2)
        # overall: space complexity O(1)
        return []

    def twoSumII(self, numbers: List[int], target: int) -> List[int]:
        
        # time complexity: iteration over list of n length O(n)
        for i in range(len(numbers)): 

            # search for complement
            currComplementSearch = target - numbers[i]
            
            # Set up BinarySearch
            # set new left boundary for iteration BinarySearch
            # reset right boundary for iteration BinarySearch
            # given constraint index1 < index2
            # BinarySearch on right section of array after left element
            # time complexity: binarySearch O(log n) for each iteration O(n), leading to O(n log n)
            left, right = i + 1, len(numbers) - 1
            
            # BinarySearch
            # "<=": working within subarray [i+1, j] separate from i, 
            # so must evaluate num at left == right, as might be currComplementSearch
            # Base Case: no more array remaining to search
            # complement for numbers[i] was not found, continue iteration
            while left <= right:
                
                # middle element
                midIndex = (left + right) // 2
                midNum = numbers[midIndex]

                # found target complement
                if midNum == currComplementSearch:
                    # convert to 1-indexed array, per input/output example
                    return [i + 1, midIndex + 1]  

                # "BinarySearch" on relevant subsection
                # update left or right pointer
                elif midNum < currComplementSearch:
                    left = midIndex + 1
                else:
                    right = midIndex - 1

        # overall: time complexity O(n log n)
        # overall: space complexity O(1)
        return []

    def twoSumII(self, numbers: List[int], target: int) -> List[int]:

        # Set up BinarySearch Modification
        # initialize outer pointers
        # space complexity: left and right pointers constant O(1)
        left, right = 0, len(numbers) - 1  

        # BinarySearch Modification
        # "<": working within subarray containing left and right
        # cannot evaluate num at left == right, breaks constraints of index1 < index2
        # Base Case: no more array remaining to search, 
        # return []
        # time complexity: iterate over list of n length O(n)
        while left < right:

            # grab current sum
            currSum = numbers[left] + numbers[right]  

            # found target sum
            if currSum == target:
                # convert to 1-indexed array, per input/output example
                return [left + 1, right + 1]

            # "BinarySearch" on relevant subsection
            # update left or right pointer
            elif currSum < target:
                left += 1
            else:
                right -= 1

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return []

    def threeSum(self, nums: List[int]) -> List[List[int]]:

        # space complexity: set of unique m triplets tuples O(m)
        res = set() 
        n = len(nums)

        # time complexity: n choose three for all triplet combinations / three nested loops O(n^3)
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j + 1, n):
                    
                    # time complexity: sum and comparison operation in constant O(1)
                    if nums[i] + nums[j] + nums[k] == 0:

                        # time complexity: sorting 3 elements in near constant O(1)
                        triplet = sorted([nums[i], nums[j], nums[k]])
                        
                        # time complexity: insert operation in constant O(1)
                        res.add(tuple(triplet))

        # overall: time complexity O(n^3)
        # overall: space complexity O(,)
        return [list(triplet) for triplet in res]

    def threeSum(self, nums: List[int]) -> List[List[int]]:
       
        # space complexity: set of unique m triplet tuples O(m)
        n = len(nums)
        res = set()

        # freezing one of the triple tuple values
        # time complexity: iteration over list of n length O(n)
        for i in range(n - 2):

            # grab complement
            target = -nums[i]
            seen = {}      # [ (value → its index), ...]

            # freezing second of the triple tuple values
            # time complexity: iteration over list of n length per outer iteration O(n^2)
            for j in range(i + 1, n):

                # grab complement
                complement = target - nums[j]

                # time complexity: lookup operation in constant O(1)
                if complement in seen:

                    # add unique tuple to res
                    triplet = tuple(sorted((nums[i], nums[j], complement)))
                    res.add(triplet)
                else:
                    seen[nums[j]] = j

        # overall: time complexity  
        # overall: space complexity 
        return [list(t) for t in res]

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        # Note: Two Sum vs 3Sum
        # Two sum, finding two numbers whose sum equals a target is simple
        # with hashmaps or two pointer approaches being efficient
        # 3Sum adds complexity with a third variable.
        # Grouping techniques aim to narrow and organize the solution space
        # reducing redundant checks while finding valid triplets

        # positive, negative, and zero sets
        # space complexity: 
        p, n, z = [], [], []
        
        # set ensures no duplicate triplets
        # space complexity: 
        res = set()

        # time complexity: iterate over list of n length O(n)
        for i in nums:
            if i < 0:
                n.append(i)
            elif i > 0:
                p.append(i)
            else:
                z.append(i)

        # sets for unique groups
        # time complexity: convert list into set O(n)
        P, N = set(p), set(n)

        # (0, num, -num)
        # time complexity: iterate over positive numbers list n length O(n)
        if len(z) > 0:
            for i in P:                
                # time complexity: negative target lookup in constant O(1)
                nTarget = -i
                if nTarget in N:
                    res.add((nTarget, 0, i))

        # (0, 0, 0)
        # time complexity: len operation constant O(1)
        if len(z) >= 3:
            res.add((0, 0, 0))

        # (-, -, +) negative pairs
        # time complexity: iterate over list of negative numbers n length O(n)
        for i in range(len(n)):
            # time complexity: iterate over list of negative numbers n length O(n) per outer iteration O(n), leading to O(n^2)
            for j in range(i+1, len(n)):
                # time complexity: lookup operation constant O(1)
                pTarget = -(n[i] + n[j])
                if pTarget in P:
                    # INCORRECT:
                    # sorted() -> List[int]
                    # cannot hash list into set()
                    # must use tuple(sorted())
                    res.add((sorted([n[i], n[j], pTarget])))
        
        # (-, +, +) positive pairs
        # time complexity: iterate over list of positive numbers n length O(n)
        for i in range(len(p)):
            # time complexity: iterate over list of positive numbers n length O(n) per outer iteration O(n), leading to O(n^2)
            for j in range(i+1, len(p)):
                # time complexity: lookup operation constant O(1)
                nTarget = -(p[i] + p[j])
                if nTarget in n:
                    # INCORRECT:
                    # sorted() -> List[int]
                    # cannot hash list into set()
                    # must use tuple(sorted())
                    res.add(tuple(sorted([p[i], p[j], nTarget])))

        # convert valid set of tuple triplets into valid list of tuple triplets

        # overall: time complexity O(n^2) 
        # overall: space complexity O(n)
        return list(res)  

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        # Note: Two Sum vs 3Sum
        # Two sum, finding two numbers whose sum equals a target is simple
        # with hashmaps or two pointer approaches being efficient
        # 3Sum adds complexity with a third variable.
        # Grouping techniques aim to narrow and organize the solution space
        # reducing redundant checks while finding valid triplets

        # positive, negative, and zero sets
        # space complexity: 
        p, n, z = [], [], []
        
        # set ensures no duplicate triplets
        # space complexity: 
        res = set()

        # time complexity: iterate over list of n length O(n)
        for i in nums:
            if i < 0:
                n.append(i)
            elif i > 0:
                p.append(i)
            else:
                z.append(i)

        # sets for unique groups
        # time complexity: convert list into set O(n)
        P, N = set(p), set(n)

        # (0, num, -num)
        # time complexity: iterate over positive numbers list n length O(n)
        if len(z) > 0:
            for i in P:                
                # time complexity: negative target lookup in constant O(1)
                nTarget = -i
                if nTarget in N:
                    res.add((nTarget, 0, i ))

        # (0, 0, 0)
        # time complexity: len operation constant O(1)
        if len(z) >= 3:
            res.add((0, 0, 0))

        # (-, -, +) negative pairs
        # time complexity: iterate over list of negative numbers n length O(n)
        for i in range(len(n)):
            # time complexity: iterate over list of negative numbers n length O(n) per outer iteration O(n), leading to O(n^2)
            for j in range(i+1, len(n)):
                # time complexity: lookup operation constant O(1)
                # INCORRECT:
                # stop being half asleep, index into the correct array
                pTarget = -(nums[i] + nums[j])
                if pTarget in P:
                    # INCORRECT:
                    # stop being half asleep, index into the correct array
                    res.add(tuple(sorted([nums[i], nums[j], pTarget])))
        
        # (-, +, +) positive pairs
        # time complexity: iterate over list of positive numbers n length O(n)
        for i in range(len(p)):
            # time complexity: iterate over list of positive numbers n length O(n) per outer iteration O(n), leading to O(n^2)
            for j in range(i+1, len(p)):
                # time complexity: lookup operation constant O(1)
                # INCORRECT:
                # stop being half asleep, index into the correct array
                nTarget = -(nums[i] + nums[j])
                if nTarget in n:
                    # INCORRECT:
                    # stop being half asleep, index into the correct array
                    res.add(tuple(sorted([nums[i], nums[j], nTarget])))

        # convert valid set of tuple triplets into valid list of tuple triplets

        # overall: time complexity O(n^2) 
        # overall: space complexity O(n)
        return list(res)  

    def threeSum(self, nums: List[int]) -> List[List[int]]:

        # Note: Two Sum vs 3Sum
        # Two sum, finding two numbers whose sum equals a target is simple
        # with hashmaps or two pointer solutions being efficient
        # 3Sum adds complexity with a third variable,
        # but converting 3Sum into a two sum problem allows
        # the use of hashmap or two pointer solutions again

        # set ensures no duplicate triplets
        # space complexity: 
        results = set()
        n = len(nums)

        # time complexity: default python sorting TimSort, O(n log n)
        nums.sort()

        # mimic 
        # time complexity
        for i in range(n - 2):

            # skip iteration:
            # i should only "BinarySearch" through any number once 
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            # early break: 
            # only allow negative numbers for i in (i, j, k)
            if nums[i] > 0:
                break

            # Set up "BinarySearch" modification:          
            # set new left boundary for iteration BinarySearch
            # reset right boundary for iteration BinarySearch  
            left, right = i + 1, n - 1

            # "BinarySearch" modification: 
            # "<": working within subarray separate from i
            # cannot evaluate num at left == right given constraint i != j, i != k, j != k
            # Base case: no more array remaining to search
            # complement for numbers[i] was not found, 
            # continue iteration for i
            # time complexity: BinarySearch on subarray of n elements O(log n) for n iterations, leading to O(n log n)
            while left < right:
                
                # grab current sum (i, j, k)
                currSum = nums[i] + nums[left] + nums[right]

                # found target sum
                if currSum == 0:
                    
                    # add triplet to result set
                    results.add((nums[i], nums[left], nums[right]))

                    # skip iteration:
                    # j and k should only "BinarySearch" through any number once 
                    left += 1
                    right -= 1

                    # skip iteration:
                    # j and k should only "BinarySearch" through any number once 
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

                # "BinarySearch" on relevant subsection
                # update left or right pointer
                elif currSum < 0:
                    left += 1
                else:
                    right -= 1

        # convert valid set of tuple triplets into valid list of tuple triplets

        # Time Complexity: O(n^2)
        # Space Complexity: O(n)
        return list(results)

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        # Note: Two Sum vs 3Sum
        # Two sum, finding two numbers whose sum equals a target is simple
        # with hashmaps or two pointer approaches being efficient
        # 3Sum adds complexity with a third variable.
        # Grouping techniques aim to narrow and organize the solution space
        # reducing redundant checks while finding valid triplets

        # positive, negative, and zero sets
        # space complexity: 
        p, n, z = [], [], []
        
        # set ensures no duplicate triplets
        # space complexity: 
        res = set()

        # time complexity: iterate over list of n length O(n)
        for i in nums:
            if i < 0:
                n.append(i)
            elif i > 0:
                p.append(i)
            else:
                z.append(i)

        # sets for unique groups
        # time complexity: convert list into set O(n)
        P, N = set(p), set(n)

        # (0, num, -num)
        # time complexity: iterate over positive numbers list n length O(n)
        if len(z) > 0:
            for i in P:                
                # time complexity: negative target lookup in constant O(1)
                nTarget = -i
                if nTarget in N:
                    res.add((nTarget, 0, i ))

        # (0, 0, 0)
        # time complexity: len operation constant O(1)
        if len(z) >= 3:
            res.add((0, 0, 0))

        # (-, -, +) negative pairs
        # time complexity: iterate over list of negative numbers n length O(n)
        for i in range(len(n)):
            # time complexity: iterate over list of negative numbers n length O(n) per outer iteration O(n), leading to O(n^2)
            for j in range(i+1, len(n)):
                # time complexity: lookup operation constant O(1)
                pTarget = -(n[i] + n[j])
                if pTarget in P:
                    res.add(tuple(sorted([n[i], n[j], pTarget])))
        
        # (-, +, +) positive pairs
        # time complexity: iterate over list of positive numbers n length O(n)
        for i in range(len(p)):
            # time complexity: iterate over list of positive numbers n length O(n) per outer iteration O(n), leading to O(n^2)
            for j in range(i+1, len(p)):
                # time complexity: lookup operation constant O(1)
                nTarget = -(p[i] + p[j])
                if nTarget in n:
                    res.add(tuple(sorted([p[i], p[j], nTarget])))

        # convert valid set of tuple triplets into valid list of tuple triplets

        # overall: time complexity O(n^2) 
        # overall: space complexity O(n)
        return list(res)  

    def maxArea(self, height: List[int]) -> int:

        n = len(height)
        maxWater = 0
        
        # time complexity: iterate over array of n length O(n)
        for i in range(n - 1):

            # time complexity: iterate over array of n length for each outer iteration O(n^2)
            for j in range(i + 1, n):

                # calculate current water
                currWater = min(height[i], height[j]) * (j - i)
                maxWater = max(maxWater, currWater)
        
        # overall: time complexity O(n^2)
        # overall: space complexity O(1)
        return maxWater

    def maxArea(self, height: List[int]) -> int:
        
        # set up "BinarySearch" modification
        left, right = 0, len(height)-1
        maxWater = 0 

        # time complexity: two pointer iteration over list of n length O(n)
        while left < right:

            # grab smaller height between outside pointers
            smallerHeight = min(height[left], height[right])

            # width includes walls: 
            # [1, 1] is 1 water, so (rightIndex - leftIndex) = width
            # calculate curr water between outside pointers, (smallerHeight * width)
            currWater = smallerHeight * (right-left)
            
            # compare to global max
            maxWater = max(maxWater, currWater)

            # Greedy:
            # As we move pointers inwards, width is guaranteed to get shrink
            # Thus, we can continue to move our pointers,
            # until we hit a bigger height than our current smaller height
            # time complexity: two pointer iteration over list of n length O(n)
            if height[left] < height[right]:
                # step past current left/right wall combination
                left += 1
                # Greedy:
                while left < right and height[left] < smallerHeight:
                    left += 1 
            else:
                # step past current left/right wall combination
                right -= 1
                # Greedy:
                while left < right and height[right] < smallerHeight:
                    right -= 1

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return maxWater

    def trap(self, height: List[int]) -> int:
        n = len(height)
        water = 0

        # time complexity: iterate over list of n length o(n)
        for i in range(n):

            # Use two pointers to calculate leftMax and rightMax
            leftMax, left = 0, i
            rightMax, right = 0, i

            # time complexity: iterate over left hand side of list n length per outer iteration O(n^2)
            while left >= 0:
                leftMax = max(leftMax, height[left])
                left -= 1

            # time complexity: iterate over right hand side of list n length per outer iteration O(n^2)
            while right < n:
                rightMax = max(rightMax, height[right])
                right += 1

            # curr water trapped for curr bar i
            water += min(leftMax, rightMax) - height[i]

        # overall: time complexity O(n^2)
        # overall: space complexity O(1)
        return water

    def trap(self, height: List[int]) -> int:
        
        L, R = 0, len(height) - 1
        water = 0

        # setting curr left/right max to ends of list
        leftMax, rightMax = height[L], height[R]

        # time complexity: iterate over list of n length with two pointers O(n)
        while L < R:
            
            # grabbing weak link
            if height[L] < height[R]:
                # INCORRECT: skips water trapped at previous position before the pointer moved
                L += 1

                # INCORRECT: updating leftMax *before* calculating trapped water causes error
                leftMax = max(leftMax, height[L])

                # INCORRECT: water calculation uses updated leftMax prematurely
                water += min(leftMax, rightMax) - height[L]

            # grabbing weak link
            else: 
                # INCORRECT: skips water trapped at previous position before the pointer moved
                R -= 1

                # INCORRECT: updating rightMax *before* calculating trapper water causes error
                rightMax = max(rightMax, height[R])

                # INCORRECT: water calculation uses updated rightMax prematurely
                water += min(leftMax, rightMax) - height[R]
        
        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return water

    def trap(self, height: List[int]) -> int:

        # Note: 
        # Outer Pointers: act as wall/side to bound inner pointers
        # Inner Pointers: traverse inward from both ends to track height for current position
        # Water Trapping: compare inner pointer to outer pointers wall/side to determine 
        # if theres enough depth to trap water

        # Set up "BinarySearch" modification
        # outer pointers
        outerLeftMax, outerRightMax = 0, 0
        # inner pointers
        left, right = 0, len(height) - 1
        water = 0

        # Monotonic "BinarySearch" modification
        # time complexity: two pointer iteration over list of n length O(n)
        while left < right:

            # Monotonic "BinarySearch" on relevant subsection
            # implies: height[left] < height[right]
            # case 1: [5, 0, 3, 2, 4, 6], left < right for entire array 
            # case 2: [5, 0, 3, 9, 4, 6], left < right broken at some point
            # case 1 implies: while height[left] < height[right] 
            # and while height[left] < outerLeftMax
            # then: water is limited by outerLeft/outerRight 
            # as water will eventually be caught by right
            if height[left] < height[right]:

                # case 1: implication broken
                # implies: outerLeftMax < height[left] < height[right] 
                # then: update outerLeftMax             
                if height[left] >= outerLeftMax:
                    outerLeftMax = height[left]

                # case 1: implication applies
                # implies: height[left] < outerLeftMax < height[right]
                else:
                    water += outerLeftMax - height[left]

                # shift pointer
                left += 1

            # implies: height[right] < height[left]
            else:
                
                # case 1: implication broken
                # implies: outerRightMax < height[right] < height[left]     
                # then: update outerRightMax
                if height[right] >= outerRightMax:
                    outerRightMax = height[right]

                # case 1: implication applies
                # implies: height[right] < outerRightMax < height[left]
                else:
                    water += outerRightMax - height[right]

                # shift pointer
                right -= 1

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return water

    def trap(self, height: List[int]) -> int:

        # Note: 2 concepts here: 
        # Monotonic Stack: A stack that maintains non-increasing heights 
        # When non-increasing breaks: curr height will serve as right wall,
        # top of stack will serve as depth, and top of stack - 1 will serve as left wall

        # Monotonic stack to store indices
        stack = []  
        water = 0

        # push and pop each bar at most once
        # time complexity: iterate over list of n length O(n)
        for i in range(len(height)):

            # Check: stack is non empty, depth candidate exists
            # Check: if current height[i] breaks non-increasing order,
            # will be viable to act as a right wall
            # implies: we keep appending while monotonic non-increasing stays valid
            # implies: stack is kept in monotonic non-increasing order
            # implies: when monotonic non-increasing breaks, we have found right wall
            while stack and height[i] > height[stack[-1]]:
                
                # curr while loop iteration:
                # height[i]: right wall
                # pop stack[-1]: depth candidate
                # peak stack[-2]: left wall

                # while stack is non-empty:
                # stack.pop() will iterate depth candidate and left wall
                # essentially dragging the right wall over the monotonic stack, 
                # adding all possible water, with all combinations of left wall and depth candidate
                # until a depth candidate is taller than the current right wall
                # then we just add the right wall to the stack maintaining monotonic order
                depthCandidate = stack.pop() 

                # Check: if stack empty after pop, no left wall exists
                # implies: cannot trap water, end while loop, add item to stack
                if not stack:
                    break

                # trapped water involves the space between two walls, excluding walls
                # width = (right - left - 1)

                # After stack.pop():
                # height[i]: right wall
                # popped depthCandidate: depth
                # peak stack[-1]: left wall
                # while loop check implies: depthCandidate < height[i]
                # monotonic stack check implies: depthCandidate < stack[-1]
                rightWall = i
                leftWall = stack[-1]
                distance = rightWall - leftWall - 1

                rightHeight = height[i]
                depthHeight = height[depthCandidate]
                leftHeight = height[leftWall]

                # subtract the depth minus smaller height to get water depth
                boundedHeight = min(rightHeight, leftHeight) - depthHeight

                # add the trapped water for the current segment 
                water += distance * boundedHeight

            # implies: monotonic non-increasing is still valid
            # implies: append height to stack
            stack.append(i)

        # overall: time complexity O(n)
        # overall: space complexity O(n) (due to the stack)
        return water

    def trap(self, height: List[int]) -> int:
        
        # Note:
        # Dynamic Programming Concept:
        # Left Maximum Array: Stores the maximum height encountered from the start up to each index i.
        # Right Maximum Array: Stores the maximum height encountered from the end up to each index i.
        # Avoid recomputing maximum heights repeatedly.

        n = len(height)
        if n == 0:
            return 0

        # Arrays to store max heights from the left and right
        # leftMax[i]: Maximum height from 0 to index i
        # rightMax[i]: Maximum height from index i to (n-1)
        leftMax = [0] * n
        rightMax = [0] * n
        water = 0

        # calculate left max for each bar
        # time complexity: iterate over list of n length O(n)
        leftMax[0] = height[0]
        for i in range(1, n):
            leftMax[i] = max(leftMax[i - 1], height[i])

        # calculate right max for each bar
        # time complexity: iterate over list of n length O(n)
        rightMax[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            rightMax[i] = max(rightMax[i + 1], height[i])

        # calculate trapped water for each bar
        # time complexity: iterate over list of n length O(n)
        for i in range(n):

            # The water trapped above bar i is determined by the minimum between
            # leftMax[i] and rightMax[i] minus the curr bar height
            water += min(leftMax[i], rightMax[i]) - height[i]

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return water

    def longestPalindrome(self, s: str) -> str:

        # Note: 
        # Preprocessing with #, ^, and $:
        # '#': ensures uniform expansion, for both odd and even length palindromes
        # '^' and '$': sentinel characters that don't match valid characters
        # in the input string, serve as true start and end markers
        # '^': ensures all '#' are on odd characters, and since all palindromes 
        # will have a start and end character of '#', it makes it easy to map from
        # the expandedStr to the original string

        # Boundary expansion: 
        # For any index i, center of palindrome at i can either be: 
        # - a character from the original string
        # - a placeholder '#''
        # Center definition allows even length palindromes such as "abba", see below,
        # to have a single middle point, allowing the same expanding logic 
        # for even and odd strings for palindrome validation

        # Ex:
        # ^ # a # b # b # a # $    || new string len 11,
        # 0 1 2 3 4 5 6 7 8 9 10   || with palindromes centered at each index:

        # index 1 palindrome: "#"
        # index 2 palindrome: "#a#"
        # index 3 palindrome: "#" 
        # etc...
        # index 5 palindrome: "#"
        # etc...

        expandableStr = "#".join(f"^{s}$")
        n = len(expandableStr)

        # Note: 
        # Iteration tracks the right boundary for the current farthest right palindromic substring, 
        # This allows us to take advantage of the mirror radius trick
        # to calculate the radius of any index i more efficiently

        # p[i]: radius of the palindrome centered at index i
        # n instead of (n-1), because we ignore sentinel indexes 0 and (n-1)
        p = [0] * n

        # mirror radius validation: tracking right boundary via right
        # right: right boundary of the palindrome with the right most boundary
        right = 0

        # mirror radius validation: calculating mirror index via center
        # center: index of the center of the palindrome with the right most boundary 
        center = 0 

        # range skips sentinel indexes 0 and (n-1), ^ and $
        # i: center of current palindrome
        # time complexity: iterate over list of n length O(n)
        for i in range(1, n - 1):

            # mirror:
            # i is current index being processed
            # i is to the right of center and has a mirror to the left of center
            # ex: center = 6, i = 7 => mirror = (2 * 6) - 7 = 5
            mirror = (2 * center) - i 

            # mirror radius validation:
            # if i lies within bounds of the right most palindrome,
            # the right most palindrome itself guarantees that the palindrome radius
            # for the mirror of i, is applicable to i as well
            # since mirror and i are by definition mirrors/identical to each other
            if i < right:

                # mirror radius is either:
                # - less than the distance between i and right bound,
                #   in which case all of the radius is valid
                # - exceeds bounds and is farther than right bound,
                #   in which case only the radius up until the right bound is valid
                
                # i radius is thus, bounded by minimum between: 
                # - mirror radius
                # - distance from i to the right bound
                p[i] = min(right - i, p[mirror])

            # assumption: if valid case, we have pre-set p[i] to p[mirror]
            # now explore: extend radius p[i] until palindromic status is broken
            while expandableStr[i + p[i] + 1] == expandableStr[i - p[i] - 1]:
                p[i] += 1

            # p[i]: radius for palindrome at i
            # i: center for palindrome at i
            # check: if we have a new right most boundary, update center and right 
            if i + p[i] > right:
                right = i + p[i]
                center = i

        # iteration complete:
        # p[] stores radius of palindrome centered at each index

        # scan through p[] to find the maximum palindrome radius and its center
        maxRadius, centerIndex = max((n, i) for (i, n) in enumerate(p))

        # Note:
        # index and radius are both in context of expandable string, not the original string
        # thus, we need a formula to translate to original string

        # Notice, how in the expanded string, 
        #  - all original characters are on even index
        #  - all original characters have matching # on the left odd index

        # abba =>  ^ # a # b # b # a # $   | a=2, b=4, b=6, a=8
        # 0123 =>  0 1 2 3 4 5 6 7 8 9 10  | #=1, #=3, #=5, #=7

        # aba =>   ^ # a # b # a # $       | a=2, b=4, a=6
        # 012 =>   0 1 2 3 4 5 6 7 8       | #=1, #=3, #=5

        # any palindrome will always end with a '#'.
        # so if we divide the starting odd position by 2, it will always map
        # to an original character.
        # so an easy translation formula is:

        start = (centerIndex - maxRadius) // 2
        
        # splice longest substring

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return s[start: start + maxRadius]