hash()  ->  [key mod (5)]
    ----------------------------
    hash(10) = 10 % 5 = 0
    hash(22) = 22 % 5 = 2
    hash(31) = 31 % 5 = 1
    hash(14) = 14 % 5 = 4
    hash(17) = 17 % 5 = 2 (collision!)

    New table size - current number of elements 
    (double table size * load factor) - current n elements
    (2 n * 0.75) 
    1.5 n  = New Load Factor Element Count

    New Load Factor Element Count - Current Element Count
    1.5 n - n 
    0.5
    n/2 = Additional space until next rebalance

    def rotate(nums: List[int], k: int) -> None:
        
        n = len(nums)
        k %= n  # handle cases where k > n
        
        # Opposite ends reverse subarray [start, end]
        def reverse(start: int, end: int) -> None:
            
            # Reverse until hit middle of subarray
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1

        # Reverse entire array
        reverse(0, n - 1)
        # Reverse first k elements [0, k)
        reverse(0, k - 1)
        # Reverse remaining elements [k, n)
        reverse(k, n - 1)

    def freqCount():

        # object
        s = "aabbcc"

        # representation
        freq = {}

        # mapping
        for char in s:
            freq[char] = freq.get(char, 0) + 1

    # freq = {'a': 2, 'b': 2, 'c': 2}

    def groupAnagrams(strs):
        
        # groups
        anagrams = {}

        # for list
        for word in strs:

            # create key
            key = "".join(sorted(word))
            if key not in anagrams:
                anagrams[key] = []
            
            # hash key and put value into bucket
            anagrams[key].append(word)

    # anagrams = {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}

    def fib(n, memo={}):
        if n <= 1:
            return n
        if n not in memo:
            memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
        return memo[n]

    def subsetSum(nums, target):

        result = []

        # Cache to avoid exploring previously visited paths
        cache = {}

        def dfs_backtrack(current, index, total):
            
            # Check if already explored state
            state = (tuple(current), total)
            if state in cache:
                return

            # Mark as explored
            cache[state] = True

            # Early Prune -> no potential valid path is current total exceeds target
            if total > target:
                return
            
            # Valid solution -> no need to explore further, backtrack
            if total == target:
                result.append(list(current))
                return

            # Explore -> branches from current state
            for i in range(index, len(nums)):
                
                # Build
                current.append(nums[i])
                # Explore
                dfs_backtrack(current, i + 1, total + nums[i])
                # Backtrack
                current.pop()

        dfs_backtrack([], 0, 0)
        return result

    def graph():

        # List of edges in the graph
        edges = [(1, 2), (2, 3), (1, 3)]

        # Adjacency list
        graph = {}

        # Build the adjacency list
        for u, v in edges:

            # If the node 'u' or 'v' is not yet in the graph, initialize it
            if u not in graph:
                graph[u] = []
            if v not in graph:
                graph[v] = []

            # Add 'v' to the list of neighbors for 'u' and 'u' to 'v'
            graph[u].append(v)
            graph[v].append(u)

    # graph = {1: [2, 3], 2: [1, 3], 3: [2, 1]}

    def twoSum(nums, target):

        # Complement -> index
        complement_map = {}

        for i, num in enumerate(nums):
            
            # Calculate complement
            complement = target - num
            
            # Lookup(complement)
            if num in complement_map:
                return [complement_map[num], i]
            
            # Put(complement)
            complement_map[complement] = i

        return []

def majorityElement(nums: List[int]) -> int:
    
    # Find element that appears more then floor(n/2) times

    # votes for candidate
    count = 0

    # current candidate
    candidate = None

    for num in nums:
        
        # Reset candidate
        if count == 0:
            candidate = num

        if num == candidate:
            count += 1
        else:
            count -= 1

    # Confirm the candidate ( optional if majority element is guaranteed)
    return candidate

Sol 1: Hashmap Occurrence Counting To Detect Duplicate
1. (count = defaultdict(int))
2. for num in nums:
    a. if count[num] >= 1:
         return true
    b. count[num] += 1
3. return false

Sol 2: Seen Set TC Opt Membership Check To Detect Duplicate
1. (seen = set())
2. for n in nums:
    a. if n in seen:
         return true
    b. seen.add(n)
