# Universal Counting Template
def counting_pattern(arr):
    count = {}  # or collections.defaultdict(int)
    result = []
    
    # Count frequency
    for item in arr:
        count[item] = count.get(item, 0) + 1
        # or count[item] += 1 with defaultdict
    
    # Process based on frequency
    for key, freq in count.items():
        if meets_condition(freq):
            result.append(key)
    
    return result

# Examples: LC 49, LC 242, LC 451, LC 347, LC 692

# Two Sum Pattern Template
def two_sum_pattern(nums, target):
    seen = {}  # {value: index}
    
    for i, num in enumerate(nums):
        complement = target - num
        
        if complement in seen:
            return [seen[complement], i]
        
        seen[num] = i
    
    return []

# Variations:
# - Multiple pairs: collect all instead of returning first
# - K-diff pairs: check for num+k and num-k
# - Examples: LC 1, LC 167, LC 15, LC 532, LC 1010

# Prefix Sum Pattern Template
def prefix_sum_pattern(nums, target):
    prefix_sum = 0
    sum_count = {0: 1}  # {sum: count/index}
    result = 0

    for num in nums:
        prefix_sum += num

        # Check if (prefix_sum - target) exists
        if prefix_sum - target in sum_count:
            result += sum_count[prefix_sum - target]

        # Update current prefix sum count
        sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1

    return result

# For max length problems, store index instead of count:
# sum_index = {0: -1}, then calculate i - sum_index[prefix_sum - target]
# Examples: LC 560, LC 325, LC 525, LC 523

# Sliding Window with HashMap Template
def sliding_window_hashmap(s, pattern):
    if len(pattern) > len(s):
        return []
    
    pattern_count = {}
    window_count = {}
    
    # Count pattern frequency
    for char in pattern:
        pattern_count[char] = pattern_count.get(char, 0) + 1
    
    left = 0
    result = []
    
    for right in range(len(s)):
        # Expand window
        char = s[right]
        window_count[char] = window_count.get(char, 0) + 1
        
        # Contract window if needed
        while window_size_condition_met():
            # Check if current window is valid
            if window_count == pattern_count:
                result.append(left)
            
            # Remove leftmost character
            left_char = s[left]
            window_count[left_char] -= 1
            if window_count[left_char] == 0:
                del window_count[left_char]
            left += 1
    
    return result

# Examples: LC 3, LC 76, LC 438, LC 567

# Caching/Memoization Template
class CacheTemplate:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> value
        self.usage = {}  # key -> usage_info
    
    def get(self, key):
        if key in self.cache:
            self.update_usage(key)
            return self.cache[key]
        return -1
    
    def put(self, key, value):
        if len(self.cache) >= self.capacity:
            self.evict()
        
        self.cache[key] = value
        self.update_usage(key)
    
    def update_usage(self, key):
        # Update usage tracking
        pass
    
    def evict(self):
        # Remove least recently/frequently used
        pass

# Examples: LC 146 (LRU), LC 460 (LFU)

# Graph with HashMap Template
def graph_hashmap_pattern(graph_input):
    # Build adjacency list/map
    graph = {}  # node -> [neighbors] or node -> {neighbor: weight}
    
    for edge in graph_input:
        node1, node2 = edge[0], edge[1]
        if node1 not in graph:
            graph[node1] = []
        if node2 not in graph:
            graph[node2] = []
        
        graph[node1].append(node2)
        graph[node2].append(node1)  # for undirected
    
    # Process using DFS/BFS with visited tracking
    visited = set()
    result = []
    
    def dfs(node):
        if node in visited:
            return
        
        visited.add(node)
        result.append(node)
        
        for neighbor in graph.get(node, []):
            dfs(neighbor)
    
    return result

# Examples: LC 133, LC 200, LC 694, LC 1257

# Python - SortedDict (from sortedcontainers)
from sortedcontainers import SortedDict

# TreeMap Pattern Template
def treemap_pattern(data):
    # TreeMap maintains sorted order by key
    tree_map = SortedDict()

    # Basic operations
    tree_map[key] = value           # O(log n) insert
    value = tree_map.get(key)       # O(log n) search
    del tree_map[key]               # O(log n) delete

    # Ordered operations
    first_key = tree_map.keys()[0] if tree_map else None    # Min key
    last_key = tree_map.keys()[-1] if tree_map else None    # Max key

    # Range queries
    # Get all keys in sorted order
    for key in tree_map.keys():
        process(key, tree_map[key])

    # Find floor/ceiling (closest keys)
    # bisect_left/bisect_right for approximate match
    import bisect
    keys = list(tree_map.keys())
    idx = bisect.bisect_left(keys, target)  # Floor index

    return tree_map

# Examples: LC 853, LC 729/731/732, LC 846, LC 352, LC 981

// Java - TreeMap Pattern
import java.util.*;

// TreeMap Pattern Template
public void treeMapPattern(int[] data) {
    // TreeMap maintains sorted order by key (Red-Black Tree)
    TreeMap<Integer, Integer> treeMap = new TreeMap<>();

    // Basic operations - O(log n)
    treeMap.put(key, value);        // Insert
    Integer value = treeMap.get(key);  // Search
    treeMap.remove(key);            // Delete

    // Ordered operations - O(log n)
    Integer firstKey = treeMap.firstKey();   // Min key
    Integer lastKey = treeMap.lastKey();     // Max key
    Integer floorKey = treeMap.floorKey(k);  // Largest key <= k
    Integer ceilKey = treeMap.ceilingKey(k); // Smallest key >= k

    // Lower/Higher (exclusive)
    Integer lower = treeMap.lowerKey(k);     // Largest key < k
    Integer higher = treeMap.higherKey(k);   // Smallest key > k

    // Range queries - O(k log n) where k is range size
    Map.Entry<Integer, Integer> firstEntry = treeMap.firstEntry();
    Map.Entry<Integer, Integer> lastEntry = treeMap.lastEntry();

    // Iterate in sorted order - O(n)
    for (Map.Entry<Integer, Integer> entry : treeMap.entrySet()) {
        int key = entry.getKey();
        int val = entry.getValue();
        // Process in sorted order
    }

    // SubMap views (range queries)
    SortedMap<Integer, Integer> subMap = treeMap.subMap(fromKey, toKey);
    SortedMap<Integer, Integer> headMap = treeMap.headMap(toKey);
    SortedMap<Integer, Integer> tailMap = treeMap.tailMap(fromKey);
}

# Python - LC 853 Car Fleet
def carFleet(target, position, speed):
    # Use sorted iteration (similar to TreeMap)
    cars = sorted(zip(position, speed), reverse=True)  # Sort by position descending

    stack = []
    for pos, spd in cars:
        time = (target - pos) / spd  # Time to reach target
        if not stack or time > stack[-1]:
            stack.append(time)

    return len(stack)

# Alternative using SortedDict
from sortedcontainers import SortedDict

def carFleet_v2(target, position, speed):
    car_map = SortedDict()
    for p, s in zip(position, speed):
        car_map[-p] = s  # Negative for reverse order

    fleets = 0
    prev_time = 0

    for neg_pos, spd in car_map.items():
        pos = -neg_pos
        time = (target - pos) / spd
        if time > prev_time:
            fleets += 1
            prev_time = time

    return fleets

// Java - LC 853 Car Fleet
/**
 * time = O(N log N)
 * space = O(N)
 */
