def max_consecutive_ones(nums: list[int]) -> int:

        # Aux state: track current streak
        count = 0

        # Aux state: track max streak
        max_count = 0

        # Left Pointer: iterate array
        for right in range(len(nums)):
            
            # Condition: while consecutive 1's is true
            if nums[right] == 1:
                # Aux state: add to streak
                count += 1
                max_count = max(max_count, count)
            else:
                # Aux state: reset streak
                count = 0

        return max_count

    # max_consecutive_ones([1,1,0,1,1,1]) -> 3

    def is_palindrome(s: str) -> bool:

        # Left: start of array
        # Right: end of array
        left, right = 0, len(s) - 1

        # Break when left and right pointers match 
        # when the middle of the array is hit
        while left < right:

            # if palindrome invariant is broken
            if s[left] != s[right]:
                return False

            # shrink left and right pointers towards middle
            left += 1
            right -= 1

        # valid palindrome
        return True

    # is_palindrome("radar") -> True
    # is_palindrome("hello") -> False

    def longest_unique_substring(s: str) -> int:

        # Left: start of window
        left = 0

        # Window data: stores unique chars within window range
        char_set = set()

        # Window data: stores max window found up to now
        maxLength = 0

        # Right: end of window, expand window range as we iterate
        for right in range(len(s)):

            # Invariant: window holds list of unique chars
            # Broken: if condition is broken, shrink window from the 
            # left side until the unique char condition is true again
            while s[right] in char_set:

                # Window data: remove char on left boundary of window
                char_set.remove(s[left])
                
                # Left: start of window, shrink window range
                left += 1
            
            # Invariant: window holds list of unique chars

            # Window data: add char unique list, guaranteed to be unique
            char_set.add(s[right])
  
            # Window data: check global max
            maxLength = max(maxLength, right - left + 1)

        return maxLength

    # longest_unique_substring("abcabcbb") -> 3

    # linked list node definition
    class ListNode:
        def __init__(self, value=0, next=None):
            self.value = value
            self.next = next

    def has_cycle(head: ListNode) -> bool:
        
        # Tortoise, hare pointers: same starting index
        slow, fast = head, head

        while fast and fast.next:

            # Tortoise pointer: x1 steps
            # Hare pointer: x2 steps
            slow = slow.next
            fast = fast.next.next

            # if pointers match, cycle exists
            # will be hit a n/2 iterations
            if slow == fast:
                return True

        # reached end of list, no cycles
        return False

    # LinkedList: 1 -> 2 -> 3 -> 4 -> 2
    # has_cycle(head) -> True

    def partition(nums, pivot):

        # Left: partition flip slot
        left = 0

        # Right: iterate array checking condition
        for right in range(len(nums)):

            # Condition: if curr element value is less than pivot val, 
            # flip element to left side of array in place
            if nums[right] < pivot:

                # Flip: swap element with flip slot
                nums[left], nums[right] = nums[right], nums[left]

                # Left: iterate flip slot by 1 step
                left += 1

        # Left: ends up pointing to first index where all elements 
        # are greater than the pivot value
        return (nums, left)

    # partition([9, 3, 5, 2, 8, 1, 6], 5) -> ([3, 2, 1, 5, 8, 9, 6], 5)

    def merge_sorted_arrays(arr1, arr2):

        result = []

        # i / j: 2 pointers
        i, j = 0, 0

        # i / j: parallel iterate array, while elements remain in both lists 
        while i < len(arr1) and j < len(arr2):

            # Merge: append smaller element between arrays 
            if arr1[i] < arr2[j]:
                result.append(arr1[i])
                i += 1
            else:
                result.append(arr2[j])
                j += 1
        
        # Merge: one list has run out of elements, 
        # append list with remaining elements as its already sorted
        result.extend(arr1[i:])
        result.extend(arr2[j:])

        # merged sorted array
        return result

    # merge_sorted_arrays([1, 3, 5], [2, 4, 6]) -> [1, 2, 3, 4, 5, 6]

    def split_words(s: str, delim: str = ' ') -> list[str]:

        words = []

        # Left: frozen until right hits delim
        left = 0

        # Right: iterate list checking for delim
        right = 0

        # Right: iterate list
        while right < len(s):

            # Right condition: delimiter found
            if s[right] == delim:

                # Logic: check if non-empty word, 
                # then splice word and add to array
                if left != right:
                    words.append(s[left:right])

                # Left: Catch up, move to right+1, to 1 index
                # after the delimiter, to restart scanning for delim
                left = right + 1

            # Right: iterate pointer, either after delim
            # or to next index
            right += 1

        # Right: hit end of string, check if last word exists
        if left < len(s):
            words.append(s[left:])

        return words


    # split_words("catch up pointers example") -> ['catch', 'up', 'pointers', 'example']

    def threeSum(nums):

        result = []
        nums.sort()

        # k: 3 pointers, i, left, right

        # i: iterate pointer as 'frozen' pointer
        for i in range(len(nums)):

            # i: Avoid duplicates
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            # Inner two pointer approach:

            # Left: 1 index after frozen pointer
            # Right: right end of array
            left, right = i + 1, len(nums) - 1
            while left < right:

                # Condition: check if triplet sum == 0
                current_sum = nums[i] + nums[left] + nums[right]                
                if current_sum == 0:

                    # Match: add triplet
                    result.append([nums[i], nums[left], nums[right]])

                    # Left / Right: Iterate to 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

                # Search: 
                # left end has lowest numbers, right end has highest numbers,
                # shift towards whichever gets triplet sum closer to 0

                # Left: shift towards higher numbers
                elif current_sum < 0:
                    left += 1 

                # Right: shift towards lower numbers 
                else:
                    right -= 1

        return result

    # threeSum([-1, 0, 1, 2, -1, -4]) -> [[-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 of `i` with respect to `center`
            mirror = 2 * center - i

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

            # Expand around 'i' while palindrome condition true
            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))

        # Convert index back to original string
        start = (centerIndex - maxLen) // 2
        
        # Grab palindrome substring
        return s[start: start + maxLen]

