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

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

        # sc: hashmap relative to input O(n)
        count = defaultdict(int)

        # tc: iterate over list O(n)
        for num in nums:

            # tc: in operation constant O(1)
            if count[num] >= 1:
                return True
            # tc: put operation constant O(1)
            count[num] += 1

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

    def containsDuplicate(self, nums: List[int]) -> bool:
        
        # sc: set relative to input O(n)
        seen = set()

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

            # tc: in operation O(1)
            if n in seen:
                return True
            # tc: add operation O(1)
            seen.add(n)
            
        # overall: tc O(n)
        # overall: sc O(n)
        return False

    def containsDuplicate(self, nums: List[int]) -> bool:
        
        # Create unique set
        # tc: iterate over original n list O(n)
        # sc: set relative to input O(n)
        unique = set(nums)

        # Compare if unique set is different than original list
        # tc: length operation constant 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: python (2.3-3.10) TimSort, Python (3.11+) PowerSort Worst/Avg: O(n log n), Best: O(n)
        # sc: sorts in place, no extra memory O(1)
        nums.sort()

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

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

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

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

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

        # tc: iteration over char count O(n)
        for value in count.values():

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

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

        # Check: mismatch length
        if len(s) != len(t):
            return False

        # tc: single iterate over both strings at same time O(n)
        for i in range(len(s)):
            count[ord(s[i]) - ord('a')] += 1
            count[ord(t[i]) - ord('a')] -= 1

        # tc: iterate over count array length 26 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:
        
        # Note:
        # Why Normalization is required in real life?
        # Because Unicode allows characters to be represented in multiple valid ways.
        # Why? Doesn't that make it more complicated?
        # Yes, but the alternative would be needing millions of characters:
        # Some languages have hundred of diacritics (e.g, dots, tildes, strokes) 
        # that can be superimposed to create the letters for their alphabet.
        # When Unicode was created, it had to support existing encodings (Latin-1, MacRoman, Windows-1252)
        # which have pre-composed/defined characters (é, ñ, ü) as well as other encodings as mentioned above 
        # with use diacritics.
        # The solution is to allow a composing system, that instead of pre-encoding every possible combination (infinite)
        # instead we use base characters + combining marks. (letter + marks)
        
        # Thus, we need normalization to allow visually equal characters which are built/composed in different
        # ways to be equal.

        # 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.
        
        # Without normalization (built/composed differently do not equal, even if visually equal):
        #   "é" != "e\u0301"
        
        # With normalization (build/composed differently do equal, because they are visually equal):
        #   "é" == "e\u0301"


        # NFC = Normalization Form C, where the C means Canonical Composition
        # Combines characters into their precomposed forms when possible.
        # So e +  ́ = é.
        # allows for even comparison

        # NFD = Normalization Form C, where the C means Canonical Decomposition
        # so the inverse

        # tc: iteration relative to input O(n)
        # sc: 2 string copies relative to input O(n)
        import unicodedata
        s = unicodedata.normalize("NFC", s)
        t = unicodedata.normalize("NFC", t)

        # early len check
        if len(s) != len(t):
            return False

        # sc: dictionary possibly up to number of distinct characters O(k)
        count = defaultdict(int)

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

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

        # tc: O(k) over unique keys (≤ n)
        for value in count.values():
            if value != 0:
                return False

        # overall: tc O(n)
        # overall: sc O(k) <= O(n)
        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

        N/A

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

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        anaGroup = {}
        
        for word in strs:
            
            charCount = [0] * 26
            for char in word:
                charCount[ord(char) - ord('a')] += 1
            
            # BUG: 
            # Attempted to hash mutable list charCount
            if charCount not in anaGroup:
                anaGroup[charCount] = []
            
            anaGroup[charCount].append(word)
        
        return list(anaGroup.values())

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        groupAna = {}

        for s in strs:
            count = defaultdict(int)

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

            tupKey = tuple(count)

            # BUG: 
            # hashmaps are not sorted
            # so tuple will vary (e.g., "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]]:
        
        # Note: 
        # Tuples immutable, allowing them to be hashed
        # Array allows for constant ordered representation

        # sc: store k chars for n words O(n * k)
        anaGroup = {}

        # tc: iterate over list O(n) 
        for word in strs:
            
            # sc: array for 26 O(1)
            charCount = [0] * 26  
            
            # tc: iterate over string k length O(k)
            for char in word:
                charCount[ord(char) - ord('a')] += 1
            
            # sc: array of 26 to tuple O(1)
            key = tuple(charCount)  
            
            # tc: in operation O(1) 
            if key not in anaGroup:
                anaGroup[key] = []  

            # tc: put operation 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())

    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        
        def partitionSection(left, right, randIndex):
            freqPartition = frequency[unique[randIndex]]
            leftPartition = left
            unique[randIndex], unique[right] = unique[right], unique[randIndex]

            for i in range (left, right):
                if frequency[unique[i]] > freqPartition:
                    unique[i], unique[leftPartition] = unique[leftPartition], unique[i]
                    leftPartition += 1
            
            unique[right], unique[leftPartition] = unique[leftPartition], unique[right]

            return leftPartition

        def quickSelectBinarySearchHelper(left, right, finalMarker):
            
            # ran out of space
            if left == right:
                return

            randIndex = random.randint(left, right)
            resIndex = partitionSection(left, right, randIndex)

            if resIndex == finalMarker:
                return

            # BUG:
            # this format is confusing
            # we are searching for the finalMarker, so always have that on 
            # the left.
            # The correct order should be:
            # if the finalMarker is less than the result, then we shift right
            # but because of the confused order, we are doing the reverse
            # INSTEAD:
            # elif finalMarker < resIndex 
            #   quickSelectBinarySearchHelper(left, resIndex-1, finalMarker)
            elif resIndex < finalMarker:
                quickSelectBinarySearchHelper(left, resIndex-1, finalMarker)
            else:
                quickSelectBinarySearchHelper(resIndex+1, right, finalMarker)

        frequency = defaultdict(int)
        for n in nums:
            frequency[n] += 1
        
        unique = list(frequency.keys())
        n = len(unique)
        l, r = 0, n-1

        finalIndex = k-1
        quickSelectBinarySearchHelper(l, r, finalIndex)
        return unique[:k]

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

        # MinHeap: 
        # Heap only guarantees that the root is the min or max, and
        # provides no guarantee about the relative order of nodes. 
        # The minHeap root will hold the smallest element,
        # as we iterate we will add elements, 
        # and we only remove the root/smallest element when heap exceeds size k.
        # This ensures the heap will hold the k most frequent
        # elements we have seen so far

        # sc: freq count for list, m unique elements in worst case O(n)
        freq = defaultdict(int)

        # Calculate freq count for each element
        # tc: iterate over list O(n)
        for num in nums: 
            freq[num] += 1

        # sc: minHeap holds smallest k elements O(k)
        minHeap = []

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

            # tc: push operation O(log n)
            heapq.heappush(minHeap, (freq, num)) 
            
            # if heap grows to size k + 1, pop least freq root so we keep the k most freq elements
            if len(minHeap) > k:
