Hash Map Cheatsheet（雜湊表速查）

d = {'a': 1, 'b': 2}
d['a']  # -> 1

d.get('a')  # -> 1

d.get('c', 0)  # -> 0

d.get('z')

#-------------------------------------------------------------------------------
# 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}
x.items()  # -> 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
mydict = {'a':['a1','a2','a3'], 'b':['b1','b2','b3']}

res = [mydict[x] for x in mydict]

print (res)  # -> [['a1', 'a2', 'a3'], ['b1', 'b2', 'b3']]

# python
# LC 1 - Two Sum
# IDEA: one pass; look up the complement among the values already seen, THEN record this value
# time = O(n), space = O(n)
def twoSum(nums, target):
    seen = {}                          # {value: index}, only indices < i
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:               # the partner sits strictly to the left
            return [seen[need], i]
        seen[x] = i                    # record after the lookup: x never pairs with itself
    return []

// java
// LC 1 - Two Sum
// IDEA: one pass; look up the complement among the values already seen, then record this value
// time = O(n), space = O(n)
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();   // {value: index}, only indices < i
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];
        if (seen.containsKey(need)) {
            return new int[]{seen.get(need), i};
        }
        seen.put(nums[i], i);
    }
    return new int[0];
}

nums = [3,2,4], target = 6
i=0  x=3  need=3  not in {}            seen={3:0}
i=1  x=2  need=4  not in seen          seen={3:0, 2:1}
i=2  x=4  need=2  seen[2]=1            -> [1, 2]

# python
# LC 242 - Valid Anagram
# IDEA: count s up and t down in one map; every count back at 0 <=> same multiset
# time = O(n), space = O(k)   k = distinct characters (26 for lowercase)
def isAnagram(s, t):
    if len(s) != len(t):
        return False
    count = {}
    for a, b in zip(s, t):
        count[a] = count.get(a, 0) + 1
        count[b] = count.get(b, 0) - 1
    for c in count.values():
        if c != 0:
            return False
    return True

// java
// LC 242 - Valid Anagram
// IDEA: lowercase only -> an int[26] is the count map; s counts up, t counts down
// time = O(n), space = O(1)   26 counters
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }
    for (int c : count) {
        if (c != 0) {
            return false;
        }
    }
    return true;
}

last_idx - first_idx + 1 == number_of_occurrences

# python
# LC 4038 - Count Integers Appearing in a Single Block
# IDEA: {val: [idx, ...]}, then a value is special iff its indices are consecutive
# time = O(n), space = O(n)
from collections import defaultdict

def countSpecialIntegers(nums: list) -> int:
    my_map = defaultdict(list)
    for i, v in enumerate(nums):
        my_map[v].append(i)

    cnt = 0
    for k in my_map:
        idxs = my_map[k]
        # span == count  <=>  indices are consecutive
        if idxs[-1] - idxs[0] + 1 == len(idxs):
            cnt += 1
    return cnt

# [1,1,2,2,3] -> 1:[0,1] 2:[2,3] 3:[4]     -> every span == count -> 3
# [1,2,1]     -> 1:[0,2] -> 2-0+1 = 3 != 2 -> broken -> only 2 is special -> 1

# python
# LC 4038 - keep only (first_idx, last_idx, count) per value
# IDEA: the span check reads only the first index, the last index and the count
# time = O(n), space = O(k), k = number of distinct values
def countSpecialIntegers(nums: list) -> int:
    info = {}                                  # {val: [first, last, cnt]}
    for i, v in enumerate(nums):
        if v not in info:
            info[v] = [i, i, 1]
        else:
            info[v][1] = i
            info[v][2] += 1
    return sum(1 for first, last, cnt in info.values() if last - first + 1 == cnt)

# python
# LC 49 - Group Anagrams
# IDEA: canonical key = the word's letters sorted; anagrams share it, nothing else does
# time = O(n * k log k), space = O(n * k)   n words of length <= k
def groupAnagrams(strs):
    groups = {}                          # {sorted letters: [words]}
    for word in strs:
        key = "".join(sorted(word))
        if key not in groups:
            groups[key] = []
        groups[key].append(word)
    return list(groups.values())

