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]

Sol 2: Iterative In Place
1. (left, right = start, end)
2. while left < right:
    a. s[left], s[right] = s[right], s[left]
    b. left += 1 
    c. right -= 1
3. return

if __name__ == "__main__":

    sol = Solution()

    testCases = [

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

        # Edge cases
        "",
        "a",

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

    for s in testCases:

        chars = list(s)
        sol.reverseString(chars)

        # !r calls repr() on the value before inserting it into the f-string,
        # for strings that means it wraps the output in quotes
        # w/ : 'hello' -> 'olleh'
        # w/o: hello -> hello
        print(f"{s!r} -> {''.join(chars)!r}")

    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)

class Solution {
public:
    void reverseString(vector<char>& s) {

        // 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

        helper(s, 0, s.size() - 1);

        // overall: tc O(n)
        // overall: sc O(n)
    }

private:
    void helper(vector<char>& s, int left, int right) {
        if (left >= right) {
            return;
        }

        // Swap characters at the current ends
        swap(s[left], s[right]);

        // Recurse inward
        helper(s, left + 1, right - 1);
    }
};

    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)

class Solution {
public:
    void reverseString(vector<char>& s) {

        // 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

        int left = 0;
        int right = s.size() - 1;

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

            // Swap characters at left and right
            swap(s[left], s[right]);

            // Shrink window from both ends
            left++;
            right--;
        }

        // overall: tc O(n)
        // overall: sc O(1)
    }
};

Sol 2: Shrink While Cleaning In Place:
1. def isAlphaNum(c):
    a. if ord('a') <= ord(c) <= ord('z') or
          etc
          return True

2. def toLower(c):
    a. if ord('A') <= ord(c) <= ord('Z'):
        return(chr(ord(c) + 32))
    b.   return c

3. (left, right = start, end)
4. while left < right:
    a. while left < right and not isAlphaNum(s[left]):
      left += 1
    b. while left < right and not isAlphaNum(s[right]):
      right -= 1
    c. leftChar = toLower(s[left])
    d. rightChar = toLower(s[right])
    e. if leftChar != rightChar:
        return False
    f. left += 1
    g. right -= 1
5. return True