public int carFleet(int target, int[] position, int[] speed) {
    // Build HashMap first
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < position.length; i++) {
        map.put(position[i], speed[i]);
    }

    // Convert to TreeMap for sorted iteration (descending order)
    TreeMap<Integer, Integer> treeMap = new TreeMap<>(Collections.reverseOrder());
    treeMap.putAll(map);

    int fleets = 0;
    double prevTime = 0;

    // Iterate from position closest to target (sorted order)
    for (Map.Entry<Integer, Integer> entry : treeMap.entrySet()) {
        int pos = entry.getKey();
        int spd = entry.getValue();
        double time = (double)(target - pos) / spd;

        // If current car takes longer, it forms a new fleet
        if (time > prevTime) {
            fleets++;
            prevTime = time;
        }
    }

    return fleets;
}

// Java - LC 729 My Calendar I
/**
 * time = O(log N) per operation
 * space = O(N)
 */
class MyCalendar {
    TreeMap<Integer, Integer> calendar;

    public MyCalendar() {
        calendar = new TreeMap<>();
    }

    public boolean book(int start, int end) {
        // Find largest start time <= current start
        Integer prev = calendar.floorKey(start);

        // Find smallest start time >= current start
        Integer next = calendar.ceilingKey(start);

        // Check no overlap with previous booking
        if (prev != null && calendar.get(prev) > start) {
            return false;
        }

        // Check no overlap with next booking
        if (next != null && next < end) {
            return false;
        }

        calendar.put(start, end);
        return true;
    }
}

# Python - LC 729 My Calendar I
from sortedcontainers import SortedDict

class MyCalendar:
    """
    time = O(log N) per operation
    space = O(N)
    """
    def __init__(self):
        self.calendar = SortedDict()

    def book(self, start: int, end: int) -> bool:
        # Find previous and next bookings
        idx = self.calendar.bisect_left(start)

        # Check previous booking
        if idx > 0:
            prev_start = self.calendar.keys()[idx - 1]
            if self.calendar[prev_start] > start:
                return False

        # Check next booking
        if idx < len(self.calendar):
            next_start = self.calendar.keys()[idx]
            if next_start < end:
                return False

        self.calendar[start] = end
        return True

# LC 205 Isomorphic Strings
def isIsomorphic(s: str, t: str) -> bool:
    s2t, t2s = {}, {}
    for a, b in zip(s, t):
        if s2t.get(a, b) != b or t2s.get(b, a) != a:
            return False
        s2t[a] = b
        t2s[b] = a
    return True

# LC 290 Word Pattern
def wordPattern(pattern: str, s: str) -> bool:
    words = s.split()
    if len(pattern) != len(words):
        return False
    p2w, w2p = {}, {}
    for p, w in zip(pattern, words):
        if p2w.get(p, w) != w or w2p.get(w, p) != p:
            return False
        p2w[p] = w
        w2p[w] = p
    return True

# LC 347 Top K Frequent Elements — O(n) bucket approach
from collections import Counter

def topKFrequent(nums: list, k: int) -> list:
    count = Counter(nums)
    # bucket[i] = list of numbers that appear exactly i times
    bucket = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        bucket[freq].append(num)

    result = []
    for freq in range(len(bucket) - 1, 0, -1):
        result.extend(bucket[freq])
        if len(result) >= k:
            return result[:k]
    return result

# LC 692 Top K Frequent Words — bucket + sort within bucket
from collections import Counter

def topKFrequent_words(words: list, k: int) -> list:
    count = Counter(words)
    bucket = [[] for _ in range(len(words) + 1)]
    for word, freq in count.items():
        bucket[freq].append(word)

    result = []
    for freq in range(len(bucket) - 1, 0, -1):
        bucket[freq].sort()          # alphabetical within same frequency
        result.extend(bucket[freq])
        if len(result) >= k:
            return result[:k]
    return result

# LC 139 Word Break — {index: bool}
def wordBreak(s: str, wordDict: list) -> bool:
    word_set = set(wordDict)
    memo = {}

    def dp(i):
        if i == len(s):
            return True
        if i in memo:
            return memo[i]
        for j in range(i + 1, len(s) + 1):
            if s[i:j] in word_set and dp(j):
                memo[i] = True
                return True
        memo[i] = False
        return False

    return dp(0)

# LC 1048 Longest String Chain — {word: longest_chain_ending_here}
def longestStrChain(words: list) -> int:
    words.sort(key=len)
    dp = {}   # word -> longest chain ending at this word
    best = 1
    for word in words:
        dp[word] = 1
        for i in range(len(word)):
            prev = word[:i] + word[i+1:]   # remove one character
            if prev in dp:
                dp[word] = max(dp[word], dp[prev] + 1)
        best = max(best, dp[word])
    return best

# LC 322 Coin Change — classic DP, memo keyed by amount
def coinChange(coins: list, amount: int) -> int:
    memo = {}
    def dp(rem):
        if rem < 0: return float('inf')
        if rem == 0: return 0
        if rem in memo: return memo[rem]
        memo[rem] = min(dp(rem - c) + 1 for c in coins)
        return memo[rem]
    res = dp(amount)
    return res if res != float('inf') else -1

# LC 496 Next Greater Element I
# map each element of nums1 to its next-greater in nums2
def nextGreaterElement(nums1: list, nums2: list) -> list:
    next_greater = {}   # val -> next greater val in nums2
    stack = []          # monotonic decreasing stack

    for num in nums2:
        # pop all elements smaller than current — current is their next greater
        while stack and stack[-1] < num:
            next_greater[stack.pop()] = num
        stack.append(num)

    return [next_greater.get(n, -1) for n in nums1]

# LC 503 Next Greater Element II (circular array)
def nextGreaterElements(nums: list) -> list:
    n = len(nums)
    result = [-1] * n
    stack = []  # stores indices

    for i in range(2 * n):   # traverse twice for circular
        while stack and nums[stack[-1]] < nums[i % n]:
            result[stack.pop()] = nums[i % n]
        if i < n:
            stack.append(i)
    return result

# LC 739 Daily Temperatures — index-based answer map
def dailyTemperatures(temps: list) -> list:
    result = [0] * len(temps)
    stack = []  # monotonic decreasing stack of indices

    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)
    return result

# LC 187 Repeated DNA Sequences — find all length-10 substrings appearing ≥ 2 times
def findRepeatedDnaSequences(s: str) -> list:
    if len(s) <= 10:
        return []
    seen, repeated = set(), set()
    for i in range(len(s) - 9):
        sub = s[i:i+10]
        if sub in seen:
            repeated.add(sub)
        seen.add(sub)
    return list(repeated)

# General Rabin-Karp rolling hash template
def rabin_karp(s: str, pattern: str) -> list:
    """Return all start indices where pattern occurs in s."""
    n, m = len(s), len(pattern)
    if m > n:
        return []

    BASE = 26
    MOD = (1 << 61) - 1   # Mersenne prime — minimises collisions

    def char_val(c):
        return ord(c) - ord('a')

    # Precompute BASE^(m-1) mod MOD
    power = pow(BASE, m - 1, MOD)

    # Hash of pattern and first window
    p_hash = 0
    w_hash = 0
    for i in range(m):
        p_hash = (p_hash * BASE + char_val(pattern[i])) % MOD
        w_hash = (w_hash * BASE + char_val(s[i])) % MOD

    result = []
    for i in range(n - m + 1):
        if w_hash == p_hash and s[i:i+m] == pattern:  # verify on hash match
            result.append(i)
        if i < n - m:
            # Roll: remove leftmost, add new rightmost
            w_hash = (w_hash - char_val(s[i]) * power) % MOD
            w_hash = (w_hash * BASE + char_val(s[i + m])) % MOD

    return result