// java
// LC 49 - Group Anagrams
// IDEA: canonical key = the word's letters sorted; anagrams share it, nothing else does
// time = O(n * k log k), space = O(n * k)
public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String word : strs) {
        char[] letters = word.toCharArray();
        Arrays.sort(letters);
        String key = new String(letters);     // a String, not the char[]: arrays hash by identity
        if (!groups.containsKey(key)) {
            groups.put(key, new ArrayList<>());
        }
        groups.get(key).add(word);
    }
    return new ArrayList<>(groups.values());
}

# python
# LC 149 - Max Points on a Line
# IDEA: anchor at each point, group the others by a gcd-normalized slope key
# time = O(n^2), space = O(n)
from collections import defaultdict
from math import gcd

def maxPoints(points: list) -> int:
    n = len(points)
    if n <= 2:
        return n
    best = 1
    for i in range(n):
        slope_count = defaultdict(int)
        x1, y1 = points[i]
        for j in range(i + 1, n):
            dx, dy = points[j][0] - x1, points[j][1] - y1
            g = gcd(abs(dx), abs(dy))
            if g:
                dx, dy = dx // g, dy // g
            if dx < 0 or (dx == 0 and dy < 0):     # canonical sign
                dx, dy = -dx, -dy
            slope_count[(dx, dy)] += 1
            best = max(best, slope_count[(dx, dy)] + 1)   # +1 = anchor point
    return best

// java
// LC 149 - Max Points on a Line
// IDEA: anchor at each point, group the others by a gcd-normalized slope key
// time = O(n^2), space = O(n)
public int maxPoints(int[][] points) {
    int n = points.length;
    if (n <= 2) return n;
    int best = 1;
    for (int i = 0; i < n; i++) {
        Map<String, Integer> slopeCount = new HashMap<>();
        for (int j = i + 1; j < n; j++) {
            int dx = points[j][0] - points[i][0];
            int dy = points[j][1] - points[i][1];
            int g = gcd(Math.abs(dx), Math.abs(dy));
            if (g != 0) { dx /= g; dy /= g; }
            // canonical direction: force dx > 0, or dx == 0 && dy > 0
            if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; }
            String key = dx + "/" + dy;
            int cnt = slopeCount.merge(key, 1, Integer::sum);
            best = Math.max(best, cnt + 1);   // +1 for the anchor point itself
        }
    }
    return best;
}

private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

pair = (min(x, y), max(x, y))      # (2, 5) and (5, 2) -> the same key (2, 5)
pair_count[pair] += 1
best = max(best, pair_count[pair]) # running max: counts only go up, so no second pass

(x, y) or (y, x)   -> (y, y)   unequal -> equal       +1
(x, x)             -> (y, y)   equal   -> equal        0   (never lost)
(x, a), a != y     -> (y, a)   unequal -> unequal      0
anything without x -> untouched                        0

answer = (adjacent pairs already equal) + max over x != y of (adjacent {x, y} pairs)

# python
# LC 4066 - Maximum Equal Adjacent Pairs After at Most One Replacement
# IDEA: already-equal pairs survive any replacement; x -> y gains one per adjacent {x, y},
#       so count adjacent unequal pairs under an unordered (min, max) key and take the max
# time = O(n), space = O(n)
from collections import defaultdict

def maxEqualAdjacentPairs(nums: list) -> int:
    already_equal = 0
    unequal_pair_cnt = defaultdict(int)   # {(smaller, larger): adjacent occurrences}
    max_newly_equal = 0                   # 0 = do no operation (e.g. [1, 1, 1])

    for i in range(len(nums) - 1):
        x, y = nums[i], nums[i + 1]
        if x == y:
            already_equal += 1
        else:
            # (2, 5) and (5, 2) are fixed by the same replacement -> one key
            pair = (min(x, y), max(x, y))
            unequal_pair_cnt[pair] += 1
            max_newly_equal = max(max_newly_equal, unequal_pair_cnt[pair])

    return already_equal + max_newly_equal