if __name__ == "__main__":
    sol = Solution()

    categories = {
        "palindrome": ["racecar", "abcba", "aaaaaaaa"],
        "not palindrome": ["ksjdnfjgnsdkf", "ab"]
    }

    for (category, tests) in categories.items():

        for case in tests:

            res = sol.isPalindrome(case)

            print(f"{'category':<10} -> {category}")
            print(f"{'case':<10} -> {case}")
            print(f"{'result':<10} -> {res}")
            print("\n--------------------------\n")

    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
        # tc: O(1)
        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
        # tc: O(1)
        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

    bool isPalindrome(string s) {

        // Note:
        // - std::string is mutable, its a contiguous buffer with capacity (allocated size)
        // - avoids a separate list to ''.join() since Python strings are not mutable

        // Helper: to skip over non alphaNum chars
        // tc: O(1)
        auto isAlphaNum = [](char c) -> bool {
        //   ^^^^          ^^^^^^^^^^^^^^^^^^^
        //   variable      lambda (actual function)
            return (('a' <= c && c <= 'z') ||
                    ('A' <= c && c <= 'Z') ||
                    ('0' <= c && c <= '9'));
        };
        
        // Helper: turn uppercase into lowercase
        // tc: O(1)
        auto upperClean = [](char c) -> char {
            if ('A' <= c && c <= 'Z') {
                return c + 32;
            }
            return c;
        };

        // Reserve():
        // - std:string stores chars in a contiguous buffer with capacity (allocated size)
        //   which bounds the actual length (curr char stored)
        // - push_back() only reallocates() once length has exceeded capacity
        // - reallocates() must allocate new memory with a new capacity
        //   and copy every char over, which is expensive if done repeatedly
        // - reserve() simply preallocates the correct length to avoid unnecessary reallocates()
        // sc: O(n)
        string cleaned;
        cleaned.reserve(s.size());

        // tc: O(n)
        for (char c : s) {

           // only grab alphaNum chars
            if (isAlphaNum(c)) {
                //  ^^^^^^^
                // variable holds a callable oject (the lambda),
                // c++ lets you use () on any variable that is callable,
                // and triggers 'invoke whatever this thing is'
                // () is the call operator and lambdas overload it under the good
                cleaned.push_back(upperClean(c));
            }
        }

        // Replace [::-1]:
        // c++ std::string has no built in slice reverse like [::-1],
        // so we build a reversed copy explicitly via reverse iterators

        // C++ Iterators:
        // There are 3 ways to iterate a string in c++:

        // 1. Index Iteration: 
        //    - when we need the index
        //    - container types must support indexing

        //      for (int i = 0; i < s.size(); i++) {
        //         char c = s[i];
        //      }

        // 2. Range Based For Each Loop:
        //    - need each value, no need for index
        //    - for both containers that do and do not support indexing

        //      int i = 0;
        //      for (char c : s) {
        //          // can use both c and i
        //          i ++;
        //      }

        // 3. Iterators: 
        //    - we have forward iterators and reverse iterators
        //    - when we need more than just the value: a movable position/handle,
        //      partial ranges, two walkers at once, reversed views, or to
        //      pass into STL algorithms (sort, find, count, etc.)
        //    - works on all containers, indexable or not
        //    - only indexable containers (vector, string, array, deque) support
        //      iterator arithmetic (it + n) -- list/set/map iterators can only
        //      move one step at a time (++it), and have no numeric index at all
        
        //      - Simple forward iteration:
        //          string forward;
        //          int i = cleaned.size() - 1
        //          for (auto it = cleaned.begin(); it != cleaned.end(); ++it) {
        //              forward.push_back(*it);
        //              i --;
        //          }

        //      - Forward iteration halfway, with a manually tracked index:
        //          auto mid = s.begin() + s.size() / 2;
        //
        //          string firstHalf;
        //          int i = 0;
        //          for (auto it = s.begin(); it != mid; ++it) {
        //              firstHalf.push_back(*it);
        //              i++;
        //          }

        //          string secondHalf;
        //          int j = s.size() / 2;
        //          for (auto it = mid; it != s.end(); ++it) {
        //              secondHalf.push_back(*it);
        //              j++;
        //          }

        //      - Reverse iteration, with a manually tracked index:
        //          string reversed;
        //          int i = 0;
        //          for (auto it = cleaned.rbegin(); it != cleaned.rend(); ++it) {
        //              reversed.push_back(*it);
        //              i++;
        //          }


        // Range Constructor Iterator For std::string:
        // - same as s[::-1]
        // tc: O(n)
        // sc: O(n)
        
        string reversed;
        for (auto it = cleaned.rbegin(); it != cleaned.rend(); ++it) {
            reversed.push_back(*it);
        }
        
        
        //string reversed(cleaned.rbegin(), cleaned.rend());
        //     ^^^^^^^^  ^^^^^^^^^^^^^^^  ^^^^^^^^^^^^^^^
        //     new       reverse iterator  reverse iterator
        //     string    to cleaned's      to cleaned's
        //     variable  LAST char         position BEFORE
        //                                 the first char


        // this is the "range constructor" for std::string --
        // it takes [start_iterator, end_iterator) and copies every
        // character walked over into a new string
        //
        // rbegin() and rend() are REVERSE iterators: incrementing them
        // walks backward through the original string instead of forward,
        // so walking from rbegin() -> rend() visits cleaned's characters
        // last-to-first, and the constructor copies them in that order --
        // producing a new string that is cleaned, reversed

        bool res = (cleaned == reversed);

        // 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

    bool isPalindrome(string s) {

        // Helper: to skip over non alphaNum chars
        // tc: O(1)
        auto isAlphaNum = [](char c) -> bool {
            return (('a' <= c && c <= 'z') ||
                    ('A' <= c && c <= 'Z') ||
                    ('0' <= c && c <= '9'));
        };

        // Helper: to turn uppercase into lowercase
        // tc: O(1)
        auto upperClean = [](char c) -> char {
            if ('A' <= c && c <= 'Z') {
                return c + 32;
            }
            return c;
        };

        // outer ends pointers
        // sc: O(1)
        int left = 0;
        int right = s.size() - 1;

        // tc: O(n)
        while (left < right) {

            // skip non-alphaNum, while within bounds
            // tc: O(n)
            while (left < right && !isAlphaNum(s[left])) {
                left++;
            }

            // tc: O(n)
            while (left < right && !isAlphaNum(s[right])) {
                right--;
            }

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

            // Convert to lowercase
            char leftClean = upperClean(leftChar);
            char rightClean = upperClean(rightChar);

            // Check: if chars match
            // tc: O(1)
            if (leftClean != rightClean) {
                return false;
            }

            // Shrink pointers towards center
            // tc: O(1)
            left++;
            right--;
        }

        // overall: tc O(n)
        // overall: sc O(1)
        return true;
    }

Sol 1: Skip Char Failsafe Try Skip Slicing
1. def isPalindrome(sub):
    a. (n = len(s))
    b. (left, right = 0, n-1)
    c. return sub == sub[::-1]

2. (left, right = start, end) 
3. while left < right:
   a. if left == right:
        shrink
   b. else +1 extra life:
        return s[left+1:right+1] or s[left:right]  
4. return True

Sol 2: Outer Shrink With Reverse Fa Inwards Greedy Shrink:
def isPalindrome(i, j):
1. (left, right = start, end)
2. while left < right:
   a. if left == right:
        shrink
   b. else +1 extra life:
        return isPalindrome(left+1, right) or isPalindrome(left, right-1)
3. return True

if __name__ == "__main__":

    sol = Solution()

    sections = {
        "palindromes":        ["racecar", "aaa", "a", ""],
        "one deletion":       ["abca", "baabx", "deeee", "raceecar"],
        "near palindrome":    ["abba", "abbba"],
        "non palindromes":    ["abc", "abcdef", "leetcode"],
        "boundary patterns":  ["ab", "ac", "ba", "aaab"],
    }

    testCases = []

    # for each section
    for (label, cases) in sections.items():
        
        # for each testcase in that section
        for s in cases:
        
            # add to our test list
            testCases.append((label, s))

    # print
    for (label, s) in testCases:

        # No shallow copy needed:
        # strings are immutable in Python, validPalindrome cannot mutate s
        res = sol.validPalindrome(s)

        print(f"{'case':<18} -> {label}")
        print(f"{'input':<18} -> {s!r}")
        print(f"{'isPalindrome':<18} -> {res}")
        print("\n------------------------\n")

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

        # Substring Representation:
        #   - Opposite ends over  [left, right] over string s
        #   - On first mismatch, try removing and continue:
        #         1) left character
        #         2) right character
        #   - if failure, false
        #   - Use simple reverse [::-1] slicing to verify palindrome

        n = len(s)

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


        # Simple reverse slicing check
        # tc: O(n)
        # sc: O(n)
        def isPalindrome(sub) -> 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 is faster than a python loop which adds multiple steps for simple ops
            
            return sub == sub[::-1]


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

            # Failsafe hit:
            # chars fails palindrome check,
            # check if we can skip char and pass palindrome check
            if s[left] != s[right]:

                # Greedy Skip:
                # Two chars are mismatching,
                # this gives us 2 candidates substrings
                # by skipping either of the chars

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

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

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

                # If either passes, then failsafe succeeded
                return isPalindrome(skipLeft) or isPalindrome(skipRight)

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

        # String is complete palindrome

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

    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.

        # Simple shrink inwards palindrome:
        # tc: O(n)
        # sc: O(n)
        def isPalindrome(i, j) -> bool:

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

                # substring failed failsafe
                if s[i] != s[j]:
                    return False

                # Continue to shrink
                i += 1
                j -= 1

            # substring passed failsafe
            return True


        # original string length
        n = len(s)

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

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

        # String is a palindrome

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

Sol 1: K Pointer Parallel Traversal With Loop Clean Up
1. (i, j = start1, start2)
2. while i < len1 and j < len2:
   a. res.append(word1[i])
   b. res.append(word2[j])
   c. i += 1, j += 1
3. while i < len1: res.append(word1[i])
4. while j < len2: res.append(word2[j])
5. return "".join(res)

Sol 2: K Pointer Parallel Traversal w/ Slicing Cleanup
1. (i, j = start1, start2)
2. while i < len1 and j < len2:
   a. res.append(word1[i])
   b. res.append(word2[j])
   c. i += 1, j += 1
3. res.append(word1[i::])
4. res.append(word2[j::])
5. return "".join(res)

if __name__ == "__main__":

    sol = Solution()

    sections = {
        "same length":  [
                        ("abc", "xyz")],

        "word1 longer": [
                        ("abcd", "xy"), 
                        ("abcde", "x")],

        "word2 longer": [
                        ("ab", "xyzw"), 
                        ("a", "xyzw")],

        "single char":  [
                        ("a", "b")],

        "one empty":    [
                        ("abc", ""), 
                        ("", "xyz")],

        "both empty":   [
                        ("", "")],
    }

    testCases = []

    # for each section
    for label, pairs in sections.items():

        # for each testcase in that section
        for pair in pairs:

            # add to our test list
            testCases.append((label, pair))

    # for each tuple in each section
    for label, (word1, word2) in testCases:

        # No shallow copy needed:
        # strings are immutable in Python,
        # mergeAlternately cannot mutate word1 or word2
        res = sol.mergeAlternately(word1, word2)

        print(f"{'case':<10} -> {label}")
        print(f"{'word1':<10} -> {word1!r}")
        print(f"{'word2':<10} -> {word2!r}")
        print(f"{'merged':<10} -> {res!r}")
        print("\n------------------------\n")

    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])

            # iterate both lists
            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

    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

        #[i::] [start:end:step], 
        # when end:step are omitted, it says "from index i to end"

        # Append remaining characters via slicing
        # Returns "" if index is out of bounds, 
        # so both are always safe to append
        # tc: O(n1 - i) ~= O(n1) or O(n2 - j) ~= O(n2)
        merged.append(word1[i::])
        merged.append(word2[j::])

        # 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