# LC 1044 Longest Duplicate Substring — binary search + rolling hash
def longestDupSubstring(s: str) -> str:
    BASE, MOD = 31, (1 << 61) - 1

    def has_dup(length):
        if length == 0:
            return ""
        power = pow(BASE, length - 1, MOD)
        h = 0
        for c in s[:length]:
            h = (h * BASE + ord(c) - ord('a')) % MOD
        seen = {h: 0}
        for i in range(1, len(s) - length + 1):
            h = (h - (ord(s[i-1]) - ord('a')) * power) % MOD
            h = (h * BASE + ord(s[i+length-1]) - ord('a')) % MOD
            if h in seen:
                # verify (collision guard)
                start = seen[h]
                if s[start:start+length] == s[i:i+length]:
                    return s[i:i+length]
            seen[h] = i
        return ""

    lo, hi, ans = 0, len(s) - 1, ""
    while lo <= hi:
        mid = (lo + hi) // 2
        dup = has_dup(mid)
        if dup:
            ans = dup
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

If we want subarray[i,j] to sum to k:
  presum[j] - presum[i-1] = k
  → presum[i-1] = presum[j] - k

So at index j, check if (presum[j] - k) exists in map!

i=0: num=1, presum=1
  - Check: (1-2)=-1 not in map → count=0
  - Update: map={0:1, 1:1}

i=1: num=1, presum=2
  - Check: (2-2)=0 in map, count += map[0] = 1 → count=1
  - Update: map={0:1, 1:1, 2:1}

i=2: num=1, presum=3
  - Check: (3-2)=1 in map, count += map[1] = 1 → count=2
  - Update: map={0:1, 1:1, 2:1, 3:1}

Result: count=2 (subarrays [1,1] and [1,1])

public int subarraySum(int[] nums, int k) {
    // Map: {prefixSum: count} - NOT {prefixSum: index}!
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);  // Handle subarrays from index 0

    int presum = 0;
    int count = 0;

    for (int num : nums) {
        presum += num;

        // Check if (presum - k) exists: presum - x = k → x = presum - k
        if (map.containsKey(presum - k)) {
            count += map.get(presum - k);  // Add ALL occurrences
        }

        // Update map AFTER checking (critical order!)
        map.put(presum, map.getOrDefault(presum, 0) + 1);
    }

    return count;
}

In [10]: d = {'a': 1, 'b': 2}
    ...: d['a']
Out[10]: 1

In [11]: d.get('a')
Out[11]: 1

In [12]: d.get('c', 0)
Out[12]: 0

In [13]: d.get('z')

In [14]:

#-------------------------------------------------------------------------------
# setdefault : will creatte key if key NOT existed (with value as well if defined)
#-------------------------------------------------------------------------------

# syntax
d.setdefault(new_key)
d.setdefault(new_key, new_value)

# 662 Maximum Width of Binary Tree
car = {
  "brand": "Ford",
  "model": "Mustang",
  "year": 1964
}

# example 1) insert key "my_key", since my_key not existed, -> make it as new key and value as None (since not defined)
car.setdefault("my_key")
print (car)
# In [18]: car
# Out[18]: {'brand': 'Ford', 'model': 'Mustang', 'year': 1964, 'my_key': None}

# example 2) insert key "color", since my_key not existed, -> make it as new key and value as white
car.setdefault("color", "white")
print (car)
# Out[22]:
# {'brand': 'Ford',
#  'model': 'Mustang',
#  'year': 1964,
#  'my_key': None,
#  'color': 'white'}

# https://stackoverflow.com/questions/613183/how-do-i-sort-a-dictionary-by-value

x = {1: 2, 3: 4, 4: 3, 2: 1, 0: 0}
In [11]: x.items()
Out[11]: dict_items([(1, 2), (3, 4), (4, 3), (2, 1), (0, 0)])

#----------------------------------
# Sort hashMap by key/value !!!
#----------------------------------
x = {1: 2, 3: 4, 4: 3, 2: 1, 0: 0}
# note : have to use sorted(xxx, key=yyy), instead of xxx.sorted(....)
### NOTE this !!! : x.items()
sorted_x = sorted(x.items(), key=lambda kv: kv[1])
print (sorted_x)
# [(0, 0), (2, 1), (1, 2), (4, 3), (3, 4)]

x = {1: 2, 3: 4, 4: 3, 2: 1, 0: 0}
sorted_x = sorted(x.items(), key=lambda kv: kv[0])
print (sorted_x)
# [(0, 0), (1, 2), (2, 1), (3, 4), (4, 3)]

# 451  Sort Characters By Frequency
import collections
class Solution(object):
    def frequencySort(self, s):
        count = collections.Counter(s)
        count_dict = dict(count)
        """
        NOTE this !!!
            1. use sorted()
            2. count_dict.items()
        """
        count_tuple_sorted = sorted(count_dict.items(), key=lambda kv : -kv[1])
        res = ''
        for item in count_tuple_sorted:
            res += item[0] * item[1]
        return res

# dict values -> array
In [6]:
   ...: mydict = {'a':['a1','a2','a3'], 'b':['b1','b2','b3']}
   ...:
   ...: res = [mydict[x] for x in mydict]
   ...:
   ...: print (res)
[['a1', 'a2', 'a3'], ['b1', 'b2', 'b3']]

# LC 049 Group Anagrams
# V0
# IDEA : HASH TABLE
class Solution:
    def groupAnagrams(self, strs):
        res = {}
        for item in strs:
            k = ''.join(sorted(item))  # sort the string 
            if k not in res:  #  check if exists in res 
                res[k] = []
            res[k].append(item)  # if same, put all the same string into dict k 
        return [res[x] for x in res]  # output the result 

s = 'ababcbacadefegdehijhklij'
{k:v for k,v in enumerate(s)}

# LC 763
# V0
# IDEA : GREEDY
class Solution(object):
    def partitionLabels(self, s):
        d = {val:idx for idx, val in enumerate(list(s))}
        #print (d)
        res = []
        tmp = set()
        for idx, val in enumerate(s):
            #print ("idx = " + str(idx) + " tmp = " + str(tmp) + "idx == d[val] = " + str(idx == d[val]))
            """
            ### have to fit 2 CONDITIONS so we can split the string
            # -> 1) the element has "last time exist index" with current index
            # -> 2) ALL of the elements in cache with "last time exist index" should <= current index
            """
            if idx == d[val] and all(idx >= d[t] for t in tmp):
                res.append(idx+1)
            else:
                tmp.add(val)
        _res = [res[0]] + [ res[i] - res[i-1] for i in range(1, len(res)) ]
        return _res

# V0'
# IDEA : GREEDY
class Solution(object):
    def partitionLabels(self, S):
        # note : this trick for get max index for each element in S
        lindex = { c: i for i, c in enumerate(S) }
        j = anchor = 0
        ans = []
        for i, c in enumerate(S):
            ### NOTE : trick here
            #          -> via below line of code, we can get the max idx of current substring which "has element only exist in itself"
            #          -> e.g. the index we need to do partition 
            j = max(j, lindex[c])
            print ("i = " + str(i) + "," + " c = " + str(c) + "," +   " j = " + str(j) + "," +  " ans = " + str(ans))
            if i == j:
                ans.append(j - anchor + 1)
                anchor = j + 1
        return ans