// java
// LC 4066 - Maximum Equal Adjacent Pairs After at Most One Replacement
// IDEA: same unordered (min, max) key, packed into one long (values <= 10^9 fit in 32 bits)
// time = O(n), space = O(n)
public int maxEqualAdjacentPairs(int[] nums) {
    int alreadyEqual = 0;
    int maxNewlyEqual = 0;
    Map<Long, Integer> unequalPairCnt = new HashMap<>();

    for (int i = 0; i + 1 < nums.length; i++) {
        int x = nums[i];
        int y = nums[i + 1];
        if (x == y) {
            alreadyEqual++;
        } else {
            long small = Math.min(x, y);
            long large = Math.max(x, y);
            long pairKey = (small << 32) | large;   // canonical order, one key per {x, y}
            int cnt = unequalPairCnt.merge(pairKey, 1, Integer::sum);
            maxNewlyEqual = Math.max(maxNewlyEqual, cnt);
        }
    }
    return alreadyEqual + maxNewlyEqual;
}

nums = [1,2,1,2,1]
  i  pair    key     cnt   max_newly_equal
  0  (1,2)   (1,2)   1     1
  1  (2,1)   (1,2)   2     2      <- an ordered key would have started (2,1) at 1
  2  (1,2)   (1,2)   3     3
  3  (2,1)   (1,2)   4     4
  already_equal = 0  ->  answer = 0 + 4 = 4   (replace 1 -> 2: [2,2,2,2,2])

nums = [1,2,3,2]  -> {1,2}: 1, {2,3}: 2  -> 0 + 2 = 2
nums = [1,1,1]    -> already_equal = 2, map empty -> 2 + 0 = 2   (no operation)

# python
# LC 560 - Subarray Sum Equals K
# IDEA: count the earlier prefix sums equal to (prefix - k); look up BEFORE recording the current prefix
# time = O(n), space = O(n)
def subarraySum(nums, k):
    count_of_prefix = {0: 1}             # the empty prefix: subarrays that start at index 0
    prefix = 0
    total = 0
    for x in nums:
        prefix += x
        total += count_of_prefix.get(prefix - k, 0)   # every earlier start that closes here
        count_of_prefix[prefix] = count_of_prefix.get(prefix, 0) + 1
    return total

// java
// LC 560 - Subarray Sum Equals K
// IDEA: count the earlier prefix sums equal to (prefix - k); look up before recording the current prefix
// time = O(n), space = O(n)
public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> countOfPrefix = new HashMap<>();
    countOfPrefix.put(0, 1);             // the empty prefix
    int prefix = 0;
    int total = 0;
    for (int x : nums) {
        prefix += x;
        total += countOfPrefix.getOrDefault(prefix - k, 0);
        countOfPrefix.put(prefix, countOfPrefix.getOrDefault(prefix, 0) + 1);
    }
    return total;
}

nums = [1,1,1], k = 2
x  prefix  look up prefix-k   total  map after
1  1       -1 -> 0            0      {0:1, 1:1}
1  2        0 -> 1            1      {0:1, 1:1, 2:1}
1  3        1 -> 1            2      {0:1, 1:1, 2:1, 3:1}
-> 2

sum(nums[i..j]) = pre[j+1] - pre[i]
fixed j  ->  maximise  = minimise pre[i]   over every i with nums[i] in {nums[j]-k, nums[j]+k}
best[v]  = min pre[i] over every i seen so far with nums[i] == v

# python
# LC 3026 - Maximum Good Subarray Sum
# IDEA: best[v] = min prefix sum just before an index holding v; close at x from v = x-k or x+k
# time = O(n), space = O(n)
def maximumSubarraySum(nums: list, k: int) -> int:
    best = {}                       # {start value: min prefix sum before it}
    res = float('-inf')
    pre = 0                         # pre = sum(nums[:j]), i.e. before x
    for x in nums:
        for v in (x - k, x + k):    # the two start values that make [i..j] good
            if v in best:
                res = max(res, pre + x - best[v])
        # record x as a future START with the prefix BEFORE it
        if x not in best or pre < best[x]:
            best[x] = pre
        pre += x
    return 0 if res == float('-inf') else res