t6
                # tc: pop smallest element O(log k)
                heapq.heappop(minHeap) 
        

        # alternative expanded loop:
        # tc: grab top k occurring elements from minHeap, worst case grab n elements O(n)
        result = []
        for (_, num) in minHeap:
            result.append(num) 

        # alternative shorter notation
        # result = [num for freq, num in minHeap]

        # overall: tc O(n log n)
        # overall: sc O(n)
        return result

    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    
        # QuickSelect Modified QuickSort:
        # QuickSort sorts based on a partitioned element, whereas when QuickSort
        # complete, everything to the left of the partitioned element is less than it
        # and everything to the right of the partitioned element is greater than it.
        # QuickSelect uses a finalPartitionMarker marks the final expected correct position, 
        # where at which point it stops and elements to the left and right of finalPartitionMarker
        # are guaranteed to be smaller/larger.
        # This avoids sorting the entire array by only sorting as many elements until the 
        # finalPartitionMarker is in the correct place which
        # isolates the minimum elements needed to complete the task

        # Helper: 
        # In place partition of subarray [left,right] relative to random pivot index value
        def partitionSection(left, right, randPivotElemIndex):
            
            # tc: subarray m elements, n in worst case O(n)
            
            # Frequency count of random pivot element
            pivotElemFreq = frequency[unique[randPivotElemIndex]]

            # Move random pivot element to end
            # Tuple unpacking in python allows swapping two variables
            unique[randPivotElemIndex], unique[right] = unique[right], unique[randPivotElemIndex]
            
            # Left index to partition/move larger elements to the left boundary of subarray
            partitionIndex = left

            # tc: iterate over subarray, n in worst case O(n)
            for i in range(left, right):

                # Partition elements with frequencies above the pivotElem Freq (pivotElemFreq < freq),
                # move them to left (move larger elements greater than the pivot to the left of the pivot)
                if pivotElemFreq < frequency[unique[i]]:  
                    
                    # Slicing:
                    # Placing larger freq element on left [high... low] 
                    # allows [:k] to grab the first top k freq elements
                    unique[i], unique[partitionIndex] = unique[partitionIndex], unique[i]
                    partitionIndex += 1

            # set pivot to correct partitioned index,
            # elements left and right of pivot follow [greater... pivot ... lesser]
            unique[partitionIndex], unique[right] = unique[right], unique[partitionIndex]
            return partitionIndex

        # Helper: 
        # Wrapper function that continues to pick random partition element until we have 
        # placed some element at the "finalPartitionMarker" index
        # tc: average recursion depth O(log m)
        # sc: recursion stack for in place partitioning on average O(log m)
        def quickSelectBinarySearchHelper(left, right, finalPartitionMarker):
            
            # Base Case:
            if left == right:
                return

            # Random pivot index:
            # Differs from QuickSort "median-of-three" approach.
            # Random pivot focuses on finding the kth smallest or largest,
            # rather than fully sorting the array, and using random pivot avoids 
            # degrading to worst case O(n^2)
            randPivotElemIndex = random.randint(left, right)

            # Partition subarray
            resultPivotElemIndex = partitionSection(left, right, randPivotElemIndex)
            
            # Base Case: Random partition marker ended up in correct place
            if finalPartitionMarker == resultPivotElemIndex:
                # -> allows us to grab k top freq count by [:k]
                return 
            
            # Binary Search Modification:
            # Selects next subarray and partition pivot
            # resultPivotElemIndex must recurse towards side where finalPartitionMark is on

            # Result was to the right of final expected, 
            # search to the left of the result: [left, resultPivot-1]
            elif finalPartitionMarker < resultPivotElemIndex:
                quickSelectBinarySearchHelper(left, resultPivotElemIndex - 1, finalPartitionMarker)
            
            # Result was to the left of final expected,
            # search to the right of the result: [resultPivot+1, right]
            else:
                quickSelectBinarySearchHelper(resultPivotElemIndex + 1, right, finalPartitionMarker)

        # Calculate freq count for each element
        # tc: iterate over list O(n)
        # sc: allocate for list, n unique elements worst case O(n)
        frequency = defaultdict(int)
        for num in nums:
            frequency[num] += 1

        # Top Kth Elements Indexing: Top 2 elements are indexes [0, 1]
        # [9 7 4 3 1]
        #  0 1 2 3 4
        finalPartition = k - 1

        # Unique count to sort by during partitioning
        unique = list(frequency.keys())
        n = len(unique)
        l, r = 0, n - 1

        # For High to Low (descending) indexing:
        # with list of 6 elements, grab largest 2 elements
        # 2 - 1 = 1 (our 2nd largest)
        # splice [:2] = [0, 1]
        quickSelectBinarySearchHelper(l, r, finalPartition)

        # Pivot is now in the correct partitioned index.
        # Elements left and right of pivot follow [greater... pivot ... lesser]
        # Slice the first k to grab the top k elements

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

    def topKFrequent(self, nums: List[int], k:int) -> List[int]:
        
        # BucketSort:
        # Grouping values by freq count into buckets.
        # Allows us to iterate over most freq buckets and grab top k elements

        # Calculate freq count for each element
        # tc: iterate over list of n integers O(n)
        # sc: frequency count for unique integers O(m) 
        count = defaultdict(int)
        for key in nums:
            count[key] += 1

        # numBuckets index = items with that frequency count
        # numBuckets must account for max freq count case, where list is full of only 1 element
        # numBuckets must account for empty list, (but still needs a bucket index 0), so we need
        # len(num)+1,
        # empty: 1 bucket: [0] representing empty group
        # else: list of len 5, 6 buckets: [0, 1, 2, 3, 4, 5] each representing length group,
        # with max freq count of 5
        numBuckets = len(nums) + 1

        # list of empty lists, numBucket amount of times 
        # tc: iterate over list length O(n)
        # sc: create len(list)+1 buckets O(n)
        freqBuckets = [[] for i in range(numBuckets)]

        # tc: iterate over frequency list for m unique integer tuples (int, occurrences) O(m) 
        for int, occurrences in count.items():
            freqBuckets[occurrences].append(int)

        # sc: grabbing top k integers, n worst case O(k)
        res = []

        # tc: iterate over len(list)+1 buckets O(n)
        for i in range(len(freqBuckets) - 1, 0, -1):
            
            # tc: iterate over all elements in curr bucket O(m)
            for num in freqBuckets[i]:
                
                # tc: insert operation O(1)
                res.append(num)
                
                # tc: continue while less than k elements grabbed O(k)
                if len(res) == k:
                    return res

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

    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
        # tc: iterate list O(n)
        for i in range(1, n):
            
            # calculate prefix of i = (prefix of i - 1) * (nums[i - 1])
            prefix[i] = prefix[i - 1] * nums[i - 1]

        # Postfix
        # postfix starts at 1 = the postfix of len(n) - 1
        # start reverse iteration at: len(n) - 2
        # tc: iterate list O(n)
        for i in range(n-2, -1, -1):

            # calculate postfix of i = (postfix of i + 1) * (nums[i + 1])
            postfix[i] = postfix[i + 1] * nums[i + 1]

        # Result
        # tc: iterate list O(n)
        for i in range(n):

            # calculate product except self for i = (prefix of i) * (postfix of i)
            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: result array O(1) 
        res = [1] * n

        # Running Prefix: 
        # Generated through iteration with a starting prefix for the first element being 1, 
        # ignore and start at element 2 (index 1)

        # tc: iterate list O(n)
        for i in range(1, n):

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

        # Running Postfix: 
        # Generated through reverse iteration with a starting postfix for the last element is 1, 
        # start at the last element (index n-1)
        postfix = 1

        # tc: iterate list in reverse O(n)
        for i in range(n-1, -1, -1):
            
            # calculate product except self for i = (prefix of i) * (postfix of i)
            res[i] *= postfix
            
            # update postfix = (postfix of i) * (num at i) 
            postfix *= nums[i]

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

    def isValidSudoku(self, board: List[List[str]]) -> bool:

        # BUG:
        # defaultdict argument must be callable or None
        # --------
        # Differences: [], list, set:
        # []: instance of the list, not callable
        # list: class creates a new list object when called, callable
        # set: class creates a new set object when called, callable

        # Instead:
        # defaultdict(set)
        
        rows = defaultdict([])
        cols = defaultdict([])
        boxs = defaultdict([])

        for r in range(9):
            for c in range(9):
                tmp = board[r][c]

                if tmp != ".":

                    boxKey = (r//3, c//3)

                    if (tmp in rows[r] or
                        tmp in cols[c] or
                        tmp in boxs[boxKey]):
                        return False

                    rows[r].add(tmp)
                    cols[c].add(tmp)
                    boxs[boxKey].add(tmp)
        return True

    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = defaultdict(set)
        cols = defaultdict(set)
        boxs = defaultdict(set)


        for r in range(9):
            for c in range(9):
                tmp = board[r][c]

                if tmp != ".":

                    # BUG:
                    # will create 81 possible boxes (9 rows * 9 columns)
                    # Instead:
                    # boxKey = tuple((r//3, c//3))
                    # creates 9 boxes 
                    # (9//3), (9//3) = (1-3, 1-3) = 9 possibilities
                    boxKey = tuple((r, c))

                    if (tmp in rows[r] or
                        tmp in cols[c] or
                        tmp in boxs[boxKey]):
                        return False

                    rows[r].add(tmp)
                    cols[c].add(tmp)
                    boxs[boxKey].add(tmp)

        return True

    def isValidSudoku(self, board: List[List[str]]) -> bool:
        
        # Dictionaries And Immutable/Hashable Keys:
        # Since dictionaries use hashing, we can use any object that is 
        # both immutable and hashable as the key, 
        # which allows us to create tuples for our keys

        # sc: dictionary for rows, columns, boxes O(n)
        cols = defaultdict(set)
        rows = defaultdict(set)
        grids = defaultdict(set)

        # tc: iterate over grid (r * c) O(n^2)
        for r in range(9):
            for c in range(9):
                
                cell = board[r][c]
                if cell != ".":

                    # index between 9 box sets by tuple key (r/3, c/3)
                    gridTuple = (r // 3, c // 3)

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

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

    def isValidSudoku(self, board: List[List[str]]) -> bool:
        
        # Array of Array vs Dictionary:
        # Due to the overhead of the dictionary functions,
        # for a small use case such as 9x9 using direct array of arrays is faster.
        # For larger use cases though, dictionary would be more optimal.

        # sc: arrays for rows, columns, boxes O(n)
        rows = [[], [], [], [], [], [], [], [], []]
        col = [[], [], [], [], [], [], [], [], []]
        grids = [[], [], [], [], [], [], [], [], []]

        # tc: iterate over grid (r * c) O(n^2)
        for r in range(9):
            for c in range(9):
                
                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

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

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

                    # sc: put operation O(1)
                    col[c].append(cell)
                    rows[r].append(cell)
                    grids[boxKey].append(cell)
        
        # overall: tc O(n^2)
        # overall: sc  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(self, nums: List[int]) -> int:

        # BUG:
        # need to check for empty list case
        # or else max(size.values()) will return error

        # Instead:
        # if len(nums) == 0
        #   return 0

        parent = {}
        size = {}

        def find(x):

            if parent[x] != x:
                parent[x] = find(parent[x])

            return parent[x]


        def union(x, y):
            root_x = find(x)
            root_y = find(y)

            if root_x != root_y:

                size_x = size[root_x]
                size_y = size[root_y]

                if size_x < size_y:
                    parent[root_x] = root_y
                    size[root_y] += size[root_x]
                else:
                    parent[root_y] = root_x
                    size[root_x] += size[root_y]

        setNum = set(nums)
        for n in setNum:
            parent[n] = n
            size[n] = 1

        for n in setNum:
            if (n+1) in parent:
                union(n, n+1)

        return max(size.values())

    def longestConsecutive(nums: List[int]) -> int:
        
        # Continent Boundaries:
        # If we imagined a number line, with runs of consecutive numbers being colored
        # different colors, we could have:
        #
        #    0 1   4 5 6 7 8   11 12 13 14  19 
        #    ***   #########   -----------  ++ 
        #
        # Continent boundaries builds the lengths of these 'continents' as we iterate
        # by checking if a number has left and right neighbors who already have a 
        # continent length, and then just joins the continent lengths by 'bridging the continents'
        # by adding both the left and right neighbor continent lengths and adding +1
        # to the total length:
        #
        #     leftContinent_length   "+1 Bridge"   rightContinent_length 

        longest = 0

        # sc: hashmap of list of n length O(n)
        seqLen = defaultdict(int)

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

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

            # Calculate new bridged 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)

        # 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: iterate list O(n)
    for runStartCandidate in numSet:

        # Check if we have found start of a new run: the left most element of a run
        # tc: lookup constant O(1)
        if (runStartCandidate-1) not in numSet: 

            currRunLen = 1

            # Check if run's next element exists
            # tc: iterate over run O(n)
            while (runStartCandidate + currRunLen) in numSet:
                # Point to next sequential element
                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: dictionary for list O(n)
        parent = {}  

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

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

            # Find Representative:
            # If the parent of x is not itself, keep going up, we have not reached the representative  
            if parent[x] != x:

                # Path compression:
                # Set parent of current, to the parent of its eventual parent,
                # By the end the representative will be the parent of all children
                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 with size optimization
        # tc: Amortized O(α(n)) per operation
        def union(x, y):

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

            # If trees do not share representative
            if rootX != rootY:

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

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

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

            # Ignore duplicates that have already been initialized
            if num not in parent:
                # 1. Set all parents to self
                # 2. Set all sizes to 1
                parent[num] = num
                size[num] = 1

        # Move elements into groups of runs:
        # Merge consecutive number sequences as trees
        # tc: iterate list O(n)
        for num in nums:
            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