3. return false

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

        # Note:
        # - track total count of nums during iteration
        # - if count is ever more than 1, duplicate exists

        # sc: O(n)
        count = defaultdict(int)

        # tc: O(n)
        for num in nums:

            # tc: O(1)
            if count[num] >= 1:
                return True

            # tc: O(1)
            count[num] += 1

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

    def containsDuplicate(self, nums: List[int]) -> bool:
        
        # Note
        # - track nums we have seen during iteration
        # - if we encounter num we have already seen, duplicate exists

        # sc: O(n)
        seen = set()

        # tc: O(n)
        for n in nums:

            # tc: O(1)
            if n in seen:
                return True

            # tc: O(1)
            seen.add(n)
            
        # overall: tc O(n)
        # overall: sc O(n)
        return False

    def containsDuplicate(self, nums: List[int]) -> bool:
        
        # Note:
        # - set() in python remove duplicates, leaving only unique elements
        # - if the unique version of the original list is a different length, duplicates exist

        # Create unique set
        # tc: O(n)
        # sc: O(n)
        unique = set(nums)

        # Compare unique set length to original list length
        # tc: O(1)
        res = len(unique) != len(nums)
            
        # overall: tc O(n)
        # overall: sc O(n)
        return res

    def containsDuplicate(self, nums: List[int]) -> bool:
        
        # tc: TimSort  = Python (2.3-3.10)
        # tc: PowerSort = Python (3.11+)
        #   - both have
        #   - worst: O(n log n) 
        #   - avg: O(n log n) 
        #   - best: O(n)

        # sc: both TimSort and PowerSort sort in place O(1)
        nums.sort()

        # tc: O(n)
        for i in range(1, len(nums)):

            # tc: O(1)
            if nums[i] == nums[i - 1]
                return True

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

  oh! pseudocode hasn't been written yet, try another card! :)

    def isAnagram(self, s: str, t: str) -> bool:

        # Char Count:
        # different amount of chars, cannot be anagram
        if len(s) != len(t):
            return False

        # sc: hashmap of 26 elements O(1) 
        count = defaultdict(int)

        # tc: O(n * 2) ~ O(n)
        for x in s:
           count[x] += 1
        for x in t:
           count[x] -= 1

        # tc: O(1)
        for value in count.values():

            # If some char is not zero, 
            # then there is a mismatch in that chars occurrence between the strings,
            # no anagram
            if value != 0:
                return False

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

    def isAnagram(self, s: str, t: str) -> bool:

        # Note:
        # ord() converts unicode char to int representation
        # and use int to index into array

        # Char Count:
        # different amount of chars, cannot be anagram
        if len(s) != len(t):
            return False

        # sc: array of 26 constant O(1)
        count = [0] * 26

        # tc: O(n)
        for i in range(len(s)):
            count[ord(s[i]) - ord('a')] += 1
            count[ord(t[i]) - ord('a')] -= 1

        # tc: O(1)
        for value in count:
            if value != 0:
                return False

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

    def isAnagram(self, s: str, t: str) -> bool:
        
        # Unicode:
        # - allows characters to be represented in multiple valid ways via composing system
        # - use base characters + marks to superimpose and create different alphabets
        # - allows for millions of characters and hundreds of diacritics (e.g., dots, tildes, strokes)
        # - this beats the alternative of having a millions of unique characters

        # Normalization:
        # - we need normalization to allow visually equivalent characters
        #   which have been created via different superimpositions to be equivalent

        # Real world examples:
        # - Text copied from different platforms or editors
        # - User input from different keyboards and OSes
        # - Databases storing mixed Unicode forms
        # - International and multilingual applications
        # - Prevent subtle equality bugs and security issues
        # - etc.
        
        # With normalization:
        # - these are visually equivalent, so they are equal
        #   "é" == "e\u0301"


        # NFC (Unicode Normalization Form C):
        # Combines characters into their superimposed forms to compare visually

        # So e +  ́ = é.
        # allows for even comparison

        # NFD = (Unicode Normalization Form Decomposition):
        # Takes a superimposed form and inverts it to its characters + marks

        # tc: O(n)
        # sc: O(n * 2) ~ O(n)
        import unicodedata
        s = unicodedata.normalize("NFC", s)
        t = unicodedata.normalize("NFC", t)

        # Char Count:
        # different amount of chars, cannot be anagram
        if len(s) != len(t):
            return False

        # sc: O(k)
        count = defaultdict(int)

        # tc: O(n)
        for c in s:
            count[c] += 1

        # tc: O(n)
        for c in t:
            count[c] -= 1

        # tc: O(k)
        for value in count.values():
            if value != 0:
                return False

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

    def isAnagram(self, s: str, t: str) -> bool:

        # Note: Unicode cannot be extended for fixed array of 26 solution 

        # English lowercase letters are bounded: only 26
        # Unicode is not bounded:
        # > 140,000+ code points
        # multiple languages
        # emojis
        # symbols
        # combining characters

        # Thus, no fixed small upper bound we can use for our fixed array single pass solution
        # We need a hashmap / dictionary approach for variable size flexibility

  oh! pseudocode hasn't been written yet, try another card! :)

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        # Note:
        # dictionary is complement -> index 

        # sc: dictionary size relative to input O(n)
        tracking = {}
 
        # tc: iterate over list O(n)
        for i in range(len(nums)):

            # find the complement we should be tracking
            complement = target - nums[i]

            # tc: in operation O(1)
            if complement in tracking:
                return [i, tracking[complement]]
    
            # tc: put operation O(1)
            tracking[nums[i]] = i

        # overall: tc O(n) 
        # overall: sc O(n)
        return []

  oh! pseudocode hasn't been written yet, try another card! :)

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        # Note: 
        # Tuples immutable, allowing them to be hashed
        # Array allows for constant ordered representation

        # sc: n words each of k chars O(n * k)
        anaGroup = {}

        # tc: O(n) 
        for word in strs:
            
            # sc: O(1)
            charCount = [0] * 26  
            
            # tc: O(n)
            for char in word:
                charCount[ord(char) - ord('a')] += 1
            
            # sc: array -> tuple O(1)
            key = tuple(charCount)  
            
            # tc: O(1) 
            if key not in anaGroup:
                anaGroup[key] = []  

            # tc: O(1)
            anaGroup[key].append(word)  


        # overall: tc O(n * k)
        # overall: sc O(n * k)
        return list(anaGroup.values())

    def groupAnagrams(self, strs: List[str]) -> List[List[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: stores n tuple keys O(n) and lists of original k strings O(k), O(n * k)
        anaGroup = {}

        # tc: iterate over list O(n)
        for word in strs:

            # sc: array of 26 constant O(1)
            charCount = [0] * 26
            
            # tc: iterate over string O(m)
            for char in word:
                charCount[ord(char) - ord('a')] += 1
            
            # tc: array of 26 to list O(1)
            values = []
            for count in charCount:
                values.append(str(count))
                # delimiter
                values.append("#")  

            # tc: concat list of 26 to string O(1)
            groupCountKey = ''.join(values)

            # tc: in operation O(1)
            if groupCountKey not in anaGroup:
                anaGroup[groupCountKey] = []

            # tc: put operation O(1)
            anaGroup[groupCountKey].append(word)

        # overall: tc O(n * k)
        # overall: sc O(n * k)
        return list(anaGroup.values())

  oh! pseudocode hasn't been written yet, try another card! :)

    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        n = len(nums)

        # sc: prefix, postfix, result, arrays O(n)
        prefix = [1] * n
        postfix = [1] * n
        res = [1] * n

        # Prefix:
        # prefix of i = prefix of previous index * val of previous index
        # prefix[i] = prefix[i-1] * n[i-1]
        # tc: O(n)
        for i in range(1, n):
            prefix[i] = prefix[i-1] * nums[i-1]

        # Postfix:
        # postfix of i = postfix of next index * val of next index
        # postfix[i] = postfix[i+1] * n[i+1]
        # tc: O(n)
        for i in range(n-2, -1, -1):
            postfix[i] = postfix[i+1] * nums[i+1]

        # Result:
        # result[i] = prefix[i] * postfix[i]
        # tc: iterate list O(n)
        for i in range(n):
            res[i] = prefix[i] * postfix[i]

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

    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        n = len(nums)

        # sc: O(n) 
        res = [1] * n

        # Prefix: 
        # prefix[0] = 1
        # prefix[1] = prefix[0] * nums[0]
        # etc...
        # tc: O(n)
        for i in range(1, n):
            res[i] = res[i-1] * nums[i-1]

        # Postfix:
        # postfix[n-1] = 1
        # postfix[n-2] = postfix[n-1] * nums[n-1] 
        # tc: O(n)
        postfix = 1
        for i in range(n-1, -1, -1):
            
            # res[i] = prefix[i] * postfix[i]
            # res[i] is already holding prefix[i] so we just need postfix
            res[i] *= postfix
            
            # postfix[i] = postfix[i] * nums[i]
            # postfix is already holding postfix[i] so we just need nums[i]
            postfix *= nums[i]

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

  oh! pseudocode hasn't been written yet, try another card! :)

    def isValidSudoku(self, board: List[List[str]]) -> bool:
        
        # Dictionaries Immutable And Hashable Keys:
        # - keys can be any object that is both immutable and hashable
        # - allows us to create tuples for our keys 

        # sc: O(9 * 9) ~ O(1)
        cols = defaultdict(set)
        rows = defaultdict(set)
        grids = defaultdict(set)

        # tc: O(9 * 9) ~ O(1)
        for r in range(9):
            for c in range(9):
                
                # Validate cell if its holding a num
                cell = board[r][c]
                if cell != ".":

                    # Break 9 x 9 grid into 3 x 3 box grids (9 total boxes) 
                    # determine cell box location by = r/3, c/3
                    gridTuple = (r // 3, c // 3)

                    # tc: O(1)
                    if (cell in rows[r] or 
                        cell in cols[c] or 
                        cell in grids[gridTuple] ):
                        return False
                    
                    # tc: O(1)
                    cols[c].add(cell)
                    rows[r].add(cell)
                    grids[gridTuple].add(cell)

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

    def isValidSudoku(self, board: List[List[str]]) -> bool:
        
        # Note: 
        # Solution 2 is faster than Solution 1 for small sets, 
        # such as our 9x9 board, due to defaultdict overhead.
        # defaultdict overhead benefits will only appear on large sets.
        # Array of arrays are most efficient for smaller sets.


        # sc: O(9 * 9) ~ O(1)
        rows = [[], [], [], [], [], [], [], [], []]
        col = [[], [], [], [], [], [], [], [], []]
        grids = [[], [], [], [], [], [], [], [], []]

        # tc: O(9 * 9) ~ O(1)
        for r in range(9):
            for c in range(9):
                
                # Validate cell if its holding a num
                cell = board[r][c]
                if cell != ".":  

                    # indexing box sets by unique int calculation:
                    # ------------
                    #  (j//3)     = 0, 1, 2
                    #  (i//3) * 3 = 0, 3, 6
                    # ------------
                    #    0 1 2
                    # 0  0 1 2
                    # 3  3 4 5
                    # 6  6 7 8
                    # ------------
                    # allows to 9 indexing options

                    boxNum = (r//3) + ((c//3) * 3)

                    # tc: O(1)
                    if (cell in rows[r] or 
                        cell in col[c]  or 
                        cell in grids[boxNum]):
                        return False

                    # sc: O(1)
                    col[c].append(cell)
                    rows[r].append(cell)
                    grids[boxNum].append(cell)
        
        # overall: tc O(1)
        # overall: sc O(1)
        return True

  oh! pseudocode hasn't been written yet, try another card! :)

    def longestConsecutive(nums: List[int]) -> int:
        
        # Continent Boundaries:
        # Imagine a number line with runs of consecutive numbers being colored groups:
        
        #    0 1   4 5 6 7 8   11 12 13 14  19 
        #    ***   #########   -----------  ++ 
        
        # Continent boundaries builds the lengths of these 'continents' as we iterate
        # - all continents start at 0
        # - if number has left and right number neighbors who have continent length
        # - 'bridge the continents' left and right lengths and add +1
        
        #     leftContinent_length   "+1 Bridge"   rightContinent_length 

        longest = 0

        # sc: O(n)
        seqLen = defaultdict(int)

        # sc: O(n)
        numSet = set(nums)

        # tc: O(n)
        for num in numSet:
            
            # Get lengths of neighbor continents
            leftContinentLenFromBoundary = seqLen[num - 1]
            rightContinentLenFromBoundary = seqLen[num + 1]

            # calculate new connected bridge continent length
            bridgedLen = 1 + leftContinentLenFromBoundary + rightContinentLenFromBoundary

            # Update new continent boundaries
            seqLen[num - leftContinentLenFromBoundary] = bridgedLen
            seqLen[num + rightContinentLenFromBoundary] = bridgedLen

            # Compare to global max
            longest = max(longest, bridgedLen)

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

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

    # Rummy Run:
    # Each number is part of only 1 sequence
    # and thus are only iterated over once.
    # Thus, the number of times the loop runs across 
    # all iterations is O(n)

    longest = 0

    # sc: ignore duplicates O(n)
    numSet = set(nums)

    # tc: O(n)
    for runStartCandidate in numSet:

        # Found start of new run:
        # tc: O(1)
        if (runStartCandidate-1) not in numSet: 

            # See how far this run goes
            # tc: O(n)
            currRunLen = 1
            while (runStartCandidate + currRunLen) in numSet:

                # Continue run check
                currRunLen += 1 

            # Compare max
            longest = max(longest, currRunLen)

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

    def longestConsecutive(self, nums: List[int]) -> int:
        
        # Union Find Tree:
        # Tracks sets of elements broken into non overlapping groups.
        # In this case it tracks elements broken into groups of corresponding runs.

        # Check Empty: 
        # Avoid max(size.values()) return error
        if len(nums) == 0:
            return 0

        # Union Find Initialization:
        
        # Stores parent of each number
        # sc: O(n)
        parent = {}  

        # Stores the size of connected components
        # sc: O(n)
        size = {}    

        # Find + path compression
        # tc: O(α(n))
        def find(x):

            # Get Representative:
            # If the parent of x is not itself, keep going up
            if parent[x] != x:

                # Path compression:
                # Set parent of current, to the parent of its eventual parent,
                # the representative
                parent[x] = find(parent[x])

            # Representative Found:
            # Reached top of the group, either through compression or just regular parent, return representative
            return parent[x]

        # Union operation + size optimization
        # tc: O(α(n))
        def union(x, y):

            # Get parent for trees x and y
            rootX = find(x)
            rootY = find(y)

            # If trees do not share representative, they belong to different groups so join
            if rootX != rootY:

                # Grab tree sizes
                xSize = size[rootX]
                ySize = size[rootY]

                # Attach smaller tree to larger tree:
                # 1. join to larger tree and update size 
                # 2. update smaller tree parent to larger tree representative
                if ySize < xSize:
                    parent[rootY] = rootX
                    size[rootX] += size[rootY]
                else:
                    parent[rootX] = rootY
                    size[rootY] += size[rootX]

        # Init Union Find: 
        # tc: O(n)
        for num in nums:

            # Ignore duplicates
            if num not in parent:

                # 1. Set all parents to self
                # 2. Set all sizes to 1
                parent[num] = num
                size[num] = 1

        # Iterate and join elements into groups representing rummy runs
        # tc: O(n)
        for num in nums:

            # If the following number can join into a single run,
            # merge the groups
            if num + 1 in parent:
                union(num, num + 1)
        
        # Return group/tree (sequence of numbers) with longest size/length
        res = max(size.values())

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

  oh! pseudocode hasn't been written yet, try another card! :)

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

        # Merge Sort:
        # Classic divide and conquer -- split the array in half
        # recursively until each piece has 1 element (trivially sorted),
        # then merge pairs of sorted halves back together. The merge
        # step is what does the actual sorting work, in linear time
        # per level, across O(log n) levels.

        def mergeSort(arr: List[int]) -> List[int]:
            # Base case: a single element (or empty) is already sorted
            if len(arr) <= 1:
                return arr

            mid = len(arr) // 2

            # Recurse: sort each half independently
            left = mergeSort(arr[:mid])
            right = mergeSort(arr[mid:])

            # Merge the two sorted halves into one sorted array
            return merge(left, right)

        def merge(left: List[int], right: List[int]) -> List[int]:
            merged = []
            i = j = 0

            # Walk both halves simultaneously, always taking the
            # smaller front element -- this is what keeps the result
            # sorted and is also the classic "merge two sorted lists" op
            while i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    merged.append(left[i])
                    i += 1
                else:
                    merged.append(right[j])
                    j += 1

            # Append any leftovers -- at most one of these loops runs
            merged.extend(left[i:])
            merged.extend(right[j:])

            return merged

        return mergeSort(nums)

        # overall: tc O(n log n), log n levels of recursion, O(n)
        #          merge work per level
        # overall: sc O(n), for the merged sub-arrays at each level
        #          (not in-place)

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

        # Heap Sort:
        # Build a max-heap out of the entire array IN-PLACE (no heapq,
        # since the problem disallows built-in sort/heap functions).
        # Then repeatedly swap the max (root) with the last unsorted
        # element and shrink the heap by one, restoring the heap
        # property each time. This sorts the array in-place with O(1)
        # extra space -- the best space complexity of these four solutions.

        n = len(nums)

        def siftDown(heapSize: int, root: int) -> None:
            # Sift Down:
            # push the element at `root` down until it's >= both its
            # children, restoring the max-heap property for the subtree
            largest = root
            left = 2 * root + 1
            right = 2 * root + 2

            if left < heapSize and nums[left] > nums[largest]:
                largest = left
            if right < heapSize and nums[right] > nums[largest]:
                largest = right

            # If a child was bigger, swap it up and keep sifting down
            # into whichever subtree we swapped into
            if largest != root:
                nums[root], nums[largest] = nums[largest], nums[root]
                siftDown(heapSize, largest)

        # Build-Heap:
        # start from the last non-leaf node and sift down each node --
        # this bottom-up build is O(n), not O(n log n), since most
        # nodes are near the bottom and sift down a short distance
        for i in range(n // 2 - 1, -1, -1):
            siftDown(n, i)

        # Extract:
        # the root of a max-heap is always the current largest element.
        # Swap it to the end (its final sorted position), shrink the
        # heap by one, then sift the new root down to restore the heap
        for end in range(n - 1, 0, -1):
            nums[0], nums[end] = nums[end], nums[0]
            siftDown(end, 0)

        return nums

        # overall: tc O(n log n) -- O(n) to build the heap,
        #          O(n log n) for n extractions each costing O(log n)
        # overall: sc O(1), sorts in-place (ignoring recursion stack,
        #          which can be made O(1) with an iterative siftDown)

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

        # To avoid Quick Sort O(n^2)
        # use pivot = nums[random.randint(left, right)], 
        # instead of pivot = nums[(left + right) // 2]

        # Quick Sort (Randomized):
        # Pick a random pivot, partition the array in-place so
        # everything smaller ends up left of the pivot and everything
        # bigger ends up right, then recurse on each side. Randomizing
        # the pivot choice avoids the classic O(n^2) worst case that
        # a fixed pivot (like "always first element") hits on already
        # sorted or adversarial input.

        def quickSort(lo: int, hi: int) -> None:
            if lo >= hi:
                return

            pivotIndex = partition(lo, hi)

            # Recurse on both sides of the pivot's final position
            quickSort(lo, pivotIndex - 1)
            quickSort(pivotIndex + 1, hi)

        def partition(lo: int, hi: int) -> int:
            # Randomize:
            # swap a random element into the pivot slot (last position)
            # so the algorithm's performance doesn't depend on input order
            randIdx = random.randint(lo, hi)
            nums[randIdx], nums[hi] = nums[hi], nums[randIdx]

            pivot = nums[hi]
            i = lo  # boundary: everything before i is < pivot

            # Lomuto Partition:
            # walk through, and whenever we find something smaller
            # than the pivot, swap it into the "smaller" region and
            # advance the boundary
            for j in range(lo, hi):
                if nums[j] < pivot:
                    nums[i], nums[j] = nums[j], nums[i]
                    i += 1

            # Place the pivot in its correct final sorted position
            nums[i], nums[hi] = nums[hi], nums[i]

            return i

        quickSort(0, len(nums) - 1)
        return nums

        # overall: tc O(n log n) expected (randomization makes O(n^2)
        #          worst case astronomically unlikely in practice)
        # overall: sc O(log n) expected, for the recursion stack
        #          (in-place partitioning otherwise)

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

        # Counting Sort:
        # NOT comparison-based, so the usual O(n log n) lower bound
        # for comparison sorts doesn't apply here. Since constraints
        # guarantee values are bounded (-5*10^4 to 5*10^4, a range of
        # 10^5 + 1 possible values), we can count occurrences of each
        # value directly and reconstruct the sorted array from those
        # counts -- true O(n + range) time.

        # Why this isn't "cheating" the O(n log n) requirement:
        # the problem asks for a solution "in O(n log n) time" as a
        # baseline expectation (ruling out naive O(n^2) approaches),
        # and counting sort satisfies that trivially since
        # O(n + range) is asymptotically better when range is bounded --
        # but it's only viable BECAUSE the constraints guarantee a
        # bounded range; it wouldn't work for arbitrary integers.

        OFFSET = 50000  # shift negative values into a valid index range
        RANGE = 100001  # -50000 to 50000 inclusive

        # sc: O(range), one counter per possible value
        counts = [0] * RANGE

        # Count occurrences of each value
        # tc: O(n)
        for num in nums:
            counts[num + OFFSET] += 1

        result = []

        # Reconstruct:
        # walk counts in ascending order, appending each value as
        # many times as it occurred
        # tc: O(n + range), range dominates only when range >> n
        for i, count in enumerate(counts):
            if count > 0:
                result.extend([i - OFFSET] * count)

        # overall: tc O(10^5) ~ O(n + range)
        # overall: sc O(n + range)
        return result