LeetCode: Arrays and Hashing

    def rotate(nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n  # handle cases where k > n
        
        def reverse(start: int, end: int) -> None:
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1

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

    def freqCount():
        s = "aabbcc"
        freq = {}
        for char in s:
            freq[char] = freq.get(char, 0) + 1
        # freq = {'a': 2, 'b': 2, 'c': 2}

    def groupAnagrams(strs):
        anagrams = {}
        for word in strs:
            key = "".join(sorted(word))
            if key not in anagrams:
                anagrams[key] = []
            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):
        # Cache to store paths that can no longer lead to valid solutions
        cache = {}
        result = []

        def backtrack(current, index, total):
            # Check if we've encountered this path before
            state = (tuple(current), total)
            if state in cache:
                return
            cache[state] = True

            # Prune: If the total exceeds the target
            if total > target:
                return
            
            # Valid solution
            if total == target:
                result.append(list(current))
                return

            # Explore further candidates
            for i in range(index, len(nums)):
                # Choose
                current.append(nums[i])
                # Recurse
                backtrack(current, i + 1, total + nums[i])
                # Undo the choice
                current.pop()

        backtrack([], 0, 0)
        return result

    def graph():
        edges = [(1, 2), (2, 3), (1, 3)]  # List of edges in the graph
        graph = {}  # Initialize an empty hashmap to represent the graph

        # Build the adjacency list
        for u, v in edges:
            if u not in graph:  # If the node `u` is not yet in the graph, initialize it
                graph[u] = []
            if v not in graph:  # If the node `v` is not yet in the graph, initialize it
                graph[v] = []
            graph[u].append(v)  # Add `v` to the list of neighbors for `u`
            graph[v].append(u)  # Add `u` to the list of neighbors for `v`

        # Resulting adjacency list representation
        # graph = {1: [2, 3], 2: [1, 3], 3: [2, 1]}

    def twoSum(nums, target):
        # Map to store complement -> index
        complement_map = {}

        for i, num in enumerate(nums):
            complement = target - num
            
            # Check if current number is a complement of a previously seen number
            if num in complement_map:
                return [complement_map[num], i]
            
            # Store complement of current number with index for future lookup
            complement_map[complement] = i

        return []