# LC 1010 Pairs of Songs With Total Durations Divisible by 60
d = {}
res = 0
DURATION = some_duration
for num in nums:
    tmp = num % DURATION # let's say sum is multiply by 60
    ### NOTICE THIS :  (60 - tmp) % 60
    if (DURATION - tmp) % DURATION in d:
        res += d[(DURATION - tmp) % DURATION]
    if tmp not in d:
        d[tmp] = 1
    else:
        d[tmp] += 1

# (algorithm book (labu) p.350)
my_array = [1,2,3,4,5]
my_array_pre = [0] * (len(my_array)+1)
cur = 0
for i in range(len(my_array)):
    cur += my_array[i]
    my_array_pre[i+1] += cur

# In [17]: print ("my_array = " + str(my_array))
#     ...: print ("my_array_pre = " + str(my_array_pre))
# my_array = [1, 2, 3, 4, 5]
# my_array_pre = [0, 1, 3, 6, 10, 15]

#-----------------------------------------------
# Get sub array sum !!!!!!!
#    -> nums[i..j] sum = preSum[j+1] - preSum[i]
#-----------------------------------------------

# example 1 : sum of [1,2]
my_array_pre[1+1] - my_array_pre[0]  # 1's index is 0, and 2's index is 1. (my_array = [1, 2, 3, 4, 5])

# example 2 : sum of [2,3,4]
my_array_pre[3+1] - my_array_pre[1] # 2's index is 1, and 4's index is 3. (my_array = [1, 2, 3, 4, 5])

# LC 003
# 2 pointers + dict
# ....
l = 0
d = {}
res = 0
for r in range(len(s)):
    if s[r] in d:
        l = max(l, d[s[r]]+1)
    d[s[r]] = r
    res = max(res, r-l+1)
# ...

Transform the binary array:
- Treat 0 as -1
- Treat 1 as +1

Why? Equal 0s and 1s → sum of transformed array = 0

Map<Integer, Integer> map = new HashMap<>();
// {count: first_index_where_count_occurred}

map.put(0, -1); // Initialize for subarrays starting at index 0

count: running sum (cumulative)
  - +1 for each 1
  - -1 for each 0

If count(i) == count(j) where i < j:
  → Elements between i and j sum to 0
  → Subarray [i+1, j] is balanced (equal 0s and 1s)
  → Length = j - i

To maximize length, we want the earliest index with this count.
If count appears at indices [3, 7, 10]:
  - Store index 3
  - When we see count again at index 10, length = 10 - 3 = 7 (maximum)

If from index 0 to i, count = 0:
  → Entire subarray [0, i] is balanced
  → Length = i - (-1) = i + 1 ✓

Without this initialization, we'd miss subarrays starting at index 0.

Let count(i) = cumulative sum at index i

If count(i) == count(j) where i < j:
  count(j) - count(i) = 0

This means:
  sum of elements from index (i+1) to j = 0

In transformed array (0→-1, 1→+1):
  sum = 0 means equal number of -1s and +1s
  → equal number of 0s and 1s in original array

// Java Template
public int findMaxLength(int[] nums) {
    // Map: {count: first_index_where_count_occurred}
    Map<Integer, Integer> map = new HashMap<>();

    // Initialize: handle subarrays starting at index 0
    map.put(0, -1);

    int maxLen = 0;
    int count = 0;

    for (int i = 0; i < nums.length; i++) {
        // Transform: 0 → -1, 1 → +1
        count += (nums[i] == 1) ? 1 : -1;

        // If count seen before: calculate subarray length
        if (map.containsKey(count)) {
            maxLen = Math.max(maxLen, i - map.get(count));
        } else {
            // Store FIRST occurrence only (for max length)
            map.put(count, i);
        }
    }

    return maxLen;
}

# Python Template
def findMaxLength(nums):
    # Map: {count: first_index_where_count_occurred}
    d = {0: -1}  # Initialize for subarrays starting at index 0

    max_len = 0
    count = 0

    for i, num in enumerate(nums):
        # Transform: 0 → -1, 1 → +1
        count += 1 if num == 1 else -1

        # If count seen before: calculate subarray length
        if count in d:
            max_len = max(max_len, i - d[count])
        else:
            # Store FIRST occurrence only (for max length)
            d[count] = i

    return max_len

# 525 Contiguous Array

# V0
# IDEA : HashMap
#     -> SET UP A DICT,
#     -> FIND MAX SUB ARRAY LENGH WHEN COUNT(0) == COUNT(1)
#     -> (WHEN cur in _dict, THERE IS THE COUNT(0) == COUNT(1) CASE)
# explaination : https://leetcode.com/problems/contiguous-array/discuss/99655/python-on-solution-with-visual-explanation
class Solution(object):
    def findMaxLength(self, nums):
        # edge case
        if len(nums) <= 1:
            return 0
        # note this edge case
        if len(nums) == 2:
            if nums.count(0) == nums.count(1):
                return 2
            else:
                return 0

        # NOTE !!! : init hash map like below (idx=0, no solution, for [0,1,1] case)
        d = {0:-1} # {tmp_sum : index}
        tmp = 0
        res = 0
        for k, v in enumerate(nums):
            if v == 1:
                tmp += 1
            else:
                tmp -= 1
            """
            Case 1 : if tmp sum in dict
            # NOTE THIS : if tmp in d, return the max of (res,cur-index - index) from d with same cur-value
            """
            if tmp in d:
                res = max(res, k - d[tmp])
            """
            Case 2 : if tmp sum NOT in dict
            # NOTE THIS : if tmp not in d, then use its cur value as key, index as value
            """
            else:
                d[tmp] = k ### NOTE : we just need to add index to dict at once, since what we need is MAX len of continous subarray with condition, so we only add 1st index to dist will make this work (max len subarray)
        return res

# V0'
# https://github.com/yennanliu/CS_basics/blob/master/leetcode_python/Tree/contiguous-array.py
# explanation : https://leetcode.com/problems/contiguous-array/discuss/99655/python-on-solution-with-visual-explanation
# HASH MAP FIND EQUAL 0, 1
class Solution(object):
    def findMaxLength(self, nums):
        r = 0
        cur = 0
        ### NOTE : WE HAVE TO INIT DICT LIKE BELOW
        # https://blog.csdn.net/fuxuemingzhu/article/details/82667054
        _dict = {0:-1}
        for k, v in enumerate(nums):
            if v == 1:
                cur += 1
            else:
                cur -= 1
            if cur in _dict:
                r = max(r, k - _dict[cur])
            else:
                _dict[cur] = k
        return r

If prefix[i] % k == prefix[j] % k  (where j < i)

Then:
  (prefix[i] - prefix[j]) % k == 0

Which means:
  prefix[i] - prefix[j] = sum of nums[j+1 .. i]

Therefore:
  The subarray [j+1, i] has a sum divisible by k

Map<Integer, Integer> map = new HashMap<>();
// {remainder: count}  ← Store COUNT, not index (similar to LC 560)

map.put(0, 1); // Initialize for subarrays starting from beginning

This is a "count ALL subarrays" problem (like LC 560).

If remainder 3 appears at indices [2, 5, 8]:
  - When we reach index 5: add 1 (subarray from index 2 to 5)
  - When we reach index 8: add 2 (subarrays from 2→8 and 5→8)

Total: 3 valid subarrays

int remainder = prefixSum % k;

// MUST adjust negative remainders to positive
if (remainder < 0) {
    remainder += k;
}