if __name__ == "__main__":

    sol = Solution()

    test_cases = [

        # Regular strings
        "hello",
        "aaa",
        "abc",

        # Edge cases
        "",
        "a",

        # Palindrome patterns
        "racecar",
        "abba",
        "abca",
    ]

    for s in test_cases:

        print(sol.isPalindrome(s))

    def reverseString(self, s: List[str]) -> None:
        
        # Two Pointer Approach (In-Place)
        
        # Substring Representation:
        #   - Maintain window [left, right] representing characters to swap
        #   - Goal: Swap characters until window meets in the middle
        
        # Idea:
        #   - Initialize two pointers at the ends of the array
        #   - Swap s[left] and s[right]
        #   - Move pointers inward
        #   - Stop when left >= right

        # Yes, this is a dumb way to do recursion, just a test for syntax

        def helper(left, right):
            if left >= right:
                return
            
            # Swap characters at the current ends
            s[left], s[right] = s[right], s[left]
            
            # Recurse inward
            helper(left + 1, right - 1)
        
        helper(0, len(s) - 1)

        # overall: tc O(n)
        # overall: sc O(n)

    def reverseString(self, s: List[str]) -> None:
        
        # Two Pointer Approach (In-Place)
        
        # Substring Representation:
        #   - Maintain window [left, right] representing characters to swap
        #   - Goal: Swap characters until window meets in the middle
        
        # Idea:
        #   - Initialize two pointers at the ends of the array
        #   - Swap s[left] and s[right]
        #   - Move pointers inward
        #   - Stop when left >= right

        left = 0
        right = len(s) - 1

        # tc: iterate over half the array O(n)
        while left < right:

            # Swap characters at left and right
            s[left], s[right] = s[right], s[left]

            # Shrink window from both ends
            left += 1
            right -= 1
         
        # overall: tc O(n)
        # overall: sc O(1)