def majorityElement(nums: List[int]) -> int:
    candidate = None
    count = 0

    # Phase 1: Find a candidate for the majority element
    for num in nums:
        if count == 0:  # Reset candidate
            candidate = num
        count += (1 if num == candidate else -1)

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

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

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

            # time complexity: iteration of O(n^2)
            # 1 + 2 + 3 ... (n - 3) (n - 2) (n - 1) -> 
            # sandwich with reverse sum and cross out like terms -> n(n-1)/2 = O(n^2)
            for j in range(i + 1, len(nums)):

                # time complexity: comparison O(1)
                if nums[i] == nums[j]:
                    return True
        
        # overall: time complexity O(n^2) 
        # overall: space complexity O(1)
        return False

   def containsDuplicate(self, nums: List[int]) -> bool:
        
        # sorts small segment of array using in-place Insertion Sort 
        def insertionSort(arr: List[int], start: int, end: int) -> None:
            
            # insertion sort algo on small segment [start+1, end]
            for i in range(start + 1, end + 1):
                key = arr[i]
                j = i - 1

                while j >= start and arr[j] > key:
                    arr[j + 1] = arr[j]
                    j -= 1
                arr[j + 1] = key

        # merges two sorted subarrays into a single sorted segment using in-place Merge Sort
        def merge(arr: List[int], start: int, mid: int, end: int) -> None:
            
            # temporary arrays for left and right halves
            left = arr[start:mid + 1]
            right = arr[mid + 1:end + 1]

            # pointer for left and right arrays
            i = j = 0

            # pointer for main array where merged elements are placed
            k = start

            # merge sort algo elements into arr[start...end]
            while i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    arr[k] = left[i]
                    i += 1
                else:
                    arr[k] = right[j]
                    j += 1
                k += 1

            # place left over elements within the array, cannot use extend()
            while i < len(left):
                arr[k] = left[i]
                i += 1
                k += 1
            while j < len(right):
                arr[k] = right[j]
                j += 1
                k += 1

        # sorts array into place using runs of 32
        def timSort(arr: List[int], run: int = 32) -> None:
            
            n = len(arr)

            # Sort small runs using Insertion Sort
            # time complexity: initial sort runs O((n/run)) * run^2) ~ O(n)
            for i in range(0, n, run):
                insertionSort(arr, i, min(i + run - 1, n - 1))

            # Iterate over array and merge sort runs
            # time complexity: O(log(n/run) * n) ~ O(n log n)
            size = run
            while size < n:

                # merge neighbor pairs of runs of length 'size'
                for start in range(0, n, size * 2):
                    mid = min(start + size - 1, n - 1)
                    end = min(start + size * 2 - 1, n - 1)

                    # merge if two valid runs exists (mid < end)
                    if mid < end:
                        merge(arr, start, mid, end)

                # merged two runs of length size
                # update new run length = old run len + old run len
                size *= 2

        timSort(nums)
        
        # check for duplicates in the sorted array
        # time complexity: iterate over sorted array of n length O(n)
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return True
        
        # overall: time complexity O(n log n)
        # overall: space complexity O(n)
        return False

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

        # time complexity: iteration of O(n)
        for i in nums:

            # time complexity: iteration of O(n)
            for j in nums: 

                # INCORRECT: iterating element-wise will comparing elements to themselves
                # use index iteration in this case
                if i == j 
                    return True

        return False 

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

        # space complexity: dictionary of O(n)
        count = defaultdict(int)

        # time complexity: iteration over list of n length O(n)
        for num in nums:

            # time complexity: lookup operation in constant O(1)
            if count[num] >= 1:
                return True
            count[num] += 1

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

    def containsDuplicate(self, nums: List[int]) -> bool:
        
        # space complexity: hashset of O(n)
        seen = set()

        # time complexity: iteration of O(n)
        for n in nums:

            # time complexity: lookup operation of O(1)
            if n in seen:
                return True
            seen.add(n)
            
        # overall: time complexity  O(n)
        # overall: space complexity O(n)
        return False

    def isAnagram(self, s: str, t: str) -> bool:
        
        # time complexity: comparison of O(1)
        if len(s) != len(t):
            return False
        
        # time complexity: sorting of O(n log n) for sorting each string
        # space complexity: overall of O(n) = temporary arrays O(n) + recursion stack of O(log n)
        def mergeSort(string):
            
            # base case of list with single element ['']
            # time complexity: O(1)
            # space complexity: O(1)
            if len(string) <= 1:
                return string
            
            # time complexity: dividing operation in constant O(1)
            mid = len(string) // 2

            # mergeSort both subarrays
            left = mergeSort(string[:mid])
            right = mergeSort(string[mid:])
            
            # base case of merge two lists with single element merge ([''], [''])
            return merge(left, right)
        
        # Time Complexity: O(n) per merge
        # Space Complexity: O(n) for temporary storage of the merged array
        def merge(left, right):
        
            sorted = []
            i = j = 0

            # time complexity: iterate over two strings combined n length O(n) 
            while i < len(left) and j < len(right):

                # sort characters into sorted while iterating
                if left[i] <= right[j]:
                    sorted.append(left[i])
                    i += 1
                else:
                    sorted.append(right[j])
                    j += 1
            

            # time complexity: O(n) in worst case if either list is empty
            sorted.extend(left[i:]) # If elements remain in `left`
            sorted.extend(right[j:]) # If elements remain in `right`

            return sorted

        # Time Complexity: O(n log n) for sorting each string
        # Space Complexity: O(n) for temporary arrays and recursion stack
        sorted_s = mergeSort(list(s))
        sorted_t = mergeSort(list(t))


        # overall: time complexity: O(n log n)
        # overall: space complexity: O(n)
        return sorted_s == sorted_t

    def isAnagram(self, s: str, t: str) -> bool:
        
        # checking if length match
        if len(s) != len(t):
            return False

        # INCORRECT: checks only if all characters of s are in t
        # and not vice versa
        for char in s:
            if char not in t:
                return False
        
        # INCORRECT: does not validate that character frequency counts match
        return True

    def isAnagram(self, s: str, t: str) -> bool:
        
        # space complexity: hashmap of 26 elements constant  O(1) 
        count = defaultdict(int)

        # time complexity: iteration over string of n length O(n)
        for x in s:
           count[x] += 1

        # time complexity: iteration over string of n length O(n)
        for x in t:
           count[x] -= 1

        # time complexity: iteration over string of n length O(n)
        for value in count.values():

            # time complexity: comparison operation in constant O(1)
            if value != 0:
                return False

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

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

        # note: ord() converts a single uni-code character to its integer representation
        # int: 97-122 -> lowercase English alphabet (a-z)
        # we can calculate any char (a-z)'s uni-code integer by subtracting uni-code of 'a'
        # '(a-z)' - 'a': returns a value of 0-25 which we can index into our array
        # this simulates a hashing into our array

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

        # time complexity: iteration of O(n)
        for x in s:
           count[ord(x) - ord('a')] += 1

        # time complexity: iteration of O(n)
        for x in t:
           count[ord(x) - ord('a')] -= 1

        # time complexity: iteration of O(n)
        for value in count:

            # time complexity: comparison of O(1)
            if value != 0:
                return False

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

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        # time complexity: iteration of O(n)
        for i in range(len(nums)):

            # time complexity: iteration of O(n^2) 
            # 1 + 2 + 3 ... (n - 3) (n - 2) (n - 1) -> 
            # sandwich with reverse sum and cross out like terms -> n(n-1)/2 = O(n^2)
            for j in range(i + 1, len(nums)):

                # time complexity: summation + comparison of O(1)
                if nums[i] + nums[j] == target:
                    return [i, j]

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

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        # space complexity: hashmap of (int, index) for list n length O(n)
        tracking = {} 

        # time complexity: iterate over list n length o(n)
        for i, num in enumerate(nums):

            # INCORRECT: Overwrites already existing value in the tracking map
            # nums = [3, 3] target = 6 would fail
            tracking[num] = i

            # find complement
            complement = target - num

            # grab complement 
            if complement in tracking:
                return [tracking[complement], i]

        return []

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        # map of {complement: index, complement: index...}
        # space complexity: hashmap of list of n length  O(n)
        tracking = {}
 
        # time complexity: iterating over list of size n O(n)
        for i in range (len(nums)):

            # grab curr complement -> (target = nums[i] + complement) 
            # time complexity: subtraction O(1) 
            complement = target - nums[i]

            # time complexity: lookup operation O(1)
            if complement in tracking:
                
                # [curr_index, complement_index]
                return [i, tracking[complement]]
    
            # if miss, track currElement as potential complement
            # time complexity: insert operation O(1)
            tracking[nums[i]] = i

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

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        # time complexity: O(k log k) = merge two halves O(k) * num of levels of recursion O(log k) 
        # space complexity: O(k) = temporary array during merging O(k) + recursion stack memory O(log k)
        def mergeSort(word):
        
            # base case: list with 1 element
            # time complexity: O(1)
            # space complexity: O(1)
            if len(word) <= 1:
                return word
            
            mid = len(word) // 2
            

            # space complexity: temporary array O(k) + recursion stack memory O(log k)
            left = mergeSort(word[:mid])
            right = mergeSort(word[mid:])
            
            # space complexity: temporary array O(k)
            sorted = []
            i = j = 0
            
            # time complexity: iteration of both subarrays O(n)
            # space complexity: temporary arrays of O(n)
            while i < len(left) and j < len(right):
                if left[i] < right[j]:
                    sorted.append(left[i])
                    i += 1
                else:
                    sorted.append(right[j])
                    j += 1
            
            # Adding remaining elements from either half
            sorted.extend(left[i:])  # time complexity: O(n)
            sorted.extend(right[j:]) # time complexity: O(n)

            return ''.join(sorted_word)
    
        # space complexity: O(n * k) = for n sorted string key O(n) and original string value of length k O(k)
        anaGroup = {}
        
        # time complexity: O(n * k log k), where n is number of strings and k is maximum length
        for word in strs:
            
            # time complexity: merge sort O(k log k)
            sorted = mergeSort(word)

            # time complexity: lookup + insertion O(1)
            if sorted in hashmap:
                hashmap[sorted].append(word)
            else:
                hashmap[sorted] = [word]
        

        # overall: time complexity 
        # overall: space complexity
        return list(anaGroup.values())

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        # space complexity: stores unique m tuple keys O(m) and lists of k strings O(k), O(m * k)
        anaGroup = {}
        
        # Iterating over all strings O(n)
        for word in strs:
            
            # Counting character frequencies O(k)
            charCount = [0] * 26
            for char in word:
                charCount[ord(char) - ord('a')] += 1
            
            # INCORRECT: Mutable list `charCount` used as key
            if charCount not in anaGroup:
                anaGroup[charCount] = []  # Initialize list for group if key doesn't exist
            
            anaGroup[charCount].append(word)
        
        # overall: time complexity
        # overall: space complexity 
        return list(anaGroup.values())

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        # space complexity: stores unique m tuple keys O(m) and lists of k strings O(k), O(m * k)
        groupAna = {}

        # Iterating over all strings O(n)
        for s in strs:
            count = defaultdict(int)

            for c in s:
                count[c] += 1

            tupKey = tuple(count)

            # INCORRECT: hashmaps (count obj) is not sorted
            # so tupKey will vary for "cat" vs "tac"
            if tupKey not in groupAna:
                groupAna[tupKey] = []

            groupAna[tupKey].append(s)

        return list(groupAna.values())

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        # space complexity: stores n tuple keys O(n) and lists of original k strings O(k), O(n * k)
        anaGroup = {}
        
        # time complexity: iterating over list of n length O(n)
        for word in strs:
            
            # INCORRECT: Set creates a key excluding duplicates
            charSet = set()  
            for c in word:
                charSet.add(c) 
            
            # set sort string key
            setSort = ''.join(sorted(charSet))
            
            if setSort not in anaGroup:
                anaGroup[setSort] = [] 
            anaGroup[setSort].append(word)
        
        return list(anaGroup.values())

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        # Note: Tuples in python are immutable which makes them suitable as keys for a hashmaps
        # Lists are mutable and as such not hashable for hashmaps
        # You should use tuples where the position carries semantic meaning. 

        # [26 char count tuple key -> [anagram group list], ...]
        
        # space complexity: stores unique m tuple keys O(m) and lists of k strings O(k), O(m * k)
        anaGroup = {}

        # time complexity: iterating over all strings O(n) 
        for word in strs:
            
            # space complexity: fixed-sized array for 26 lowercase letters O(1)
            charCount = [0] * 26  
            
            # time complexity: counting chars in string of k length O(k)
            for char in word:
                charCount[ord(char) - ord('a')] += 1
            
            # space complexity: fixed-size tuple of length 26 O(1)
            key = tuple(charCount)  
            
            # time complexity: lookup operation of O(1) 
            if key not in anaGroup:
                anaGroup[key] = []  

            # time complexity: append operation to list O(1)
            anaGroup[key].append(word)  


        # overall: time complexity  O(n * k)  
        # overall: space complexity O(m * k)
        return list(anaGroup.values())

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

        # Note: using a list to build the string key is more efficient than repeatedly appending to a string, 
        # as it avoids the overhead of creating new string objects on each append
        # list takes O(m) time vs string append which takes O(m^2)

        # space complexity: stores n tuple keys O(n) and lists of original k strings O(k), O(n * k)
        anaGroup = {}

        # time complexity: iterating over n strings O(n)
        for word in strs:

            # space complexity: fixed-sized array of 26 lowercase characters O(1)
            charCount = [0] * 26
            
            # time complexity: counting characters for string k length O(k)
            for char in word:
                charCount[ord(char) - ord('a')] += 1
            
            # time complexity: creating unique char count key from fixed-sized array of 26 O(1)
            # Using a list to build the key
            key_parts = []
            for count in charCount:
                key_parts.append(str(count))
                key_parts.append("#")  # Separator

            # Concatenate once at the end
            key = ''.join(key_parts)

            # time complexity: lookup operation for key O(1)
            if key not in anaGroup:
                anaGroup[key] = []  # Initialize list for key if doesn't exist
            anaGroup[key].append(word)  # Add word to corresponding key group

        # overall: time complexity
        # overall: space complexity 
        return list(anaGroup.values())

    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        
        # space complexity: frequency count for all unique integers O(m)
        count = defaultdict(int)

        # time complexity: iterate over list of n integers O(n)
        for num in nums: 

            # time complexity: insertion operation takes constant O(1)
            count[num] += 1


        # time complexity: iteration for conversion to list takes O(m)
        # space complexity: list size is equal to number of unique integers O(m)
        countTuple = list(count.items()) # [(num, freq), ...]

        # time complexity: Insertion sort 
        # Best case O(m), Average O(m) = O(m^2/2), Worst O(m^2)
        for i in range(1, len(countTuple)):
            key = countTup[i][1]
            j = i - 1

            # while left element is greater than key
            while j >= 0 and countTuple[j][1] < key:
                countTuple[j + 1] = countTuple[j]
                j -= 1
            
            countTuple[j + 1] = key # place key

        # time complexity: grab k top occurring ints from frequency list O(k)        
        result = []
        for i in range(k):
            
            # grabbing int key from tuple [(int, count), ...]
            result.append(countTuple[i][0]) 

        # overall: time complexity  O(m^2) = O(n + m^2 + k)
        # overall: space complexity O(m)
        return result

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

        # Note: A heap only guarantees that the root is the max (max heap) or min (min heap).
        # The heap data structure only allows removing the root efficiently (O(log n))
        # The heap property says nothing about the relative order of leaves or internal nodes.
        # The smallest element could be anywhere in the leaves or internal nodes, not necessarily a leaf.
        # Thus for maxHeap, we need to add all of the elements to the tree
        # since we can't removed the smallest leaf as we go

        # space complexity: count for m unique elements worst case n elements O(n)
        count = defaultdict(int)

        # time complexity: iterate over list of n length O(n)
        for num in nums:
            count[num] += 1

        # space complexity: maxHeap must store all n elements O(n)
        maxHeap = []

        # time complexity: iteate over m unique elements worst case over n elements O(n)
        for num, freq in count.items():

            # time complexity: push onto heap O(log m) worst case O(log n) leading to best case O(m log m) worst case O(n log n) 
            heapq.heappush(maxHeap, (-freq, num))

        # space complexity: list of k elements worst case n elements best O(k) worst O(n)
        result = []

        # cannot iterate over array, as order is not guaranteed left to right
        # time complexity: iterate for k elements worst case n elements best O(k) worst O(n)
        for _ in range(k):

            # time complexity: pop top element O(log n) for k elements, worst case O(log n) for n elements, best case O(k log n) worst O(n log n)
            freq, num = heapq.heappop(maxHeap)
            result.append(num)

        # same as above
        # res = [num for _, num in (heapq.heappop(maxHeap) for _ in range(k))]

        # overall: time complexity O(n log n)
        # overall: space complexity O(n)
        return result

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

        # Note: A heap only guarantees that the root is the min (min heap) or max (max heap).
        # The heap data structure only allows removing the root efficiently (O(log n))
        # The heap property says nothing about the relative order of leaves or internal nodes.
        # The largest element could be anywhere in the leaves or internal nodes, not necessarily a leaf.
        # Thus for a minHeap, the root always holds the smallest element.
        # If we only remove the smallest element when heap as exceeded size k, 
        # the heap will always contains the k largest frequencies seen so far.

        # space complexity: count for m unique elements worst case n elements O(n)
        count = defaultdict(int)

        # time complexity: iterate over list of n length O(n)
        for num in nums: 
            count[num] += 1

        # space complexity: minHeap tracks k elements O(k)
        minHeap = []

        # time complexity: worst case iterate over n unique elements O(n)
        for num, freq in count.items(): 

            # time complexity: push onto heap O(log n) for n elements, leading to O(n log n) 
            heapq.heappush(minHeap, (freq, num)) 
            
            # if heap grows to size k + 1
            if len(minHeap) > k:

                # pop smallest element, heap will be back to size k
                # time complexity: # pop smallest O(log k) for worst case n elements, leading to O(n log k)
                heapq.heappop(minHeap) 
        
        # can iterate over heap array as only holding top k elements
        # time complexity: grab all k elements from minHeap worst case grab n elements O(n)
        result = [num for freq, num in minHeap]

        # for _, num in minHeap:
        #    result.append(num) 
        # same as above

        # overall: time complexity O(n log n)
        # overall: space complexity O(n)
        return result

    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    
        # Note: QuickSelect is a modified quicksort
        # Once the finalPartitionMarker is placed in its correct position, 
        # elements to the left and right are guaranteed to be smaller/larger
        # This avoids sorting the entire array and isolates the elements we need

        # In-place partition of array based on pivot value
        def partitionSection(left, right, randPivotElemIndex):
            
            # time complexity: partition processes m elements, n in worst case O(n)
            # Frequency of pivot element
            pivotElemFreq = frequency[unique[randPivotElemIndex]]

            # Move pivot to end
            # tuple unpacking in python, allows to swap two variables in a single line
            unique[randPivotElemIndex], unique[right] = unique[right], unique[randPivotElemIndex]
            
            # Index to partition larger elements to the left side of the section
            partitionIndex = left

            # Partition elements with freq more than pivotElemFreq to left
            # time complexity: iterates over unique elements between left and right segment O(m)
            for i in range(left, right):

                # Higher frequency -> "greater"
                if pivotElemFreq < frequency[unique[i]]:  

                    # swap larger element to left, sorting high to low
                    unique[i], unique[partitionIndex] = unique[partitionIndex], unique[i]
                    partitionIndex += 1

            # swap pivot to its final correct partitioned index
            # now elements to the right and left follow the conditions according to pivot element
            unique[partitionIndex], unique[right] = unique[right], unique[partitionIndex]
            return partitionIndex

        # time complexity: average recursion depth O(log m)
        # space complexity: recursion stack for in place partitioning on average O(log m)
        def quickSelectBinarySearchHelper(left, right, finalPartitionMarker):
            
            # Base Case: see 'For descending' below
            if left == right:
                return

            # Randomly choose a pivot index
            # differs from QuickSort "median-of-three" approach
            # random pivot is focused on finding the k-th smallest or largest
            # rather than fully sorting the array, random pivot avoids degrading to worst case O(n^2)
            randPivotElemIndex = random.randint(left, right)

            # Partition the array
            resultPivotElemIndex = partitionSection(left, right, randPivotElemIndex)
            
            # Base Case: see 'For descending' below
            if finalPartitionMarker == resultPivotElemIndex:
                return 
            
            # Binary Search Modification:
            # Selects next partition pivot
            # Recursively QuickSelect on partitioned section (left or right)
            # where finalPartitionMarker belongs to

            # finalPartitionMarker is in the left partition of resultPivotElemIndex
            elif finalPartitionMarker < resultPivotElemIndex:
                quickSelectBinarySearchHelper(left, resultPivotElemIndex - 1, finalPartitionMarker)
            
            # finalPartitionMarker is in the right partition of resultPivotElemIndex
            else:
                quickSelectBinarySearchHelper(resultPivotElemIndex + 1, right, finalPartitionMarker)

        # time complexity: iterate over list of n length O(n)
        frequency = defaultdict(int)
        for num in nums:
            frequency[num] += 1

        # QuickSelect BinarySearch to find the k most frequent elements
        unique = list(frequency.keys())
        n = len(unique)
        finalPartition = k - 1
        l, r = 0, n - 1

        # For descending:
        # say we have a list of 6 elements, we are trying to grab the largest 2 elements
        # if we do 2 - 1 we get 1.
        # so if we find we have partitioned and set index 1
        # we know that the elements 0 and 1 are the 2 largest elements
        # so we splice [:2] = [0, 1]
        quickSelectBinarySearchHelper(l, r, finalPartition)

        # overall: time complexity
        # overall: space complexity 
        return unique[:k]

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

        # Note: QuickSelect is a modified quicksort
        # Once the finalPartitionMarker is placed in its correct position, 
        # elements to the left and right are guaranteed to be smaller/larger
        # This avoids sorting the entire array and isolates the elements we need

        # In-place partition of array based on pivot frequency (low to high sorting)
        def partitionSection(left, right, randPivotElemIndex):
            
            # Frequency of pivot element
            pivotElemFreq = frequency[unique[randPivotElemIndex]]

            # Move pivot to end
            # tuple unpacking in python, allows to swap two variables in a single line
            unique[randPivotElemIndex], unique[right] = unique[right], unique[randPivotElemIndex]
            
            # Index to place smaller elements
            partitionIndex = left

            # Partition elements with freq less than pivotElemFreq to left
            # time complexity: iterates over unique elements between left and right segment O(m)
            for i in range(left, right):

                # Lower frequency -> "lower"
                if frequency[unique[i]] < pivotElemFreq:

                    # swap larger element
                    unique[i], unique[partitionIndex] = unique[partitionIndex], unique[i]
                    partitionIndex += 1

            # swap pivot to its final correct partitioned index
            # now elements to the right and left follow the conditions according to pivot element
            unique[partitionIndex], unique[right] = unique[right], unique[partitionIndex]
            return partitionIndex

        # QuickSelect helper for low to high sorting
        # Avg recursion depth: O(log m), space: O(log m)
        def quickSelectBinarySearchHelper(left, right, finalPartitionMarker):
            
            # Base Case: see 'For ascending' below
            if left == right:
                return

            # Randomly choose a pivot index
            # differs from QuickSort "median-of-three" approach
            # random pivot is focused on finding the k-th smallest or largest
            # rather than fully sorting the array, random pivot avoids degrading to worst case O(n^2)
            partitionElemIndex = random.randint(left, right)
            
            # Partition the array
            finalPartitionElemIndex = partitionPivot(left, right, partitionElemIndex)

            # Base Case: see 'For ascending' below
            if finalPartitionMarker == finalPartitionElemIndex:
                return

            # Binary Search Modification:
            # Selects next partition pivot
            # Recursively QuickSelect on partitioned section (left or right)
            # where finalPartitionMarker belongs to

            # finalPartitionMarker is in the left partition of resultPivotElemIndex
            elif finalPartitionMarker < finalPartitionElemIndex:
                quickSelectBinarySearchHelper(left, finalPartitionElemIndex - 1, finalPartitionMarker)
            
            # finalPartitionMarker is in the right partition of resultPivotElemIndex
            else:
                quickSelectBinarySearchHelper(finalPartitionElemIndex + 1, right, finalPartitionMarker)

        # time complexity: iterate over list of n length O(n)        
        frequency = defaultdict(int)
        for num in nums:
            frequency[num] += 1

        # Quickselect to find the k most frequent elements
        unique = list(frequency.keys())
        n = len(unique)
        finalPartition = n - k
        l, r = 0, n - 1

        # For ascending:
        # say we have a list of 6 elements, we are trying to grab the largest 2 elements
        # if we do 6 - 2 we get 4.
        # so if we find we have partitioned and set index 4
        # we know that the elements 4 and 5 are the 2 largest elements
        # so we splice [6-2:] = [4:] = [4, 5]
        # quickSelectBinarySearchHelper(left, right, finalPartitionMarker)
        quickSelectBinarySearchHelper(l, r, finalPartition)

        # overall: time complexity
        # overall: space complexity
        return unique[n - k:]

    def topKFrequent(self, nums: List[int], k:int) -> List[int]:
            
        # space complexity: frequency count for unique integers O(m) 
        # time complexity: iterate over list of n integers O(n)
        count = defaultdict(int)
        for key in nums:

            # time complexity: insertion operation takes constant O(1)
            count[key] += 1

        # numBuckets equal to length to account for max possible frequency count
        # the case where list is full of only 1 element O(n)
        # + 1 for case of element with 1 list, need bucket of frequency 0 and bucket of frequency 1
        numBuckets = len(nums) + 1

        # below is saying: create a list of empty lists numBuckets amount of times 
        # time complexity: iterating to set empty list for each bucket
        # space complexity: creating O(n) bucket lists
        freqBuckets = [[] for i in range(numBuckets)]

        # time complexity: iterate over frequency list for m unique integer tuples (int, occurrences) O(m) 
        for int, occurrences in count.items():

            # time complexity: insert operation takes constant O(1)
            freqBuckets[occurrences].append(int)

        # space complexity: grabbing top k integers O(k)
        res = []

        # time complexity: iterate over n buckets O(n)
        for i in range(len(freqBuckets) - 1, 0, -1):
            
            # time complexity: iterate over all entries in current bucket O(n)
            for num in freqBuckets[i]:
                
                # time complexity: insert operation takes constant O(1)
                res.append(num)
                
                # time complexity: continue while less than k integers have been grabbed O(k)
                if len(res) == k:
                    return res

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

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

        # space complexity: result array of length n O(n)
        res = [0] * len(nums)

        # time complexity: iterate over list of n integers O(n) 
        for i in range(len(nums)):

            # starting value
            product = 1

            # time complexity: iterate over list of n integers O(n)
            for j in range(n):

                # skip current index i while multiplying
                if i != j:

                    # time complexity: multiplication operation takes constant O(1)
                    product *= nums[j]
                
            # time complexity: insert operation takes constant O(1)
            res[i] = product
        
        # overall: time complexity  O(n^2)
        # overall: space complexity O(n)
        return res

    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        # space complexity: prefix, postfix, and result arrays to calculate and store final value for n integers O(n) = O(3n)
        prefix = [1] * len(nums)
        postfix = [1] * len(nums)
        res = [1] * len(nums)

        # Compute prefix products
        # time complexity: iteration over list of n length O(n)
        for i in range(1, len(nums)):
            
            # time complexity: lookup + multiplication operations take constant O(1)
            # (prefix of i) = (prefix of i - 1) * (nums[i - 1])
            prefix[i] = prefix[i - 1] * nums[i - 1]

        # Compute postfix products
        # time complexity: iteration over list of n length O(n)
        for i in range(n - 2, -1, -1):

            # time complexity: lookup + multiplication operations take constant O(1)
            # (postfix of i) = (postfix of i + 1) * (nums[i + 1])
            postfix[i] = postfix[i + 1] * nums[i + 1]

        # Combine prefix and postfix products
        # time complexity: iteration over list of length n O(n)
        for i in range(n):

            # time complexity: lookup + multiplication operations take constant O(1)
            # (product except self of i) = (prefix of i) * (postfix of i)
            res[i] = prefix[i] * postfix[i]


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

    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        # instantiate to 1, start prefix calculation at res[1], prefix of res[0] is always 1
        # space complexity: array to store results for n integers O(n) 
        res = [1] * len(nums)

        # Compute prefix products in res
        # time complexity: iterate over list of size n O(n)
        for i in range(1, len(nums)):

            # time complexity:
            # (prefix of i) = (prefix of i - 1) * (num at i - 1)
            res[i] = res[i - 1] * nums[i - 1]

        # accumulate running postfix through reverse iteration
        # postfix starts at 1, the postfix of len(n) - 1
        postfix = 1

        # start iteration at (len(n)-1), postfix of last integer will always be 1
        # time complexity: iterate over list of size n in reverse O(n)
        for i in range(len(nums) - 1, -1, -1):
            
            # (product except i) = (prefix of i) * (postfix of i)
            res[i] *= postfix
            
            # (postfix of i - 1) = (postfix of i) * (num at i) 
            postfix *= nums[i]

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

    def isValidSudoku(self, board: List[List[str]]) -> bool:
        
        # time complexity: iterating over row, col, or box (flattened) of n length (+ O(n)) not (* O(n))
        def isValidLine(line: List[str]) -> bool:
            seen = set()
            for num in line:
                if num != ".":
                    if num in seen:
                        return False
                    seen.add(num)
            return True

        # time complexity: iterating over board with n rows of length n and validating O(n^2)
        for row in board:
            if not isValidLine(row):
                return False

        # time complexity: iterating over board with n columns of length n and validating O(n^2)
        for c in range(9):
            column = []
            for r in range(9):
                column.append(board[r][c])
            if not isValidLine(column):
                return False

        # time complexity: iterating over n boxes of flattened length n <- (√n x √n) and validating O(n^2)
        for box_row in range(0, 9, 3):
            for box_col in range(0, 9, 3):
                line = []
                for r in range(box_row, box_row + 3):
                    for c in range(box_col, box_col + 3):
                        line.append(board[r][c])

                if not isValidLine(line):
                    return False

        # overall: time complexity O(n^2) = (3 * n^2)
        # overall: space complexity O(1)
        return True

    def isValidSudoku(self, board: List[List[str]]) -> bool:
        
        # space complexity: hashsets for rows, columns, and flattened boxes of n length O(n) = O(3n)
        cols = defaultdict(set)
        rows = defaultdict(set)
        grids = defaultdict(set)

        # time complexity: iterating over all cells (r * c) O(n^2)
        for r in range(9):
            for c in range(9):
                
                tmp = board[r][c]
                if tmp != ".":

                    # indexing box sets by tuple key (r/3, c/3)
                    gridTuple = (r // 3, c // 3)

                    # time complexity: lookup operation for element to corresponding sets in constant O(1)
                    if (tmp in rows[r] or 
                        tmp in cols[c] or 
                        tmp in grids[gridTuple] ):
                        return False
                    
                    # time complexity: insert operation for new element to corresponding sets in constant O(1)
                    cols[c].add(tmp)
                    rows[r].add(tmp)
                    grids[gridTuple].add(tmp)

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

    def isValidSudoku(self, board: List[List[str]]) -> bool:
        
        # space complexity: hashsets for rows, columns, and flattened boxes of n length O(n) = O(3n)
        rows = [[], [], [], [], [], [], [], [], []]
        col = [[], [], [], [], [], [], [], [], []]
        grids = [[], [], [], [], [], [], [], [], []]

        # time complexity: iterating over all cells (r * c) O(n^2)
        for r in range(9):
            for c in range(9):
                
                tmp = board[r][c]
                if tmp != ".":  

                    # indexing box sets by unique int calculation 
                    #  (j//3) = 0, 1, 2
                    #  (3 * (i//3)) = 0, 3, 6
                    #    0 1 2
                    # 0  0 1 2
                    # 3  3 4 5
                    # 6  6 7 8
                    # leads to 0-8 index indexing
                    gridKey = (3 * (i//3)) + (j//3)

                    # time complexity: lookup operation for element to corresponding sets in constant O(1)
                    if (tmp in rows[r] or 
                        tmp in col[c]  or 
                        tmp in grids[gridKey]):
                        return False

                    # space complexity: lookup operation for new element to corresponding sets in constant O(1)
                    col[c].append(tmp)
                    rows[r].append(tmp)
                    grids[gridKey].append(tmp)
        
        # overall: time complexity O(n^2)
        # overall: space complexity  O(n)
        return True

    def longestConsecutive(nums: List[int]) -> int:
        
        longest = 0

        # time complexity: Iterate over list of n length O(n)
        for num in nums:

            currLen = 1
            
            # time complexity: Iterate over potential n consecutive integers O(n)
            # time complexity: Lookup in list takes O(n)
            # time complexity: O(n^2)
            while num + currLen in nums:
                currLen += 1

            # compare to global max
            longest = max(longest, currLen)

        # Overall time complexity: O(n^3) for worst-case where we scan sequences n times for n numbers
        # Space complexity: O(1)
        return longest

    def longestConsecutive(nums: List[int]) -> int:
        
        # space complexity: hashmap of list of n length O(n)
        seqLen = defaultdict(int)
        longest = 0

        # Handle duplicates
        nums = set(nums)  

        # Iterate over unique numbers
        for num in nums:
            # Skip if num is already part of an existing sequence
            # Fetch lengths of neighboring sequences
            leftContinentLenFromBoundary = seqLen[num - 1]
            rightContinentLenFromBoundary = seqLen[num + 1]

            # Calculate new sequence length
            bridgedLen = 1 + leftContinentLenFromBoundary + rightContinentLenFromBoundary

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

            # Update the global max
            longest = max(longest, bridgedLen)

        return longest

def longestConsecutive(self, nums: List[int]) -> int: 
    
    # space complexity: set for list of n length O(n)
    numSet = set(nums)
    longest = 0

    # time complexity: iterate over list of n length O(n)
    for num in numSet:

        # found start of a run
        # time complexity: lookup operation takes constant O(1)
        if (num - 1) not in numSet: 

            # rummy run until missing an element
            currLen = 1
            # time complexity: iterate over m sequence worst case n sequence O(n), lookup O(1), leading to O(n)
            while (num + currLen) in numSet:
                currLen += 1 

            # validate with global max sequence
            longest = max(longest, currLen)

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

    def longestConsecutive(self, nums: List[int]) -> int:
        
        if len(nums) == 0:
            return 0

        # Union-Find Initialization:
        
        # Stores parent of each number
        # space complexity: hashmap of size n O(n)
        parent = {}  

        # Stores the size of connected components
        # space complexity: hashmap of size n O(n)
        size = {}    

        # Find operation with path compression
        # time complexity: Amortized O(α(n)) per operation
        def find(x):

            # if the parent of x is not itself, we have not reached the representative  
            if parent[x] != x:

                # Path compression
                # set parent of curr, to parent of parent
                parent[x] = find(parent[x])

            # return representative of group
            # either return self
            # or return parent of parent
            return parent[x]

        # Union operation with size optimization
        # time complexity: Amortized O(α(n)) per operation
        def union(x, y):

            # grab representatives of both x and y
            rootX = find(x)
            rootY = find(y)

            # trees are not already connected
            if rootX != rootY:

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

                # x tree is larger
                if ySize < xSize:
                    # attach smaller tree to larger tree
                    parent[rootY] = rootX
                    # add smaller tree size to larger tree
                    size[rootX] += size[rootY]

                # y tree is larger
                else:
                    # attach smaller tree to larger tree
                    parent[rootX] = rootY
                    # add smaller tree size to larger tree
                    size[rootY] += size[rootX]

        # Initialize Union-Find structure: 
        # Set all parents to self
        # time complexity: iterate over list of n length O(n)
        for num in nums:
            if num not in parent:
                parent[num] = num
                size[num] = 1

        # Join consecutive numbers: 
        # Union operation on sequences
        # time complexity: iterate over list of n length O(n)
        for num in nums:
            if num + 1 in parent:
                union(num, num + 1)
        
        # return largest group

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return max(size.values())