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