if __name__ == "__main__":

    sol = Solution()

    test_cases = [

        # Palindromes
        "racecar",
        "aaa",
        "a",
        "",

        # Non-palindromes
        "abc",
        "leetcode",
        "python",

        # Palindrome after one deletion
        "abca",
        "baabx"
    ]

    for s in test_cases:

        print(s, "=>", sol.isPalindrome(s))

    def isPalindrome(self, s: str) -> bool:
        
        # Note:
        # Appending to a list and joining once is more efficient than repeatedly
        # appending to a string. Strings are immutable, so each concatenation
        # creates a new string and copies all existing characters.
        # tc: list append + join: O(m), repeated string concat: O(m^2)

        # Helper: to skip over non alphaNum chars
        def isAlphaNum(c):
            if (ord('a') <= ord(c) <= ord('z') or
                ord('A') <= ord(c) <= ord('Z') or
                ord('0') <= ord(c) <= ord('9')):
                return True
            return False

        # Helper: to turn uppercase into lowercase
        def upperClean(c):
            if (ord('A') <= ord(c) <= ord('Z')):
                return chr(ord(c)+32)
            return c

        # sc: cleaned version of string O(n)
        cleaned = []

        # tc: iterate string O(n)
        for c in s:

            # only grab alphaNum chars
            if isAlphaNum(c):
                cleaned.append(upperClean(c))
        
        # tc: join alphaNum list O(n)
        phrase = "".join(cleaned)

        # Note:
        # Slicing: [start:stop:step]
        # if start and stop are omitted, slice includes the entire sequence
        # if step is -1, indicates to traverse in reverse

        # tc: single iteration over the two strings
        # sc: creates new reversed string
        res = phrase == phrase[::-1]

        # overall: tc O(n)
        # overall: sc O(n)
        return res

    def isPalindrome(self, s: str) -> bool:
        
        # Helper: to skip over non alphaNum chars
        def isAlphaNum(c):
            if (ord('a') <= ord(c) <= ord('z') or
                ord('A') <= ord(c) <= ord('Z') or
                ord('0') <= ord(c) <= ord('9')):
                return True
            return False

        # Helper: to turn uppercase into lowercase
        def UpperClean(c):
            if (ord('A') <= ord(c) <= ord('Z')):
                return chr(ord(c)+32)
            return c

        # outer ends pointers
        # sc: O(1)
        left = 0
        right = len(s)-1

        # tc: O(1)
        while left < right:

            # skip non-alphaNum, while within bounds
            # tc: O(n)
            while left < right and not isAlphaNum(s[left]):
                left += 1

            # tc: O(n)
            while left < right and not isAlphaNum(s[right]):
                right -= 1

            # grab pointer values
            # sc: O(1)
            leftChar = s[left]
            rightChar = s[right]

            # Convert to lowercase
            leftClean = UpperClean(leftChar)
            rightClean = UpperClean(rightChar)

            # Check: if chars match
            # tc: O(1)
            if leftClean != rightClean:
                return False

            # Shrink pointers towards center
            # tc: O(1)
            left += 1
            right -= 1

        # overall: tc O(n)
        # overall: tc O(1)
        return True