Sol 1: Reverse Direction Fill Two Separate While Loops:
1. (i, j = end1, end2)
2. (write = end1)
3. while 0 <= i and 0 <= j:
   a. nums1[write] = max(nums1[i], nums2[j])
   b. advance pointer with value written
   c. write -= 1
4. while 0 <= j:
    a. nums1[write] = nums2[j]
    b. j -= 1
5. return

Sol 2: Reverse Direction Fill Single While Loop Based On Nums2 Exhaustion:
1. (i, j = end1, end2)
2. (write = end1)
3. while 0 <= j
    a. if nums1 != exhausted and nums2 != exhausted
        nums1[write] = max(nums1[i], nums2[j])
        advance pointer with value written
    b. else
        nums1[write] = nums2[j]
        advance j
    c. advance write
4. return

if __name__ == "__main__":
    sol = Solution()

    categories = {
        "equal": (([1,2,3,0,0,0], 3), ([1,2,3], 3)),
        "longer": (([1,2,3,4,5,6,7,0,0], 7), ([4,9],2)),
        "empty": (([0,0,0,0,0,0], 0), ([2,4,5,6,7,8], 6))
    }

    for (category, ((a, ax), (b, bx))) in categories.items():

        cpy = a[:]
        sol.merge(a, ax, b, bx)

        print(f"{'original left':<10} -> {cpy}")
        print(f"{'original right':<10} -> {b}")
        print(f"{'merged':<10} -> {a}")
        print("\n------------------------\n")

    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:

        # Two Pointers (Reverse Traversal)

        # Write Array:
        #   - nums1 is larger than nums2
        #   - nums1's first m elements are valid,
        #     the rest are placeholders so we can place nums2 values
        #   - [1, 2, 3, 4, 0, 0, 0]
        #   - [7, 8, 9]

        # Note:
        #   - Iterate from right to left across both lists (larger to lower num)
        #   - Avoid a holder for storing overwritten values
        #     by writing to the placeholder side of nums1 (from right to left)

        # Reverse Traversal
        # sc: O(1)
        L = m - 1
        R = n - 1

        # Placeholder Reverse Write Index
        W = m + n - 1

        # When either array is exhausted, we hit our 2 cases
        # tc: O(m + n)
        while 0 <= L and 0 <= R:

            # Case 2: grab element from list2
            #   - nums2 has the larger value
            if nums1[L] < nums2[R]:
                nums1[W] = nums2[R]

                # Iterate nums2 pointer
                R -= 1

            # Case 1: grab element from list1
            #   - nums1 has the larger or equal value
            else:
                nums1[W] = nums1[L]

                # Iterate nums1 pointer
                L -= 1

            # Always iterate write pointer
            W -= 1


        # Case 1: nums1 still has elements:
        #   - nothing to do as nums1 was already in order:
        #   - [1, 2, 3, 4, 0, 0, 0]

        # Case 2: nums2 still has elements elements
        #   - we can overwrite the elements in nums1 as all have been put in placeholder positions
        #   - [1, 2, 3, 4, 2, 3, 4]
        # tc: O(m)
        while 0 <= R:
            
            # Overwrite nums1 elements
            nums1[W] = nums2[R]
            R -= 1
            W -= 1

        
        # 2 arrays have been merged into nums1

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

    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        

        # Two Pointers (Reverse Traversal)

        # Write Array:
        #   - nums1 is larger than nums2
        #   - nums1's first m elements are valid,
        #     the rest are placeholders so we can place nums2 values
        #   - [1, 2, 3, 4, 0, 0, 0]
        #   - [7, 8, 9]

        # Note:
        #   - Iterate from right to left across both lists (larger to lower num)
        #   - Avoid a holder for storing overwritten values
        #     by writing to the placeholder side of nums1 (from right to left)

        # Reverse Traversal
        # sc: O(1)
        L = m - 1
        R = n - 1

        # Placeholder Reverse Write Index
        W = m + n - 1

        # Once nums2 exhausted, we know nums1 will already be in sorted order
        #   - [1, 2, 3, 4, 0, 0, 0]
        #   - so we can exit based on nums2 exhaustion
        # tc: O(m + n)
        while 0 <= R:

            # Case 1:
            #   - nums2 still has elements
            #   - nums1 still has elements
            #   - compare 2 elements to find the larger
            if 0 <= L and nums1[L] > nums2[R]:

                # move num1 element 
                nums1[W] = nums1[L]

                # iterate nums1 pointer
                L -= 1

            # Case 2:
            #   - nums2 still has elements
            #   - nums1 exhausted
            #   - overwrite num1 elements which have been moved to placeholder slots already
            else:

                # Overwrite nums1 elements
                nums1[W] = nums2[R]
                R -= 1

            # Iterate write pointer
            W -= 1


        # 2 arrays have been merged into nums1

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