// java
// LC 3026 - Maximum Good Subarray Sum
// IDEA: same map; long, because n * |nums[i]| reaches 1e14
// time = O(n), space = O(n)
public long maximumSubarraySum(int[] nums, int k) {
    Map<Integer, Long> best = new HashMap<>();   // {start value: min prefix before it}
    long res = Long.MIN_VALUE, pre = 0;
    for (int x : nums) {
        for (int v : new int[]{x - k, x + k}) {      // |x ± k| <= 2e9 still fits an int
            Long p = best.get(v);
            if (p != null) res = Math.max(res, pre + x - p);
        }
        best.merge(x, pre, Math::min);
        pre += x;
    }
    return res == Long.MIN_VALUE ? 0 : res;
}

x    pre(before x)  look up x-k, x+k          candidate          best after
-1    0             -4, 2   -> none            -                  {-1:0}
 3   -1              0, 6   -> none            -                  {-1:0, 3:-1}
 2    2             -1, 5   -> -1: 2+2-0 = 4   4  ([-1,3,2])      {..., 2:2}
 4    4              1, 7   -> none            -                  {..., 4:4}
 5    8              2, 8   -> 2: 8+5-2 = 11   11 ([2,4,5])       {..., 5:8}
-> 11

# python
# LC 438 - Find All Anagrams in a String
# IDEA: fixed window of len(p); add the right char, drop the one that fell off the left, compare count maps
# time = O(26 * n), space = O(26)
def findAnagrams(s, p):
    m = len(p)
    if m > len(s):
        return []
    need = {}
    for ch in p:
        need[ch] = need.get(ch, 0) + 1
    window = {}
    starts = []
    for right in range(len(s)):
        ch = s[right]
        window[ch] = window.get(ch, 0) + 1
        if right >= m:                       # one too long: drop s[right - m]
            out = s[right - m]
            window[out] -= 1
            if window[out] == 0:
                del window[out]              # a zero entry would make window != need
        if right >= m - 1 and window == need:
            starts.append(right - m + 1)
    return starts

// java
// LC 438 - Find All Anagrams in a String
// IDEA: two int[26] count arrays; slide by one, compare with Arrays.equals
// time = O(26 * n), space = O(1)
public List<Integer> findAnagrams(String s, String p) {
    List<Integer> starts = new ArrayList<>();
    int m = p.length();
    if (m > s.length()) {
        return starts;
    }
    int[] need = new int[26];
    int[] window = new int[26];
    for (int i = 0; i < m; i++) {
        need[p.charAt(i) - 'a']++;
    }
    for (int right = 0; right < s.length(); right++) {
        window[s.charAt(right) - 'a']++;
        if (right >= m) {
            window[s.charAt(right - m) - 'a']--;    // drop the char that left the window
        }
        if (right >= m - 1 && Arrays.equals(window, need)) {
            starts.add(right - m + 1);
        }
    }
    return starts;
}

# python
# LC 953 - Verifying an Alien Dictionary
# IDEA: char -> rank map, then compare adjacent words rank by rank
# time = O(total chars), space = O(1)   26 keys
def isAlienSorted(words, order):
    rank = {}
    for i, c in enumerate(order):
        rank[c] = i

    def in_order(a, b):
        for ca, cb in zip(a, b):
            if rank[ca] != rank[cb]:
                return rank[ca] < rank[cb]   # the first differing letter decides
        return len(a) <= len(b)              # common prefix: the shorter word must come first

    for i in range(len(words) - 1):
        if not in_order(words[i], words[i + 1]):
            return False
    return True

# python
# LC 791 - Custom Sort String
# IDEA: rank map as a sort key; unranked chars get rank len(order) (stable sort keeps them last)
# time = O(n log n + m), space = O(n)
def customSortString(order: str, s: str) -> str:
    rank = {c: i for i, c in enumerate(order)}
    return "".join(sorted(s, key=lambda c: rank.get(c, len(order))))

// java
// LC 953 - Verifying an Alien Dictionary
// IDEA: char -> rank map turns an arbitrary alphabet into comparable ints
// time = O(total chars), space = O(1)  (26 keys)
public boolean isAlienSorted(String[] words, String order) {
    int[] rank = new int[26];                       // char -> position in `order`
    for (int i = 0; i < order.length(); i++) rank[order.charAt(i) - 'a'] = i;
    for (int i = 0; i + 1 < words.length; i++) {
        if (!inOrder(words[i], words[i + 1], rank)) return false;
    }
    return true;
}