if __name__ == "__main__":

    sol = Solution()

    test_cases = [

        # Palindromes
        "racecar",
        "aaa",
        "a",
        "",

        # One deletion needed
        "abca",
        "baabx",
        "deeee",
        "raceecar",

        # Already near-palindrome
        "abba",
        "abbba",

        # Non-palindromes
        "abc",
        "abcdef",
        "leetcode",

        # Boundary patterns
        "ab",
        "ac",
        "ba",
        "aaab",
    ]

    for s in test_cases:
        print(s, "->", sol.validPalindrome(s))

    def validPalindrome(self, s: str) -> bool:
        
        # Two Pointers (Opposite Ends)
        # + Greedy Decision at First Mismatch

        # Substring Representation:
        #   - Maintain window [left, right] over string s
        #   - Move inward while characters match
        #   - On first mismatch, we are allowed to delete at most ONE character
        
        # Greedy Insight:
        #   - If s[left] != s[right], only two deletions can fix the mismatch:
        #         1) Delete s[left]
        #         2) Delete s[right]
        #   - Deleting any other character will NOT fix this mismatch.
        #   - Therefore, trying these two options is sufficient and exhaustive.
        #   - This makes the solution greedy: we resolve the first conflict locally
        #     and never revisit earlier decisions.

        # Helper: check if strings are palindromes
        def isPalindrome(i: int, j: int) -> bool:

            # tc: worst case O(n)
            while i < j:

                # If char fails palindrome check
                if s[i] != s[j]:
                    return False

                # shrink towards center
                i += 1
                j -= 1

            return True

        # original string length
        n = len(s)


        def isPalindromeSafety(s2):

            # Opposite Ends Variables
            # sc: O(1)
            left = 0
            right = n - 1

            # tc: iterate over n O(n)
            while left < right:

                # Safety hit:
                # current mismatch chars fails palindrome check,
                # check if passes by skipping mismatch chars
                if s[left] != s[right]:

                    # Greedy Skip:
                    # Create two candidate substrings, 
                    # each by skipping one of the 2 mismatched characters
                    return isPalindrome(left + 1, right) or isPalindrome(left, right - 1)

                left += 1
                right -= 1

            return True

        # overall: tc O(n)
        # overall: sc O(1)
        return isPalindromeSafety(s)

    def validPalindrome(self, s: str) -> bool:
        
        # Sliding Window (Two Pointers + Slicing)

        # Substring Representation:
        #   - Maintain window [left, right] over string s
        #   - On mismatch, try removing either:
        #         1) left character
        #         2) right character
        #   - Use slicing to verify palindrome

        n = len(s)

        # Sliding Window Variables
        # sc: O(n) due to slicing creating new substrings
        left = 0
        right = n - 1


        # Helper:
        # su using slicing
        def isPalindrome(sub: str) -> bool:

            # CPython Interpreter:
            #
            #   Slicing: [::-1] is implemented at the interpreter level in CPython
            #   Copy:    sub[::-1] creates a reversed string copy using fast C memory operations
            #   Equal:   sub == sub[::-1] compares strings at C level with fast memory comparison
            #
            # Interpreter level ends up being much faster than a python loop over indices
            #  which adds multiple steps for simple operations
            #
            # tc: O(k), sc: O(k) where k = length of substring
            return sub == sub[::-1]


        # tc: iterate over n O(n)
        while left < right:

            # Safety hit:
            # current mismatch chars fails palindrome check,
            # check if passes by skipping mismatch chars
            if s[left] != s[right]:

                # Greedy Skip:
                # Create two candidate substrings, 
                # each by skipping one of the 2 mismatched characters

                # Slicing:
                # [0:2] = [0, 2) => [0, 1]

                # Skip left char, include right char
                skipLeft = s[left + 1 : right + 1]

                # Include left char, skip right char
                skipRight = s[left : right]         

                # Check if either resulting substring is a palindrome
                return isPalindrome(skipLeft) or isPalindrome(skipRight)

            # Shrink towards center
            left += 1
            right -= 1


        # overall: tc O(n)
        # overall: sc O(n)
        return True

    def mergeAlternately(self, word1: str, word2: str) -> str:
        
        # Two Pointers (Same Direction Traversal)

        # Substring Representation:
        #   - Traverse both strings from left to right
        #   - Append characters alternately from word1 and word2
        #   - If one string finishes first, append the remaining characters
        #
        # Goal:
        #   - Build merged string by alternating characters
        #
        # Pattern:
        #   - Two pointers moving forward independently

        n1 = len(word1)
        n2 = len(word2)

        # Two Pointer Variables
        # sc: O(n1 + n2) for result storage
        i = 0
        j = 0

        # Result list
        # sc: O(n1 + n2)
        merged = []

        # tc: iterate over lists O(min(n1, n2))
        while i < n1 and j < n2:

            # Alternate Appending
            merged.append(word1[i])
            merged.append(word2[j])

            i += 1
            j += 1


        # Word1 has remaining letters
        # tc: O(n1)
        while i < n1:
            merged.append(word1[i])
            i += 1

        # Word2 has remaining letters
        # tc: O(n2)
        while j < n2:
            merged.append(word2[j])
            j += 1

        # Join iterates over list and creates a new string
        # tc: O(n1 + n2)
        # sc: O(n1 + n2)
        res = "".join(merged)

        # overall: tc O(n1 + n2)
        # overall: sc O(n1 + n2)
        return res