// Or use this one-liner:
remainder = ((prefixSum % k) + k) % k;

If prefixSum % k == 0 at some index i:
  → The entire subarray [0, i] is divisible by k
  → We need to count this case

Without initialization, we'd miss these subarrays.

// Java Template
public int subarraysDivByK(int[] nums, int k) {
    // Map: {remainder: count}
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1); // Handle subarrays from beginning

    int count = 0;
    int prefixSum = 0;

    for (int num : nums) {
        prefixSum += num;

        // Calculate remainder (handle negatives!)
        int remainder = prefixSum % k;
        if (remainder < 0) {
            remainder += k;
        }
        // Or: int remainder = ((prefixSum % k) + k) % k;

        // Add count of all previous same remainders
        count += map.getOrDefault(remainder, 0);

        // Update remainder count
        map.put(remainder, map.getOrDefault(remainder, 0) + 1);
    }

    return count;
}

# Python Template
def subarraysDivByK(nums, k):
    # Map: {remainder: count}
    remainder_count = {0: 1}

    count = 0
    prefix_sum = 0

    for num in nums:
        prefix_sum += num

        # Calculate remainder (Python % handles negatives correctly)
        remainder = prefix_sum % k

        # Add count of all previous same remainders
        count += remainder_count.get(remainder, 0)

        # Update remainder count
        remainder_count[remainder] = remainder_count.get(remainder, 0) + 1

    return count

public int subarraysDivByK(int[] nums, int k) {
    int[] remainderCount = new int[k];
    remainderCount[0] = 1;

    int count = 0;
    int prefixSum = 0;

    for (int num : nums) {
        prefixSum += num;
        int remainder = ((prefixSum % k) + k) % k;

        count += remainderCount[remainder];
        remainderCount[remainder]++;
    }

    return count;
}

prefixSum = -1: remainder = -1 (wrong!)
prefixSum = -3: remainder = -3 (wrong!)
prefixSum = -6: remainder = -1 (wrong!)

prefixSum = -1: remainder = 4 (correct: -1 ≡ 4 mod 5)
prefixSum = -3: remainder = 2 (correct: -3 ≡ 2 mod 5)
prefixSum = -6: remainder = 4 (correct: -6 ≡ 4 mod 5)

map: {oddCount: frequency}
     → "How many times has this odd-count appeared so far?"

At index i with current oddCount:
  → Find how many previous positions had exactly (oddCount - k) odds
  → Those form subarrays with exactly k odds ending at i

If oddCount == k at index i:
  → Entire subarray [0, i] has exactly k odds
  → oddCount - k = 0, must have {0: 1} pre-initialized

// Java - LC 1248
public int numberOfSubarrays(int[] nums, int k) {
    // map: {oddCount: frequency}
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);  // base case: 0 odds seen 1 time

    int res = 0, oddCount = 0;

    for (int num : nums) {
        if (num % 2 == 1) oddCount++;  // treat odd as +1

        // How many previous positions had (oddCount - k) odds?
        res += map.getOrDefault(oddCount - k, 0);

        // Update count AFTER checking (critical order!)
        map.put(oddCount, map.getOrDefault(oddCount, 0) + 1);
    }

    return res;
}

// Exactly k = atMost(k) - atMost(k-1)
public int numberOfSubarrays(int[] nums, int k) {
    return atMost(nums, k) - atMost(nums, k - 1);
}

private int atMost(int[] nums, int k) {
    int l = 0, res = 0, oddCount = 0;
    for (int r = 0; r < nums.length; r++) {
        if (nums[r] % 2 == 1) oddCount++;
        while (oddCount > k) {
            if (nums[l] % 2 == 1) oddCount--;
            l++;
        }
        res += (r - l + 1);
    }
    return res;
}

# 523 Continuous Subarray Sum
# V0
# IDEA : HASH TABLE
# -> if sum(nums[i:j]) % k == 0 for some i < j, 
#   ->  then sum(nums[:j]) % k == sum(nums[:i]) % k  !!!!
#   -> So we just need to use a dict to keep track of sum(nums[:i]) % k 
#   -> and the corresponding index i. Once some later sum(nums[:i']) % k == sum(nums[:i]) % k and i' - i > 1, so we return True.
class Solution(object):
    def checkSubarraySum(self, nums, k):
        """
        # _dict = {0:-1} : for edge case (need to find a continuous subarray of size AT LEAST two )
        # https://leetcode.com/problems/continuous-subarray-sum/discuss/236976/Python-solution
        # 0: -1 is for edge case that current sum mod k == 0
        # demo :
                In [93]: nums = [0]
                    ...: k = 1
                    ...:
                    ...:
                    ...: s = Solution()
                    ...: r = s.checkSubarraySum(nums, k)
                    ...: print (r)
                0
                i - _dict[tmp] = 1
                False
        """
        ### NOTE : we need to init _dict as {0:-1}
        _dict = {0:-1}
        tmp = 0
        for i in range(len(nums)):
            tmp += nums[i]
            if k != 0:
                ### NOTE : we get remainder of tmp by k
                tmp = tmp % k
            # if tmp in _dict, means there is the other sub part make sub array sum % k == 0
            if tmp in _dict:
                ### only if continuous sub array with length >= 2
                if i - _dict[tmp] > 1:
                    return True
            else:
                _dict[tmp] = i
        return False

# 049 Group Anagrams
# V0
# IDEA : HASH TABLE
class Solution:
    def groupAnagrams(self, strs):
        res = {}
        for item in strs:
            k = ''.join(sorted(item))  # sort the string 
            if k not in res:  #  check if exists in res 
                res[k] = []
            res[k].append(item)  # if same, put all the same string into dict k 
        return [res[x] for x in res]  # output the result 

# LC 003
# V0'
# IDEA : TWO POINTER + SLIDING WINDOW + DICT (NOTE this method !!!!)
#       -> use a hash table (d) record visited "element" (e.g. : a,b,c,...)
#          (but NOT sub-string)
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        d = {}
        # left pointer
        l = 0
        res = 0
        """
        NOTE !!!

        we move right pointer first, then left pointer
        """
        # NOTE !!! right pointer
        for r in range(len(s)):
            """
            ### NOTE : deal with "s[r] in d" case ONLY !!! 
            ### NOTE : if already visited, means "repeating"
            #      -> then we need to update left pointer (l)
            """
            if s[r] in d:
                """
                NOTE !!! this
                -> via max(l, d[s[r]] + 1) trick,
                   we can get the "latest" idx of duplicated s[r], and start from that one
                """
                l = max(l, d[s[r]] + 1)
            # if not visited yet, record the alphabet
            # and re-calculate the max length
            d[s[r]] = r
            res = max(res, r -l + 1)
        return res

# LC 204 Count Primes
# V0
# IDEA : dict
# https://leetcode.com/problems/count-primes/discuss/1343795/python%3A-sieve-of-eretosthenes
# prime(x) : check if x is a prime
# prime(0) = 0
# prime(1) = 0
# prime(2) = 0
# prime(3) = 1
# prime(4) = 2
# prime(5) = 3
# python 3
class Solution:
    def countPrimes(self, n):
        # using sieve of eretosthenes algorithm
        if n < 2: return 0
        nonprimes = set()
        for i in range(2, round(n**(1/2))+1):
            if i not in nonprimes:
                for j in range(i*i, n, i):
                    nonprimes.add(j)
        return n - len(nonprimes) - 2  # remove prime(1), prime(2)