private boolean inOrder(String a, String b, int[] rank) {
    int n = Math.min(a.length(), b.length());
    for (int i = 0; i < n; i++) {
        int ra = rank[a.charAt(i) - 'a'], rb = rank[b.charAt(i) - 'a'];
        if (ra != rb) return ra < rb;
    }
    return a.length() <= b.length();                // prefix must come first: "app" < "apple"
}

// LC 791 - Custom Sort String  (counting sort, no comparator needed)
// time = O(n + m), space = O(1)
public String customSortString(String order, String s) {
    int[] cnt = new int[26];
    for (char c : s.toCharArray()) cnt[c - 'a']++;
    StringBuilder sb = new StringBuilder();
    for (char c : order.toCharArray()) {            // ranked chars first, in rank order
        while (cnt[c - 'a'] > 0) { sb.append(c); cnt[c - 'a']--; }
    }
    for (char c = 'a'; c <= 'z'; c++) {             // unranked chars: any order
        while (cnt[c - 'a'] > 0) { sb.append(c); cnt[c - 'a']--; }
    }
    return sb.toString();
}

# python
# LC 105 - Construct Binary Tree from Preorder and Inorder Traversal
# IDEA: {value: index in inorder} → O(1) root split
# time = O(n), space = O(n)
def buildTree(preorder: list, inorder: list):
    idx = {v: i for i, v in enumerate(inorder)}   # values are unique (given)
    pre = [0]                                     # pointer into preorder

    def build(lo, hi):
        if lo > hi:
            return None
        node = TreeNode(preorder[pre[0]])
        pre[0] += 1
        mid = idx[node.val]                       # O(1) instead of inorder.index(...)
        node.left = build(lo, mid - 1)
        node.right = build(mid + 1, hi)
        return node

    return build(0, len(inorder) - 1)

# python
# LC 205 - Isomorphic Strings
# IDEA: two maps, s->t and t->s; any disagreement in either direction breaks the bijection
# time = O(n), space = O(k)   k = distinct characters
def isIsomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    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

# python
# LC 290 - Word Pattern
# IDEA: the same two maps, letter <-> word; check the lengths first
# time = O(n), space = O(n)
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

// java
// LC 205 - Isomorphic Strings
// IDEA: two maps, s->t and t->s; any disagreement in either direction breaks the bijection
// time = O(n), space = O(k)
public boolean isIsomorphic(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    Map<Character, Character> s2t = new HashMap<>();
    Map<Character, Character> t2s = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
        char a = s.charAt(i);
        char b = t.charAt(i);
        if (s2t.containsKey(a) && s2t.get(a) != b) {
            return false;
        }
        if (t2s.containsKey(b) && t2s.get(b) != a) {
            return false;
        }
        s2t.put(a, b);
        t2s.put(b, a);
    }
    return true;
}

# python
# LC 133 - Clone Graph
# IDEA: copies = {original node: its clone}; register the clone BEFORE visiting neighbours, so cycles hit the map
# time = O(V + E), space = O(V)
class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node):
    if node is None:
        return None
    copies = {}

    def clone(original):
        if original in copies:
            return copies[original]
        copy = Node(original.val)
        copies[original] = copy                  # register first: a cycle back here stops
        for neighbor in original.neighbors:
            copy.neighbors.append(clone(neighbor))
        return copy

    return clone(node)

// java
// LC 133 - Clone Graph
// IDEA: copies = {original node: its clone}; register the clone before visiting neighbours
// time = O(V + E), space = O(V)
private Map<Node, Node> copies = new HashMap<>();

public Node cloneGraph(Node node) {
    if (node == null) {
        return null;
    }
    if (copies.containsKey(node)) {
        return copies.get(node);
    }
    Node copy = new Node(node.val, new ArrayList<>());
    copies.put(node, copy);                       // before the neighbours: cycles stop here
    for (Node neighbor : node.neighbors) {
        copy.neighbors.add(cloneGraph(neighbor));
    }
    return copy;
}

# python
# LC 710 - Random Pick with Blacklist
# IDEA: draw from [0, bound); remap each blacklisted slot below bound to a valid tail value
# time = O(B) to build, O(1) per pick, space = O(B)
import random