if __name__ == "__main__":

    sol = Solution()

    test_cases = [

        # Edge cases
        ([[], 0, [], 0]),
        ([[1], 1, [], 0]),

        # nums2 merges into empty portion of nums1
        ([[0,0,0], 0, [1,2,3], 3]),

        # Already sorted merge
        ([[1,2,3,0,0,0], 3, [4,5,6], 3]),

        # Reverse ordering merge
        ([[4,5,6,0,0,0], 3, [1,2,3], 3]),

        # Interleaving values
        ([[1,3,5,0,0,0], 3, [2,4,6], 3]),

        # Duplicate values
        ([[1,2,2,3,0,0,0], 4, [2,2,4], 3]),

        # Larger spread values
        ([[1,4,7,9,0,0,0], 4, [2,5,8], 3]),

        # nums1 dominant values
        ([[10,20,30,40,0,0,0], 4, [1,2,3], 3]),

        # Mixed pattern
        ([[2,5,7,0,0,0], 3, [1,3,6], 3]),

        # Small length merges
        ([[5,0], 1, [1], 1]),
        ([[1,0], 1, [2], 1])
    ]

    # Run tests
    for nums1, m, nums2, n in test_cases:

        # Copy list to avoid mutation issues between tests
        arr = nums1.copy()
        sol.merge(arr, m, nums2, n)
        print(arr)
        print('------')

    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        
        # Two Pointers (Reverse Direction Traversal)

        # Substring Representation:
        #   - nums1 has length m + n
        #   - First m elements are valid
        #   - Last n elements are placeholders (0s)
        
        # Idea:
        #   - Iterate from right to left across both lists appending the larger number
        #   - We avoid overwriting values in nums1 by going right to left


        # Two Pointer Variables
        # sc: O(1) (in-place modification)

        # Last valid element in nums1
        p1 = m - 1

        # Last element in nums2
        p2 = n - 1

        # Position to write next largest element in num1
        num1Write = m + n - 1

        # While loop is determined by nums2 (p2) since once that finishes,
        # the remaining elements in nums1 (p1) are already in correct order
        # since the array was originally sorted
        # tc: iterate through both arrays once O(m + n)
        # sc: in place merge O(1)
        while p2 >= 0:

            # If nums1 has elements
            # If nums1 has larger num
            # Move nums1[p1] to new position
            if p1 >= 0 and nums1[p1] > nums2[p2]:

                # Place larger value from nums1
                nums1[num1Write] = nums1[p1]

                # Move nums1 pointer left
                p1 -= 1

            # Nums1 has run out of elements
            # or
            # Nums2 has the larger value
            else:

                # Place larger value from nums2
                nums1[num1Write] = nums2[p2]

                # Move nums2 pointer left
                p2 -= 1

            # Always move write pointer left
            num1Write -= 1

        # Nums2 has run out of elements
        # Remaining Num1 elements are already in correct order

        # overall: tc O(m + n)
        # overall: sc O(1)

if __name__ == "__main__":

    sol = Solution()

    test_cases = [
        [],
        [1],
        [2,2,2,2],
        [1,2,3,4],
        [1,1,2],
        [0,0,1,1,1,2,2,3],
        [1,2,2,3,3,4],
        [5,5,5,5,6,7],
        [1,2,3,4,4,4,4],
        [1,1,2,3,3,3,4,5,5]
    ]

    for nums in test_cases:
        k = sol.removeDuplicates(nums)

        # Print result count + modified array
        print("k =", k)
        print("array =", nums)
        print("---")

    def removeDuplicates(self, nums: List[int]) -> int:
        
        # Two Pointer Pattern
        
        # Idea:
        #   - Array is sorted, so duplicates will appear consecutively.
        #   - Two Pointers
        #       left: write position for next unique value
        #       fast: scanning and grabs non duplicates
        #   - left results in pointing to the start of the duplicates
    
        # Edge case: single element
        if not nums:
            return 0

        n = len(nums)

        # Write index for next unique value
        left = 1

        # Check for unique value
        right = 1

        # tc: iterate over n O(n)
        while right < n:

            # Since array is sorted,
            # we can check if previous index is a duplicate
            if nums[right] != nums[right - 1]:

                # unique number found, put in write index
                nums[left] = nums[right]

                # iterate write index
                left += 1

            # iterate unique finder
            right += 1

        # left = index of first duplicate value
        # left = number of unique elements

        # overall: tc O(n)
        # overall: sc O(1)
        return left