# python
# LC 036 Valid Sudoku
# V0
class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        n = len(board)
        return self.isValidRow(board) and self.isValidCol(board) and self.isValidNineCell(board)
        
    def isValidRow(self, board):
        n = len(board)
        for r in range(n):
            row = [x for x in board[r] if x != '.']
            if len(set(row)) != len(row): # if not repetition 
                return False
        return True

    def isValidCol(self, board):
        n = len(board)
        for c in range(n):
            col = [board[r][c] for r in range(n) if board[r][c] != '.']
            if len(set(col)) != len(col): # if not repetition 
                return False
        return True

    def isValidNineCell(self, board):
        n = len(board)
        for r in range(0, n, 3):
            for c in range(0, n, 3):
                cell = []
                for i in range(3):
                    for j in range(3):
                        num = board[r + i][c + j]
                        if num != '.':
                            cell.append(num)
                if len(set(cell)) != len(cell): # if not repetition 
                    return False
        return True

// java
// LC 036 Valid Sudoku
// backtrack
// (algorithm book (labu) p.311)
boolean backtrack(char[][] board, int i, int j){

    int m = 9, n = 9;
    
    if (j == n){
        // if visit last col, start from next row
        return backtrack(board, i + 1, 0);
    }

    if (i == m){
        // found one solution, trigger base case
        return true;
    }

    if (board[i][j] != '.'){
        // if there id default number, then no need to looping
        return backtrack(board, i, j + 1);
    }

    for (char ch = '1'; ch <= '9'; ch++){
        // if there is no valid number, negelect it
        if (!isValid(board, i, j, ch)){
            continue;
        }

        board[i][j] = ch;

        // if found one solution, return it and terminate the program
        if (backtrack(board, i, j+1)){
            return true;
        }

        board[i][j] = '.';
    }

    // if looping 1 ~ 9, still can't find a solution
    // -> change a number to loop
    return false;
}

bollean isValid(char[][] board, int r, int c, char n){
    for (int i = 0; i < 9; i++){
        // check if row has duplicate
        if (board[r][i] == n) return false;
        // check if col has duplicate
        if (board[i][c] == n) return false;
        // check if "3 x 3 matrix" has duplicate
        if (board[ (r/3) * 3 + i / 3 ][ (c/3) * 3 + i % 3] == n) return false;
    }
    return true;
}  

# LC 1010. Pairs of Songs With Total Durations Divisible by 60
# V0
# IDEA : dict
# IDEA : NOTE : we only count "NUMBER OF PAIRS", instead get all pairs indexes
class Solution(object):
    def numPairsDivisibleBy60(self, time):
        rem = {}
        pairs = 0
        for t in time:
            #print ("rem = " + str(rem))
            t %= 60
            if (60 - t) % 60 in rem:
                """
                NOTE : this trick
                -> we append "all 60 duration combinations count" via the existing times of element "(60 - t) % 60" 
                """
                pairs += rem[(60 - t) % 60]
            if t not in rem:
                rem[t] = 1
            else:
                ### NOTE : here : we plus 1 when an element already exist
                rem[t] += 1
        return pairs

# LC 560 : Subarray Sum Equals K

# V0
# IDEA : HASH TABLE + sub array sum
# IDEA : https://blog.csdn.net/fuxuemingzhu/article/details/82767119
class Solution(object):
    def subarraySum(self, nums, k):
        n = len(nums)
        d = collections.defaultdict(int)
        d[0] = 1
        sum = 0
        res = 0
        for i in range(n):
            sum += nums[i]
            # if sum - k in d
            #  -> if sum - (every _ in d) == k
            if sum - k in d:
                res += d[sum - k]
            d[sum] += 1
        return res

# V0'
# IDEA : HASH TABLE + sub array sum
class Solution:
    def subarraySum(self, nums, k):
        # write your code here
        for i in range(1, len(nums)):
            nums[i] += nums[i - 1]
        print ("nums = " + str(nums))
        d = {0:1}
        ans = 0
        for i in range(len(nums)):
            # check sub array equals k
            if(d.get(nums[i] - k) != None):
                ans += d[nums[i] - k]
            # update dict
            if nums[i] not in d:
                d[nums[i]] = 1
            else:
                d[nums[i]] += 1
        return ans

// LC 560 : Subarray Sum Equals K
// java
// (algorithm book (labu) p.350)
// V1 : brute force + cum sum
int subarraySum(int[] nums, int k){
    int n = nums.length;
    // init pre sum
    int[] sum = new int[n+1];
    sum[0] = 0;
    for (int i = 0; i < n; i++){
        sum[i+1] = sum[i] + nums[i];
    }

    int ans = 0;
    // loop over all sub array
    for (int i=1; i <= n; i++){
        for (int j=0; j < i; j++){
            // sum of nums[j...i-1]
            if (sum[i] - sum[j] == k){
                ans += 1;
            }
        }
    }
    return ans;
}

// (algorithm book (labu) p.350)
// V2 : hash map + cum sum
int subarraySum(int[] nums, int k){
    int n = nums.length;
    // map :  key : prefix, value : prefix exists count
    // init hash map
    HashMap<Integer, Integer> preSum = new HashMap<Integer, Integer>();

    // base case
    preSum.put(0,1);

    int ans = 0;
    int sum0_i = 0;

    for (int i = 0; i < n; i++){
        sum0_i += nums[i];
        // for presum : nums[0..j]
        int sum0_j = sum0_i - k;
        // if there is already presum, update the ans directly
        if (preSum.containsKey(sum0_j)){
            ans += preSum.get(sum0_j);
        }
        // add prefix and nums[0..i] and record exists count
        preSum.put(sum0_i, preSum.getOrDefault(sum0_i,0) + 1);
    }
    return ans;
}

# LC 532 K-diff Pairs in an Array
# V0
# IDEA : HASH TABLE
import collections
class Solution(object):
    def findPairs(self, nums, k):
        answer = 0
        cnt = collections.Counter(nums)
        # NOTE THIS : !!! we use set(nums) for reduced time complexity, and deal with k == 0 case separately
        for num in set(nums):
            """
            # [b - a] = k
            #  -> b - a = +k or -k
            #  -> b = k + a or b = -k + a
            #  -> however, 0 <= k <= 10^7, so ONLY b = k + a is possible

            2 cases
                -> case 1) k > 0 and num + k in cnt
                -> case 2) k == 0 and cnt[num] > 1
            """
            # case 1) k > 0 and num + k in cnt
            if k > 0 and num + k in cnt: # | a - b | = k -> a - b = +k or -k, but here don't have to deal with "a - b = -k" case, since this sutuation will be covered when go through whole nums  
                answer += 1
            # case 2) k == 0 and cnt[num] > 1
            if k == 0 and cnt[num] > 1:  # for cases k = 0 ->  pair like (1,1) will work. (i.e. 1 + (-1))
                answer += 1
        return answer

# V0'
# IDEA : SORT + BRUTE FORCE + BREAK
class Solution(object):
    def findPairs(self, nums, k):
        # edge case
        if not nums and k:
            return 0
        nums.sort()
        res = 0
        tmp = []
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if abs(nums[j] - nums[i]) == k:
                    cur = [nums[i], nums[j]]
                    cur.sort()
                    if cur not in tmp:
                        res += 1
                        tmp.append(cur)
                elif abs(nums[j] - nums[i]) > k:
                    break
        return res