class Solution:
    def __init__(self, n: int, blacklist: list):
        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:         # skip tail values that are blacklisted too
                    last -= 1
                self.mapping[b] = last
                last -= 1

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

// java
// LC 710 - Random Pick with Blacklist
// IDEA: draw from [0, bound); remap each blacklisted slot below bound to a valid tail value
// time = O(B) to build, O(1) per pick, space = O(B)
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
    }
}

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

# python
# LC 692 - Top K Frequent Words
# IDEA: count with a map, heapify (-count, word) so ties pop alphabetically, pop k times
# time = O(n + k log n), space = O(n)
import heapq

def topKFrequent(words, k):
    count = {}
    for word in words:
        count[word] = count.get(word, 0) + 1
    heap = []
    for word, freq in count.items():
        heap.append((-freq, word))           # negate: heapq is a min-heap
    heapq.heapify(heap)                      # O(n), cheaper than n pushes
    result = []
    for _ in range(k):
        result.append(heapq.heappop(heap)[1])
    return result

// java
// LC 692 - Top K Frequent Words
// IDEA: count with a map; a heap ordered by count desc, then word asc; poll k times
// time = O(n log n), space = O(n)
public List<String> topKFrequent(String[] words, int k) {
    Map<String, Integer> count = new HashMap<>();
    for (String word : words) {
        count.put(word, count.getOrDefault(word, 0) + 1);
    }
    PriorityQueue<String> heap = new PriorityQueue<>((a, b) -> {
        int byCount = Integer.compare(count.get(b), count.get(a));   // higher count first
        if (byCount != 0) {
            return byCount;
        }
        return a.compareTo(b);                                      // tie: alphabetical
    });
    heap.addAll(count.keySet());
    List<String> result = new ArrayList<>();
    for (int i = 0; i < k; i++) {
        result.add(heap.poll());
    }
    return result;
}

# python
# LC 692 - Top K Frequent Words (buckets by count)
# IDEA: buckets[c] = words seen exactly c times; walk counts high -> low, sorting each bucket for the tie rule
# time = O(n log n) worst case (every word in one bucket), O(n) when the counts are distinct, space = O(n)
def topKFrequent_buckets(words, k):
    count = {}
    for word in words:
        count[word] = count.get(word, 0) + 1
    buckets = [[] for _ in range(len(words) + 1)]   # a count is at most len(words)
    for word, freq in count.items():
        buckets[freq].append(word)
    result = []
    for freq in range(len(words), 0, -1):
        for word in sorted(buckets[freq]):          # the tie rule: alphabetical within one count
            result.append(word)
            if len(result) == k:
                return result
    return result

# python
# floor / ceiling on a SortedDict (pip install sortedcontainers; preinstalled on LeetCode)
# IDEA: bisect_* returns an index into the sorted keys; guard it, then read the key
# time = O(log n) per query, space = O(n)
from sortedcontainers import SortedDict

def floor_key(d, x):                       # Java floorKey(x): largest key <= x, or None
    i = d.bisect_right(x) - 1
    return d.keys()[i] if i >= 0 else None

def ceiling_key(d, x):                     # Java ceilingKey(x): smallest key >= x, or None
    i = d.bisect_left(x)
    return d.keys()[i] if i < len(d) else None

d = SortedDict({10: "a", 20: "b", 30: "c"})
print(floor_key(d, 25), ceiling_key(d, 25))   # 20 30
print(floor_key(d, 5), ceiling_key(d, 35))    # None None
print(list(d.irange(15, 30)))                 # [20, 30]

// java
// floor / ceiling / range on a TreeMap
// IDEA: a red-black tree keyed in order; floorKey / ceilingKey return a key or null
// time = O(log n) per query, space = O(n)
TreeMap<Integer, String> d = new TreeMap<>();
d.put(10, "a");
d.put(20, "b");
d.put(30, "c");
Integer floor = d.floorKey(25);            // 20
Integer ceiling = d.ceilingKey(25);        // 30
Integer none = d.floorKey(5);              // null: guard it before unboxing
SortedMap<Integer, String> range = d.subMap(15, true, 30, true);   // {20=b, 30=c}

# 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