if __name__ == "__main__":

    sol = Solution()

    test_cases = [

        # Edge cases
        "",
        "a",
        "0",
        "1",

        # Minimal valid cases
        "01",
        "10",

        # Simple repeating groups
        "0011",      # 2
        "000111",    # 3
        "00001111",  # 4

        # Uneven groups
        "00011",     # 2
        "001",       # 1
        "1100",      # 2

        # Alternating pattern
        "010101",    # 5
        "101010",    # 5

        # Long same-character blocks
        "000000",    # 0
        "111111",    # 0

        # Mixed patterns
        "00110011",  # 6
        "1011000",   # 3
        "00110",     # 3

        # Realistic patterns
        "0001110011", # 6
        "100111001",  # 4

        # Random patterns
        "110001110",  # 5
        "010011",     # 3
    ]

    for s in test_cases:
        print(s, "=>", sol.countBinarySubstrings(s))

    def countBinarySubstrings(self, s: str) -> int:
        
        # Consecutive Group Lengths Approach (Two Pointers)

        # Idea:
        #   - Track consecutive characters as groups using two pointers.
        #   - prevGroupLength stores length of previous group, currGroupLength stores current group.
        #   - Whenever a character change is found, update result by min(prevGroupLength, currGroupLength)
        #   - Continue until the end of the string.

        n = len(s)

        # Empty Check:
        if n <= 1:
            return 0

        # Initialize pointers

        # start of current group
        left = 0
        
        # explore the string
        right = 1 

        # Start prev group at 0
        prevGroupLen = 0
        
        # Start curr group at 1, first element in array
        currGroupLen = 1
        
        # 
        res = 0

        # tc: iterate over n O(n)
        while right < n:

            # Extend current group
            if s[right] == s[right-1]:
                currGroupLen += 1

            # Form new group:
            else:
                
                # Pairs depend on the shorter group:
                #   0011 => "01" and "0011"
                # So we need to check the min group every time a new group is found
                res += min(prevGroupLen, currGroupLen)
                
                # Make current group, the new previous group
                prevGroupLen = currGroupLen

                # start new group
                currGroupLen = 1


            # Iterate group finder
            right += 1

        # Process the last group,
        # as no groups follow the last group to mark it
        res += min(prevGroupLen, currGroupLen)

        # overall: tc O(n)
        # overall: sc O(1)
        return res

    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
            # BUG: 
            # 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 decode(self, encoded: str) -> List[str]:
        
        # base 10 strategy 
        # or 2 pointer splice strategy

        decoded = []
        left = 0

        while left < len(encoded):

            # grab length before delim
            currLen = 0
            while encoded[left] != "#":

                # BUG:
                # we need to update currLen, not add to it
                currLen += (10*currLen) + int(encoded[left])
                left += 1
            
            # step past delim
            left += 1
            substring = []

            for _ in range(currLen):
                substring.append(encoded[left])
                left += 1

            decoded.append(''.join(substring))

        return decoded