# LC 734. Sentence Similarity
# V0'
# https://zxi.mytechroad.com/blog/hashtable/leetcode-734-sentence-similarity/
import collections
class Solution(object):
    def areSentencesSimilar(self, words1, words2, pairs):
        if len(words1) != len(words2): return False
        similars = collections.defaultdict(set)
        for w1, w2 in pairs:
            similars[w1].add(w2)
            similars[w2].add(w1)
        for w1, w2 in zip(words1, words2):
            if w1 != w2 and w2 not in similars[w1]:
                return False
        return True

# V0
# IDEA : array op
#   -> Apart from edge cases
#   -> there are cases we need to consider
#     -> 1) if sentence1[i] == sentence2[i]
#     -> 2) if sentence1[i] != sentence2[i] and
#           -> [sentence1[i], sentence2[i]] in similarPairs
#           -> [sentence2[i], sentence1[i]] in similarPairs
class Solution(object):
    def areSentencesSimilar(self, sentence1, sentence2, similarPairs):
        # edge case
        if sentence1 == sentence2:
            return True
        if len(sentence1) != len(sentence2):
            return False
        for i in range(len(sentence1)):
            tmp = [sentence1[i], sentence2[i]]
            """
            NOTE : below condition
                1) sentence1[i] != sentence2[i]
                  AND
                2) (tmp not in similarPairs and tmp[::-1] not in similarPairs)

                -> return false
            """
            if sentence1[i] != sentence2[i] and (tmp not in similarPairs and tmp[::-1] not in similarPairs):
                return False
        return True

# LC 146 LRU Cache
# note : there is also array/queue approach
# V1
# IDEA : Ordered dictionary
# https://leetcode.com/problems/lru-cache/solution/
# IDEA : 
#       -> There is a structure called ordered dictionary, it combines behind both hashmap and linked list. 
#       -> In Python this structure is called OrderedDict 
#       -> and in Java LinkedHashMap.
from collections import OrderedDict
class LRUCache(OrderedDict):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self:
            return - 1
        
        self.move_to_end(key)
        return self[key]

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last = False)

# LC 438. Find All Anagrams in a String
# V0
# IDEA : SLIDING WINDOW + collections.Counter()
class Solution(object):
    def findAnagrams(self, s, p):
        ls, lp = len(s), len(p)
        cp = collections.Counter(p)
        cs = collections.Counter()
        ans = []
        for i in range(ls):
            cs[s[i]] += 1
            if i >= lp:
                cs[s[i - lp]] -= 1
                ### BE AWARE OF IT
                if cs[s[i - lp]] == 0:
                    del cs[s[i - lp]]
            if cs == cp:
                ans.append(i - lp + 1)
        return ans

# LC 554. Brick Wall
# V0
# IDEA : HASH TABLE + COUNTER UPDATE (looping every element in the list and cumsum and 
import collections
class Solution(object):
    def leastBricks(self, wall):
        _counter = collections.Counter()
        count = 0
        # go through every sub-wall in wall
        for w in wall:
            cum_sum = 0
            # go through every element in sub-wall
            for i in range(len(w) - 1):
                cum_sum += w[i]
                ### NOTE we can update collections.Counter() via below
                _counter.update([cum_sum])
                count = max(count, _counter[cum_sum])
        return len(wall) - count

// LC 325 — prefix sum + hashmap, store FIRST occurrence (max length variant)
// Key: prefixSum[j] - prefixSum[i] = k  →  check if (curSum - k) exists in map
public int maxSubArrayLen(int[] nums, int k) {
    Map<Integer, Integer> preSumMap = new HashMap<>();
    preSumMap.put(0, -1); // handle subarrays starting at index 0

    int curSum = 0, maxSize = 0;
    for (int i = 0; i < nums.length; i++) {
        curSum += nums[i];
        if (preSumMap.containsKey(curSum - k)) {
            maxSize = Math.max(maxSize, i - preSumMap.get(curSum - k));
        }
        preSumMap.putIfAbsent(curSum, i); // store FIRST occurrence only
    }
    return maxSize;
}

// java
// LC 1257

// V0-1
// IDEA: HASHMAP (fixed by gpt)
// TODO: validate
public String findSmallestRegion_0_1(List<List<String>> regions, String region1, String region2) {

    // Map each region to its parent
    /**
     *  NOTE !!!
     *
     *   map : {child : parent}
     *
     *   -> so the key is child, and the value is its parent
     *
     */
    Map<String, String> parentMap = new HashMap<>();

    for (List<String> regionList : regions) {
        String parent = regionList.get(0);
        for (int i = 1; i < regionList.size(); i++) {
            parentMap.put(regionList.get(i), parent);
        }
    }

    // Track ancestors of region1
    /**  NOTE !!!
     *
     *  we use `set` to track `parents` (ancestors)
     *  if exists, add it to set,
     *  and set `current region` as its `parent`
     *
     */
    Set<String> ancestors = new HashSet<>();
    while (region1 != null) {
        ancestors.add(region1);
        region1 = parentMap.get(region1);
    }

    // Traverse region2’s ancestors until we find one in region1’s ancestor set
    while (!ancestors.contains(region2)) {
        region2 = parentMap.get(region2);
    }

    return region2;
}

Step 1: Build productCount map
  for i in [0, n):
    for j in (i, n):
      productCount[nums[i]*nums[j]]++

Step 2: For each count n >= 2:
  ans += C(n, 2) * 8
       = n*(n-1)/2 * 8
       = 4 * n * (n-1)

// LC 1726 - Tuple with Same Product
// Time: O(N^2)  Space: O(N^2)
public int tupleSameProduct(int[] nums) {
    Map<Integer, Integer> productCount = new HashMap<>();

    // Step 1: count frequency of each pair product
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            int product = nums[i] * nums[j];
            productCount.put(product, productCount.getOrDefault(product, 0) + 1);
        }
    }

    // Step 2: for each product with n pairs, C(n,2) * 8 tuples
    int ans = 0;
    for (int count : productCount.values()) {
        if (count >= 2) {
            ans += count * (count - 1) / 2 * 8;
            // equivalent: ans += 4 * count * (count - 1);
        }
    }
    return ans;
}

C(n,2) * 8
= n*(n-1)/2 * 8
= 4 * n * (n-1)

pos = {value: current_index}   # O(1) lookup of "where is value v right now?"

For each index i (left → right):
  correct_val = sorted_arr[i]            # what SHOULD be at index i
  if arr[i] != correct_val:
     swap_idx = pos[correct_val]         # where correct_val currently is
     # 1) UPDATE the map BEFORE swapping (critical!)
     pos[arr[i]]      = swap_idx         # the value we move away keeps its new home
     pos[correct_val] = i                # correct_val is now at i
     # 2) swap in the array
     arr[i], arr[swap_idx] = arr[swap_idx], arr[i]
     swaps += 1

# python - LC 2471
from collections import deque

class Solution(object):
    def minimumOperations(self, root):
        # time  = O(N log M)  (M = widest level; sorting dominates per level)
        # space = O(M)
        q = deque([root])
        ops = 0

        while q:
            size = len(q)
            level = []
            for _ in range(size):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)

            ops += self.min_swaps(level)   # add this level's cost

        return ops

    def min_swaps(self, arr):
        # min swaps to sort `arr` via {value: index} hashmap
        n = len(arr)
        sorted_arr = sorted(arr)
        pos = {v: i for i, v in enumerate(arr)}   # {value: current index}
        swaps = 0

        for i in range(n):
            correct_val = sorted_arr[i]
            if arr[i] != correct_val:
                swap_idx = pos[correct_val]

                # update map BEFORE swapping (so we don't lose arr[i]'s key)
                pos[arr[i]] = swap_idx
                pos[correct_val] = i

                # swap
                arr[i], arr[swap_idx] = arr[swap_idx], arr[i]
                swaps += 1

        return swaps