Sol 1: Track Group Lengths Side By Side To Find Min Shared 0's and 1's
1. (i = 1)
2. (prev, curr = 0, 1)
3. (groups = 0)
4. while scan <= len:
   a. if arr[i] == arr[i-1]:
      curr += 1
   b. else:
      groups += min(prev, curr)
      prev = curr
      curr = 1
   c. i += 1
5. group += min(prev, curr)
6. return groups

if __name__ == "__main__":

    sol = Solution()

    testCases = [

        # 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 testCases:
        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 we scan as we match characters
        #
        #   - The number of groups found, depends on the shorter group:
        
        # Inner Outer Group Calculation:
        #
        #    0000110 =>  ["01", "0011"]
        #      00110 =>  ["01", "0011"]
        #   
        #   We add the min to the total as the length is the number of groups
        #    0001110 => ["01", "0011", "000111"]  
        #   makes 3 individual groups

        n = len(s) - 1

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

        # Initialize pointers
        # tc: O(1)

        # Start scanner at index 1, we have labeled index 0 as a group
        right = 1 

        # Start prev group at 0, no group exists before index 0
        prevGroupLen = 0
        
        # Start curr group at 1, we have labeled index 0 as a group
        currGroupLen = 1
        
        # Total number of groups
        res = 0

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

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

            # Form new group:
            else:
                
                # We add the min to the total as the length is the number of groups
                #   000111 => "01", "0011", "000111"
                res += min(prevGroupLen, currGroupLen)
                
                # Make current group, the new previous group
                prevGroupLen = currGroupLen

                # Start new group length
                currGroupLen = 1


            # Iterate group finder
            right += 1

        # Nothing will trigger the last group to match
        # as no nums will follow the last group
        res += min(prevGroupLen, currGroupLen)

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

Sol 1, 2: Encode and Decode With Delim "{length}#{string}"
Encode:
1. list = []
2. For each string:
   a. list.append("{length}#")
   b. list.append(string)
3. return "".join(list)

Sol 1: Decode Two Catch-Up Pointers
Decode:
1. list = []
2. (left = start)
3. while left <= len:
   a. (right = left)
   b. While right != '#':
        len = int(s[left:right])
   c. right += 1
   d. list.append(s[right:right+len])
   e. left = right + len
3. return list

Sol 2: Decode One Pointer + Slice String By Length
Decode:
1. list = []
2. (left = start)
3. while left <= encoded_len:
   a. len = 0
   a. While left != '#'
        len = (len * 10) + int(encoded[left])
   b. left += 1, Skip '#'
   c. s = []
   d. for _ in range(len)
        s.append(encoded[left])
   e. list.append(''.join(s))
3. return list

if __name__ == "__main__":

    sol = Solution()

    testCases = [

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

        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: n strings each n length O(n^2)
        encoded = []

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

            # tc: delimiter 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: n strings each n length O(n^2)
        decoded = []
        left = 0

        # tc: n strings each n length O(n^2)
        while left < len(encoded):

            # Grab len from delim "{len}#"
            currLen = 0
            while encoded[left] != "#":

                # Elementary Math Carry 10:
                # add zero to right side of prev,
                # then add new number
                currLen = currLen * 10 + int(encoded[left]) 
                left += 1

            # skip delimiter '#'
            left += 1  

            # left is now pointing to start of string
            # [ 2 # h i ... ]
            #       ^
            #       l 

            # tc: O(n)
            substring = []
            for _ in range(currLen):

                # Grab char from string
                substring.append(encoded[left])
                left += 1
            
            # left is now pointing to start of next length
            # [ 2 # h i 3 # b y e ...]
            # [ 0 1 2 3 4 5 6 7 8 ...]
            #           ^
            #           l

            # Add string to list
            decoded.append(''.join(substring))

        # Return full list of decoded strings

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

Sol 1: Char Order Rank And Compare Word By Pairs
1. rank = {}
2. for (i, char) in enumerate(order):
        a. rank[char] = i
3. (i = start)
4. for i in range (words_len-1)
        a. (word1, word2 = words[i], words[i+1])
        b. minLen = min(word1_len, word2_len)
        c. for j in range minLen:
                differenceFound = False
                if word1[j] != word2[j]:
                    if word1[j] > word[2]:
                        Return False
                    else:
                        differenceFound = True
                        break;
            
        d. if not differenceFound and len(word1) > len(word2):
            return False
3. return True

    def isAlienSorted(self, words: List[str], order: str) -> bool:

        # Two Pointer (Lockstep Across Sequences):
        # Given an alphabet ordering and a list of words,
        # verify that the word list is sorted according to the ordering.

        # Strategy:
        # 1. Build a rank map: char -> alien alphabet order number
        # 2. Grab pairs of words and find the first differing character
        # 3. Differing character determines pairs relative order
        # 4. If one word is a prefix of the other (no differing char found), 
        #    then the shorter word must come first

        # Rank Mapping: 
        # char -> alien alphabet order number
        # sc: O(1)
        rank = {}
        for i, char in enumerate(order):
            rank[char] = i

        # tc: O(n * c)
        for i in range(len(words) - 1):

            pair1 = words[i]
            pair2 = words[i+1]

            # Lockstep Scan:
            # walk both words with j, 
            # only compare up to the shorter words length
            minLen = min(len(pair1), len(pair2))

            # Track whether we found a differing char
            foundDifference = False

            for j in range(minLen):

                # Char Mismatch:
                # there exists a rank difference
                if pair1[j] != pair2[j]:

                    # Incorrect Rank Order:
                    # this pair is in reverse order, invalid order
                    if rank[pair1[j]] > rank[pair2[j]]:
                        return False

                    # Correct Rank Order:
                    # this pair is in the correct order,
                    # no need to continue comparing
                    foundDifference = True
                    break

            # No Rank Difference Found:
            # one is a prefix of the other,
            # validate that the shorter word comes first
            if not foundDifference and len(pair1) > len(pair2):

                # Shorter word is second, invalid order
                return False

        # Every pair of words is in the correct order,
        # entire list is in the correct order

        # overall: tc O(n * l)
        # overall: sc O(1)
        return True

Sol 1: Extra Array For Re Indexing Then Overwrite Original
1. (k = k % n)
2. rotatedCopy = [0] * n
3. For each i in nums:
        a. newIndex = (i + k) % n
        b. rotatedCopy[newIndex] = nums[i]
4. For i in range nums_len:
        a. nums[i] = rotatedCopy[i]
5. return nums

Sol 2: Modular Cycle Traversal With Direct Re Index Into Original:
1. (k = k % n)
2. (numsMoved = 0)
3. (cycleEntryPoint = 0)
3. while numsMoved != n:
   a. indexToShift = cycleEntryPoint
   a. carry = nums[indexToShift]
   b. While True
        shiftedIndex = indexToShift + k
        inBoundsIndex = shiftedIndex % n
        swap(nums[inBoundsIndex], nums[carry])
        indexToShift = inBoundsIndex
        numsMoved += 1
        if indexToShift == cycleEntryPoint:
            break;
   c. cycleEntryPoint += 1
4. return nums

Sol 3: Array Reversal Trick
1. revArr(left, right):
        a. while left < right:
            swap(nums[left], nums[right])
            left += 1, rights -= 1
1. (k = k % n)
2. revArr(0, nums_len-1)
3. revArr(0, k-1)
4. revArr(k, nums_len-1)
5. return arr

if __name__ == "__main__":
    sol = Solution()

    categories = {
        "1": ([1,2,3,4,5], 1),
        "2": ([1,2,3,4,5], 2),
        "3": ([1,2,3,4,5], 3),
        "4": ([1,2,3,4,5], 4),
        "5": ([1,2,3,4,5], 5)
    }

    for (category, (nums, k)) in categories.items():

        # shallow item copy
        cpy = nums[:]

        sol.rotate(nums, k)

        print(f"{'category':<10} -> {category}")
        print(f"{'orig':<10} -> {cpy}")
        print(f"{'k':<10} -> {k}")
        print(f"{'shifted':<10} -> {nums}")
        print("\n----------------------\n")

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

        # Substring Representation:
        #   - Each element moves to (i + k) % n
        #   - We avoid overwriting the original array
        #     before mapping is complete by moving nums to 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
        rotatedCopy = [0] * n

        # Calculate all the new indexes and move nums
        # tc: O(n)
        for indexCandidate in range(n):

            # Shift index i to its new index
            newIndex = (indexCandidate + k) % n

            # Put num in corresponding new index
            rotatedCopy[newIndex] = nums[indexCandidate]

        # Overwrite original array with shifted extra array
        # tc: O(n)
        for i in range(n):
            nums[i] = rotatedCopy[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 movement creates a cycle that we can follow as 
        #     we rotate elements 

        # Cycle:
        #   - Think of the cycle as a circle with nodes
        #   - We can step through the cycle, going from node to node
        #     as we place nums in their new nodes
        
        #   - The circle can 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

        # Total num of elements we have moved to new indexes
        numsMoved = 0  

        # Start of the first cycle
        currCycleEntryPoint = 0

        # tc: shift n elements O(n)
        while numsMoved < n:

            # First shifted index will be the index at the cycle entry point
            indexToShift = currCycleEntryPoint

            # First carried value will be the value at the cycle entry point
            carriedValue = nums[indexToShift]

            # While we have not reached the beginning of the current cycle
            while True:

                # Cycle Formula:

                # shift the index 
                shiftedIndex = indexToShift + k
                
                # make sure it does go out of bounds
                inBoundsIndex = shiftedIndex % n

                # Placed num we are carrying into its new rotated position
                # The displaced number becomes our new carry
                nums[inBoundsIndex], carriedValue = carriedValue, nums[inBoundsIndex]

                # Set new index, as next index we are calculating the new position for
                indexToShift = inBoundsIndex

                # Number of numbers we have replaced
                numsMoved += 1

                # If we returned to the current cycle entry point, cycle is complete
                if currCycleEntryPoint == indexToShift:
                    break

            # Move to the next potential cycle entry point
            currCycleEntryPoint += 1

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

    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: reverses an array
        def reverse(left, right) -> None:

            # tc: 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 [0, k] elements
        reverse(0, k - 1)

        # Reverse second [k, n] elements
        reverse(k, n - 1)

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