if __name__ == "__main__":

    sol = Solution()

    test_cases = [

        # Edge cases with custom delim
        [],
        [""],
        ["a"],
        ["#"],
        ["##"],

        # Mixed length strings
        ["hello"],
        ["leet", "code"],
        ["abc", "defg", "h"],
        ["racecar", "level", "radar"],
    ]

    # Test encoding + decoding round trip
    for strs in test_cases:

        print("Original:", strs)

        encoded = sol.encode(strs)
        decoded = sol.decode(encoded)

        print("Encoded:", encoded)
        print("Decoded:", decoded)
        print("***")

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

        # Note:
        # Appending to a list and joining once is more efficient than repeatedly
        # appending to a string. Strings are immutable, so each concatenation
        # creates a new string and copies all existing characters.
        # tc: list append + join: O(m), repeated string concat: O(m^2)

        # sc: n strings with m chars O(n * m)
        encoded = []

        # tc: iterate list O(n)
        for s in strs:
            
            # Note:
            # custom delimiter to mark start of string "{length}#" -> "5#""

            # tc: delimiter length proportional to log10(m) ~= O(1)
            encoded.append(str(len(s)) )
            encoded.append("#")
            encoded.append(s)
    
        # overall: tc O(n * m)
        # overall: sc O(n * m)
        return ''.join(encoded)


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

        # sc: n strings with m chars O(n * m)
        decoded = []
        left = 0

        # tc: iterate over encoded O(n * m)
        while left < len(encoded):

            # set right to start of length prefix
            right = left

            # tc: log 10 (m) ~= O(1)
            # shift right until pointing to delimiter
            while encoded[right] != "#":
                right += 1

            # after:
            # [ 2 # h i ... ]
            #   ^ ^
            #   l r 

            # slice out string length
            length = int(encoded[left:right])

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

            # after:
            # [ 2 # h i ... ]
            #   ^   ^
            #   l   r 

            # tc: slice out substring of length m 
            decoded.append(encoded[right:right + length])
           
            # set left to start of next custom delimiter
            left = right + length
            
            # after:
            # [ 2 # h i 3 # b y e ...]
            # [ 0 1 2 3 4 5 6 7 8 ...]
            #       ^   ^
            #       r   l

        # overall: tc O(n * m)
        # overall: sc O(n * m)
        return decoded

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

        # Note:
        # Appending to a list and joining once is more efficient than repeatedly
        # appending to a string. Strings are immutable, so each concatenation
        # creates a new string and copies all existing characters.
        # tc: list append + join: O(m), repeated string concat: O(m^2)

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

        # tc: iterate over list of strings n length O(n)
        for s in strs:
            
            # Note:
            # custom delimiter to mark start of string "{length}#" -> "5#""

            # tc: delimiter length proportional to log10(m) ~= O(1)
            encoded.append(str(len(s)) )
            encoded.append("#")
            encoded.append(s)
        
        # overall: tc O(n^2)
        # overall: sc O(n^2)
        return ''.join(encoded)


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

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

        # tc: 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  

            # after:
            # [ 2 # h i ... ]
            #       ^
            #       l  

            # tc: iterate string O(n) for n delimiters O(n), O(n^2)
            substring = []
            for _ in range(currLen):

                # grab string of currLen
                substring.append(encoded[left])
                left += 1
            
            # left is set to start of next length

            # after:
            # [ 2 # h i 3 # b y e ...]
            # [ 0 1 2 3 4 5 6 7 8 ...]
            #           ^
            #           l

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


        # overall: tc O(n^2)
        # overall: sc O(n^2)
        return decoded