// java - LC 2471
/**
 * time  = O(N log M)   // M = widest level; sorting dominates
 * space = O(M)
 */
public int minimumOperations(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    int ops = 0;

    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            level.add(node.val);
            if (node.left != null)  q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        ops += minSwaps(level);
    }
    return ops;
}

// min swaps to sort via {value: index} map
private int minSwaps(List<Integer> arr) {
    int n = arr.size();
    Integer[] sorted = arr.toArray(new Integer[0]);
    Arrays.sort(sorted);

    Map<Integer, Integer> pos = new HashMap<>();   // {value: current index}
    for (int i = 0; i < n; i++) pos.put(arr.get(i), i);

    int swaps = 0;
    for (int i = 0; i < n; i++) {
        int correctVal = sorted[i];
        if (!arr.get(i).equals(correctVal)) {
            int swapIdx = pos.get(correctVal);

            // update map BEFORE swapping
            pos.put(arr.get(i), swapIdx);
            pos.put(correctVal, i);

            // swap
            int tmp = arr.get(i);
            arr.set(i, arr.get(swapIdx));
            arr.set(swapIdx, tmp);
            swaps++;
        }
    }
    return swaps;
}

sorted = [1, 2, 3]
pos    = {3:0, 1:1, 2:2}

i=0: correct=1, arr[0]=3 (mismatch)
     swap_idx = pos[1] = 1
     update map: pos[3]=1, pos[1]=0  → pos = {3:1, 1:0, 2:2}
     swap arr[0],arr[1] → arr = [1, 3, 2]   swaps=1

i=1: correct=2, arr[1]=3 (mismatch)
     swap_idx = pos[2] = 2
     update map: pos[3]=2, pos[2]=1  → pos = {3:2, 1:0, 2:1}
     swap arr[1],arr[2] → arr = [1, 2, 3]   swaps=2

i=2: correct=3, arr[2]=3 (match) → skip

Result: 2 swaps

START: Analyzing Hash Map Problem
                   |
                   v
           Are you counting elements/frequency?
                   |
                YES|    NO
                   |     |
                   v     v
         [CATEGORY 1:     Looking for pairs/complements?
          COUNTING]            |
                            YES|    NO
                               |     |
                               v     v
                     [CATEGORY 2:    Need to find subarray properties?
                      TWO SUM]            |
                                       YES|    NO
                                          |     |
                                          v     v
                                 [CATEGORY 3:    Using sliding window technique?
                                  PREFIX SUM]          |
                                                    YES|    NO
                                                       |     |
                                                       v     v
                                             [CATEGORY 4:    Designing a data structure?
                                              SLIDING]            |
                                                               YES|    NO
                                                                  |     |
                                                                  v     v
                                                        [CATEGORY 5:    Working with graphs/trees?
                                                         DESIGN]              |
                                                                           YES|    NO
                                                                              |     |
                                                                              v     v
                                                                    [CATEGORY 6:   [OTHER PATTERNS]
                                                                     GRAPH]

# 1. Use defaultdict for cleaner counting code
from collections import defaultdict
count = defaultdict(int)  # No need for get(key, 0)

# 2. Use Counter for frequency problems
from collections import Counter
freq = Counter(arr)  # Automatically counts frequencies

# 3. Handle edge cases with dict.get()
value = my_dict.get(key, default_value)

# 4. Clean up zero counts to save space
if count[key] == 0:
    del count[key]

# 5. Use enumerate when you need both index and value
for i, val in enumerate(arr):
    # Use both i and val

// 1. Use getOrDefault to avoid null checks
map.put(key, map.getOrDefault(key, 0) + 1);

// 2. Use containsKey for existence checks
if (map.containsKey(key)) { /* ... */ }

// 3. Initialize with appropriate capacity
Map<String, Integer> map = new HashMap<>(expectedSize);

// 4. Use putIfAbsent for first occurrence
map.putIfAbsent(key, index);  // Only puts if key doesn't exist

# Track multiple relationships simultaneously
def complex_problem(arr):
    index_map = {}      # value -> index
    freq_map = {}       # value -> frequency
    reverse_map = {}    # index -> value
    
    for i, val in enumerate(arr):
        index_map[val] = i
        freq_map[val] = freq_map.get(val, 0) + 1
        reverse_map[i] = val

# Hash Map + Priority Queue (Heap)
import heapq
from collections import defaultdict

def top_k_frequent(nums, k):
    count = defaultdict(int)
    for num in nums:
        count[num] += 1
    
    # Use heap with frequency
    heap = []
    for num, freq in count.items():
        heapq.heappush(heap, (-freq, num))  # Max heap using negative values
    
    result = []
    for _ in range(k):
        result.append(heapq.heappop(heap)[1])
    return result

# For substring pattern matching
def rolling_hash_example(s, pattern):
    base, mod = 256, 10**9 + 7
    pattern_hash = sum(ord(c) * pow(base, i, mod) for i, c in enumerate(pattern)) % mod
    
    # Slide window and update hash incrementally
    # ... implementation details

n=10, blacklist=[2,3,5,8]   →   bound = 10 - 4 = 6

RANDOM RANGE  [0, bound)
|----|----|----|----|----|----|
  0    1    2    3    4    5
             X    X         X
             ↑bad inside range — must remap

TAIL RANGE  [bound, n)
|----|----|----|----|
  6    7    8    9
             X            ← also blacklisted, skip it

Remapping (last starts at 9, walks left skipping blacklisted):
  b=2  →  last=9 (valid)  → map 2→9,  last=8
  b=3  →  last=8 (blacklisted, skip) → last=7 (valid) → map 3→7, last=6
  b=5  →  last=6 (valid)  → map 5→6,  last=5

Final mapping: { 2→9, 3→7, 5→6 }

pick() result for each index in [0,5]:
  0 → 0   (not mapped, return directly)
  1 → 1
  2 → 9   (remapped)
  3 → 7   (remapped)
  4 → 4
  5 → 6   (remapped)

Valid numbers returned: {0,1,4,6,7,9} ✓ uniformly distributed

// LC 710 - Random Pick with Blacklist
class Solution {
    private Map<Integer, Integer> mapping = new HashMap<>();
    private Random random = new Random();
    private int bound;

    public Solution(int n, int[] blacklist) {
        bound = n - blacklist.length;

        Set<Integer> blackSet = new HashSet<>();
        for (int b : blacklist) blackSet.add(b);

        int last = n - 1;
        for (int b : blacklist) {
            if (b < bound) {
                // Skip tail values that are also blacklisted
                while (blackSet.contains(last)) last--;
                mapping.put(b, last);
                last--;
            }
        }
    }

    public int pick() {
        int idx = random.nextInt(bound);
        return mapping.getOrDefault(idx, idx);  // remap if blacklisted, else return directly
    }
}

import random

class Solution:
    def __init__(self, n: int, blacklist: list[int]):
        self.bound = n - len(blacklist)
        black_set = set(blacklist)
        self.mapping = {}

        last = n - 1
        for b in blacklist:
            if b < self.bound:
                while last in black_set:
                    last -= 1
                self.mapping[b] = last
                last -= 1

    def pick(self) -> int:
        idx = random.randrange(self.bound)
        return self.mapping.get(idx, idx)