if __name__ == "__main__":

    sol = Solution()

    test_cases = [

        # Edge cases
        ([1], 1),
        ([1], 5),

        # Small arrays
        ([1,2], 1),
        ([1,2], 2),
        ([1,2], 3),

        # Classic rotation patterns
        ([1,2,3,4,5,6,7], 3),
        ([1,2,3,4,5,6,7], 1),
        ([1,2,3,4,5,6,7], 7),

        # k greater than length
        ([1,2,3,4,5], 8),
        ([1,2,3,4,5], 12),

        # Reverse pattern
        ([7,6,5,4,3,2,1], 2),

        # Already rotated
        ([3,4,5,6,7,1,2], 2),

        # Duplicate values
        ([1,1,1,1,2,2,2], 3),

        # Mixed values
        ([10,20,30,40,50], 2),

        # Realistic dataset
        ([9,8,7,6,5,4,3,2,1], 4)
    ]

    for nums, k in test_cases:

        arr = nums.copy()
        sol.rotate(arr, k)
        print(f"k = {k}: {arr}")

    def rotate(self, nums: List[int], k: int) -> None:
        
        # Array Re Indexing (Using Extra Array)

        # Substring Representation:
        #   - Each element at index i moves to:
        #         (i + k) % n

        # Issue:
        # We are avoiding overwriting the original array
        # before we rae done mapping all of the elements
        
        # Solution:
        #   - Track where elements will be mapped to in extra array

        n = len(nums)

        # If k is larger than n,
        # just mod it so its relative to the actual array size
        k = k % n

        # sc: O(n) for extra array
        rotated = [0] * n

        # tc: O(n)
        for i in range(n):

            # Calculate new index for curr num at index i
            newIndex = (i + k) % n

            # Push num to new index in extra array
            rotated[newIndex] = nums[i]

        # Overwrite original array with extra array
        # tc: O(n)
        for i in range(n):
            nums[i] = rotated[i]


        # overall: tc O(n)
        # overall: sc O(n)

    def rotate(self, nums: List[int], k: int) -> None:
        
        # Cyclic Replacements (Modular Cycle Traversal)

        # Idea:
        #   - Each element moves to (i + k) % n
        #   - This creates cycles
        #   - Follow each cycle and rotate elements

        # Circle
        #   - The array can be thought as a circle with nodes
        #   - We just traverse the cycle which takes us from node to node
        #     and we just place the nums in their new locations
        #   - Now the circle can actually have multiple cycles:
        #      0 => 2 => 0
        #      1 => 3 => 1
        #     or have a single cycle:
        #      0 => 2 => 4 => 1 => 3 => 0
        #     which is why we need the inner outer while loop to make sure:
        #        - complete the current cycle
        #        - complete all cycles
        
        n = len(nums)

        # If k is larger than n,
        # just mod it so its relative to the actual array size
        k = k % n

        # number of elements moved
        count = 0  

        # start of first cycle
        start = 0

        # tc: each element visited once O(n)
        while count < n:

            current = start
            prevValue = nums[start]

            # Follow cycle
            while True:

                # Cycle Formula
                nextIndex = (current + k) % n

                # Swap elements at Cycle point 
                nums[nextIndex], prevValue = prevValue, nums[nextIndex]

                # Follow the cycle
                current = nextIndex

                count += 1

                # If reached the end of the cycle
                if start == current:
                    break

            # Increase cycle count
            start += 1

        # overall: tc O(n)
        # overall: sc O(1)

    def rotate(self, nums: List[int], k: int) -> None:

        # Two Pointers (Reversal Trick Technique)

        # Key Insight:
        #   Reverse entire array
        #         [7,6,5,4,3,2,1]
        #   Reverse first k elements
        #         [5,6,7,4,3,2,1]
        #   Reverse remaining n-k elements
        #         [5,6,7,1,2,3,4]

        # This achieves rotation in-place.

        n = len(nums)

        # If k is larger than n,
        # just mod it so its relative to the actual array size
        k = k % n
        
        # Helper: reverse subarray nums[left...right]
        def reverse(left, right) -> None:

            # tc: iterate over n O(n)
            while left < right:

                # swap elements at index
                nums[left], nums[right] = nums[right], nums[left]

                # shrink towards middle
                left += 1
                right -= 1

        # Reverse entire array
        reverse(0, n - 1)

        # Reverse first k elements
        reverse(0, k - 1)

        # Reverse remaining elements
        reverse(k, n - 1)

        # overall: tc O(n)
        # overall: sc O(1)

    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:
        
        # boundaries
        left, right = 0, len(height)-1
        maxWater = 0 

        # tc: iteration n O(n)
        while left < right:

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

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

            # Greedy Shift:
            # As we move pointers inwards, width is guaranteed to shrink
            # Thus, the only way to beat our currWater is with a taller height
            # Thus, we can continue to move our pointers,
            # until we hit a bigger height than our current smaller height
            # Or conversely, we only need to stop and check at a bigger height

            # tc: iteration n list O(n)
            if height[left] < height[right]:
                # step past current left/right wall combination
                left += 1
                # Greedy Shift:
                while left < right and height[left] < smallerHeight:
                    left += 1 
            else:
                # step past current left/right wall combination
                right -= 1
                # Greedy Shift:
                while left < right and height[right] < smallerHeight:
                    right -= 1

        # overall: tc O(n)
        # overall: sc O(1)
        return maxWater

    def numRescueBoats(self, people: List[int], limit: int) -> int:
        # Greedy + Two Pointers (Opposite Direction)

        # Substring Representation:
        #   - Sort people by weight
        #   - Maintain window [left, right]
        #       left  -> lightest remaining person
        #       right -> heaviest remaining person
        #
        # Greedy Insight:
        #   - If the heaviest person cannot pair with the lightest,
        #     they cannot pair with anyone.
        #   - So the heaviest must go alone.
        #   - Otherwise, pair them together.
        #
        # Goal:
        #   - Minimize number of boats


        # tc: O(n log n) due to sorting
        people.sort()

        # Two Pointer Variables
        # sc: O(1) (ignoring sort space)
        left = 0
        right = len(people) - 1

        boats = 0


        # tc: O(n)
        while left <= right:

            # If lightest + heaviest fit together
            if people[left] + people[right] <= limit:
                left += 1  # pair them

            # Heaviest person always boards
            right -= 1

            boats += 1


        # overall: tc O(n log n)
        # overall: sc O(1)
        return boats

    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