Trie & Design

Problem: Implement a trie with insert(word), search(word) (is this exact word stored?) and startsWith(prefix) (does any stored word start with it?).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ word.length, prefix.length ≤ 2000 · word and prefix consist only of lowercase English letters. · At most 3 * 10⁴ calls in total will be made to insert, search, and startsWith.

From brute force to the pattern: Storing the words in a list makes startsWith scan everything: O(n · L). A trie answers both queries in O(L).

Spot it: Many words that share prefixes, and questions about prefixes → a trie: each node is one character position, its children are the possible next characters, and a flag marks where a word ends.

Approach:

1. A TrieNode has children (a dict char → TrieNode) and is_end.
2. insert: walk from the root, creating missing children, and set is_end = True on the last node.
3. A helper _walk(text) follows the characters and returns the final node, or None if a character is missing.
4. search needs that node to exist and be a word end; startsWith only needs it to exist.

class TrieNode:
    def __init__(self):
        self.children = {}     # next character -> TrieNode
        self.is_end = False    # does a stored word end exactly here?


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def _walk(self, text):
        # follow text's characters; None if the path breaks off
        node = self.root
        for ch in text:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_end

    def startsWith(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

What the code is doing, line by line:

1. TrieNode.children: a dictionary, so each step down is an O(1) lookup and only characters that actually occur take memory.
2. insert: create a child only when it's missing, so shared prefixes share nodes ("app" and "apple" share a → p → p).
3. node.is_end = True: marks a whole word. Without it, search("app") couldn't tell a word from a mere prefix of "apple".
4. _walk: the shared descent used by both queries.
5. search: the path must exist and end on a word. startsWith: the path existing is enough.

Dry run on the example:

LeetCode Example 1: insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app") → True, False, True, True.

call	path walked	result
insert("apple")	root → a → p → p → l → e (all created); e.is_end = True	—
search("apple")	reaches e, which is a word end	True
search("app")	reaches the second p, is_end is False	False
startsWith("app")	reaches the second p	True
insert("app")	path exists; set the second p's is_end = True	—
search("app")	reaches the second p, now a word end	True

Edge cases to test:

• search for a prefix that isn't a whole word → False.
• Inserting the same word twice.
• One word being a prefix of another, e.g. app and apple.

Complexity: O(L) time per operation for a word of length L; O(total characters inserted) space.

Problem: Design a cache with a fixed capacity. get(key) returns the value or -1; put(key, value) inserts or updates, and when the cache is over capacity it evicts the least recently used key. Both must be O(1).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ capacity ≤ 3000 · 0 ≤ key ≤ 10⁴ · 0 ≤ value ≤ 10⁵ · At most 2 * 10⁵ calls will be made to get and put.

From brute force to the pattern: A list ordered by recency makes moving an item O(n); a dict alone forgets the order. Map + doubly linked list does every operation in O(1) (OrderedDict packages the same idea).

Spot it: Two needs at once: find a key in O(1) (hash map) and move any entry to "most recent" or drop the oldest in O(1) (doubly linked list). The map stores key → list node, which glues the two together.

Key insight: Keep two sentinel nodes, head (least recent side) and tail (most recent side). Every access unlinks the node and re-inserts it just before tail; eviction removes head.next. (Python's OrderedDict packages exactly this, with move_to_end and popitem(last=False).)

Approach:

1. A Node holds key, val, prev, next. head and tail are dummy nodes linked to each other.
2. _remove(node) unlinks a node; _add_to_end(node) inserts it just before tail.
3. get: missing → -1. Otherwise move the node to the end (it's now most recent) and return its value.
4. put: if the key exists, remove its old node. Create a new node, add it at the end, and store it in the map.
5. If the map is over capacity, evict head.next (the least recent) from the list and from the map.

class Node:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.nodes = {}                     # key -> Node in the list
        # dummies: head.next is the LEAST recent, tail.prev the MOST recent
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_end(self, node):
        last = self.tail.prev
        last.next = node
        node.prev = last
        node.next = self.tail
        self.tail.prev = node

    def get(self, key: int) -> int:
        if key not in self.nodes:
            return -1
        node = self.nodes[key]
        # touched: move it to the most-recent end
        self._remove(node)
        self._add_to_end(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.nodes:
            self._remove(self.nodes[key])
        node = Node(key, value)
        self._add_to_end(node)
        self.nodes[key] = node
        if len(self.nodes) > self.capacity:
            oldest = self.head.next
            self._remove(oldest)
            del self.nodes[oldest.key]      # the node remembers its key for this

What the code is doing, line by line:

1. self.nodes: key → Node, so get and put find a node without scanning the list.
2. head / tail dummies: every real node always has a prev and a next, so _remove and _add_to_end need no None checks.
3. _remove(node): link its neighbours to each other. O(1) because the list is doubly linked (we know prev).
4. _add_to_end(node): splice it in just before tail, marking it most recent.
5. get: a hit counts as a use, so move the node to the end.
6. put: replace any old node, add the new one at the end, and evict head.next if over capacity. Storing key inside the node lets us delete it from the map.

Dry run on the example:

LeetCode Example 1, capacity = 2: put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4) → 1, -1, -1, 3, 4.

call	list after (least → most recent)	returns
put(1, 1)	1	—
put(2, 2)	1, 2	—
get(1)	2, 1	1
put(3, 3)	2, 1, 3 → over capacity, evict 2 → 1, 3	—
get(2)	1, 3	−1
put(4, 4)	evict 1 → 3, 4	—
get(1)	3, 4	−1
get(3)	4, 3	3
get(4)	3, 4	4

Edge cases to test:

• put on an existing key updates it and makes it most recent.
• Capacity 1.
• get on a missing key → −1.

Complexity: O(1) time for get and put; O(capacity) space.

Problem: Support addWord(word) and search(word), where word may contain . meaning "any single letter".

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ word.length ≤ 25 · word in addWord consists of lowercase English letters. · word in search consist of '.' or lowercase English letters. · There will be at most 2 dots in word for search queries. · At most 10⁴ calls will be made to addWord and search.

From brute force to the pattern: Comparing the pattern against every stored word is O(n · L) per search. A trie follows only matching branches, and only . branches out.

Spot it: Store the words in a trie as in LeetCode 208. A normal letter follows one child; a . must try every child, which turns the search into a DFS over the trie.

Approach:

1. addWord is the trie's insert.
2. search uses dfs(node, i): can word[i:] be matched starting at node?
3. If i == len(word), succeed only if node.is_end.
4. For ., return True if any child matches the rest; for a letter, follow that child if it exists.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False


class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        def dfs(node, i):
            if i == len(word):
                return node.is_end
            ch = word[i]
            if ch == ".":
                # a wildcard: any child may continue the match
                for child in node.children.values():
                    if dfs(child, i + 1):
                        return True
                return False
            if ch not in node.children:
                return False
            return dfs(node.children[ch], i + 1)

        return dfs(self.root, 0)

What the code is doing, line by line:

1. addWord: identical to Trie.insert.
2. dfs(node, i): we stand on node having matched word[:i].
3. if i == len(word): return node.is_end: all characters matched; it counts only if a word ends here.
4. if ch == ".": try each child in turn and stop at the first success. This is the only place the search branches.
5. A normal letter has at most one way forward: its child, if it exists.

Dry run on the example:

After addWord("bad"), addWord("dad"), addWord("mad") (LeetCode Example 1): search("pad") → False, search("bad") → True, search(".ad") → True, search("b..") → True. Tracing search(".ad"):

dfs at	word[i]	choices	result
root, i = 0	.	try children b, d, m	…
b, i = 1	a	child a exists	…
b → a, i = 2	d	child d exists	…
b → a → d, i = 3	(end)	is_end is True	True (returned up; d and m are never tried)

Edge cases to test:

• A pattern of only dots, e.g. "...".
• A pattern longer than every word.
• A pattern that matches a prefix but not a whole word.

Complexity: addWord: O(L). search: O(L) without dots, up to O(26^d · L) with d dots in the worst case.

Problem: Design a set with insert(val), remove(val) (each returns whether it changed the set) and getRandom() (each element equally likely), all in average O(1) time.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: -2³¹ ≤ val ≤ 2³¹ - 1 · At most 2 * 10⁵ calls will be made to insert, remove, and getRandom. · There will be at least one element in the data structure when getRandom is called.

From brute force to the pattern: A set can't pick a random element in O(1); a list can't remove from the middle in O(1). Using both, plus swap-with-last removal, makes every operation average O(1).

Spot it: A hash set gives O(1) insert/remove but can't pick a random element in O(1); a list can (random.choice) but removes in O(n). Use both: the list holds the values, and a map records each value's index in the list.

Key insight: To delete from the middle of the list in O(1), move the last value into the hole, update its index in the map, then pop() the end.

Approach:

1. insert: if present, return False; else append to the list and store its index.
2. remove: if absent, return False. Otherwise copy the last value into the removed value's slot, fix that value's index, pop the list, and delete the removed value from the map.
3. getRandom: random.choice(self.values).

import random

class RandomizedSet:
    def __init__(self):
        self.values = []          # the elements, for O(1) random picks
        self.index_of = {}        # value -> its position in self.values

    def insert(self, val: int) -> bool:
        if val in self.index_of:
            return False
        self.index_of[val] = len(self.values)
        self.values.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.index_of:
            return False
        hole = self.index_of[val]
        last = self.values[-1]
        # move the last value into the hole, then drop the end
        self.values[hole] = last
        self.index_of[last] = hole
        self.values.pop()
        del self.index_of[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.values)

What the code is doing, line by line:

1. self.values: a plain list, so random.choice picks any element uniformly in O(1).
2. self.index_of: lets remove find the element's position without searching.
3. insert: the new value goes at the end, so its index is the old length.
4. remove: self.values[hole] = last overwrites the removed value with the last one, and self.index_of[last] = hole records its new position. Popping the end is O(1).
5. The order matters when val is the last value: we update its index, then del self.index_of[val] removes it anyway, so the result is still correct.

Dry run on the example:

insert(1), insert(2), insert(3), remove(1), insert(2), getRandom():

call	values	index_of	returns
insert(1)	[1]	{1: 0}	True
insert(2)	[1, 2]	{1: 0, 2: 1}	True
insert(3)	[1, 2, 3]	{1: 0, 2: 1, 3: 2}	True
remove(1)	3 moves into slot 0 → [3, 2]	{2: 1, 3: 0}	True
insert(2)	[3, 2]	unchanged	False
getRandom()	[3, 2]	unchanged	3 or 2, each with probability ½

Edge cases to test:

• Removing the last element (the swap is with itself).
• Inserting a value that's already present → False.
• Removing a missing value → False.

Complexity: Average O(1) time for every operation, O(n) space.

Problem: Return the maximum nums[i] XOR nums[j].

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 2 * 10⁵ · 0 ≤ nums[i] ≤ 2³¹ - 1

From brute force to the pattern: All pairs: O(n²). Bit trie: O(31n).

Spot it: XOR is maximised by making the highest bits differ. Store every number's bits (high to low) in a binary trie; for each number, greedily walk to the child with the opposite bit at each level.

Why not another pattern? Trying all pairs is O(n²) with n = 2·10⁵.

Approach:

1. Insert each number's 31 bits from the top into a trie of dicts.
2. For each number, walk the trie preferring the opposite bit; each successful choice sets that bit of the XOR.
3. Track the maximum.

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        root = {}
        for x in nums:
            node = root
            for b in range(30, -1, -1):
                bit = x >> b & 1
                node = node.setdefault(bit, {})  # path of bits, highest first
        best = 0
        for x in nums:
            node = root
            xor = 0
            for b in range(30, -1, -1):
                bit = x >> b & 1
                if 1 - bit in node:
                    xor |= 1 << b  # a number with the opposite bit exists: this bit of the XOR is 1
                    node = node[1 - bit]
                else:
                    node = node[bit]
            best = max(best, xor)
        return best

What the code is doing, line by line:

1. A 1 in a higher bit beats any combination of lower bits, so the greedy choice per level is optimal.
2. Every number is in the trie, so a path always exists.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• One number → 0.
• All equal → 0.
• Zero in the array.

Complexity: O(31 · n) time and space.

Problem: Return the queries that can be turned into some dictionary word by changing at most two letters (all words have equal length).

Solve it on LeetCode ↗

Constraints: 1 ≤ queries.length, dictionary.length ≤ 100 · n == queries[i].length == dictionary[j].length · 1 ≤ n ≤ 100 · All queries[i] and dictionary[j] are composed of lowercase English letters.

From brute force to the pattern: This is the direct approach and it's fast enough for the limits; a trie with a 2-mismatch budget scales further.

Spot it: Equal lengths make an "edit" a letter substitution, so it's a Hamming distance check. With ≤ 100 words each, comparing every query with every dictionary word (stopping early) is fast. (A trie with a mismatch budget is the scalable variant.)

Why not another pattern? Generating all words within two substitutions (C(n,2) · 26²) is far bigger than the dictionary.

Approach:

1. For each query, for each dictionary word: count mismatches, stopping after 3.
2. Keep the query if some word has ≤ 2 mismatches.

class Solution:
    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
        def close(a, b):
            diff = 0
            for x, y in zip(a, b):
                if x != y:
                    diff += 1
                    if diff > 2:
                        return False  # already too different
            return True

        return [q for q in queries if any(close(q, w) for w in dictionary)]  # keeps the original order

What the code is doing, line by line:

1. Same-length words differ only by substitutions, so count mismatched positions.
2. Stopping at 3 mismatches keeps each comparison short.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A query equal to a dictionary word.
• Exactly two mismatches.
• No matches → [].

Complexity: O(q · d · n) time, O(1) extra space.

Problem: Return the longest common prefix length (in digits) between any x in arr1 and any y in arr2.

Solve it on LeetCode ↗

Constraints: 1 ≤ arr1.length, arr2.length ≤ 5 * 10⁴ · 1 ≤ arr1[i], arr2[i] ≤ 10⁸

From brute force to the pattern: All pairs: O(nm · d). Prefix set: O((n + m) · d).

Spot it: Prefixes of numbers are x, x // 10, x // 100, … — a path in a digit trie. A hash set of all prefixes of arr1 works the same way: for each y, strip digits until a prefix is found.

Why not another pattern? Comparing all pairs is O(n · m · digits) with n, m = 5·10⁴.

Approach:

1. Add every prefix of every x to a set.
2. For each y, while y > 0 and y not in the set: y //= 10.
3. The answer is the longest found prefix's digit count.

class Solution:
    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
        prefixes = set()
        for x in arr1:
            while x:
                prefixes.add(x)  # x, x // 10, x // 100, ...
                x //= 10
        best = 0
        for y in arr2:
            while y and y not in prefixes:
                y //= 10  # drop the last digit
            if y:
                best = max(best, len(str(y)))
        return best

What the code is doing, line by line:

1. Dropping the last digit (// 10) is moving up one level in the digit trie.
2. The first prefix of y found in the set is its longest common prefix with any x.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No common first digit → 0.
• Equal numbers.
• Different lengths (e.g. 1 and 100).

Complexity: O((n + m) · digits) time, O(n · digits) space.

Problem: Design a cache with capacity that evicts the least frequently used key (ties: least recently used). get and put in O(1).

Solve it on LeetCode ↗

Constraints: 1 ≤ capacity ≤ 10⁴ · 0 ≤ key ≤ 10⁵ · 0 ≤ value ≤ 10⁹ · At most 2 * 10⁵ calls will be made to get and put.

From brute force to the pattern: Scanning for the least frequent key is O(n) per eviction; frequency buckets make it O(1).

Spot it: Two levels of hash maps: each frequency has its own LRU list (an OrderedDict is a hash map + linked list). Using a key moves it from list f to list f + 1. Eviction pops the oldest key from the list of min_freq.

Why not another pattern? A heap keyed by (freq, time) gives O(log n), not O(1); scanning for the LFU key is O(n).

Approach:

1. touch(key): remove from buckets[freq]; if that was min_freq and it's now empty, min_freq += 1; add to buckets[freq + 1].
2. get: missing → −1; else touch and return.
3. put: existing → update value and touch. New: if full, evict the first key of buckets[min_freq]; insert with freq 1, min_freq = 1.

from collections import OrderedDict, defaultdict

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.entry = {}  # key -> [value, freq]
        self.buckets = defaultdict(OrderedDict)  # freq -> keys, least recent first
        self.min_freq = 0

    def _touch(self, key):
        value, freq = self.entry[key]
        del self.buckets[freq][key]
        if not self.buckets[freq] and freq == self.min_freq:
            self.min_freq += 1  # that frequency level is now empty
        self.buckets[freq + 1][key] = None  # most recent in the next level
        self.entry[key][1] = freq + 1

    def get(self, key: int) -> int:
        if key not in self.entry:
            return -1
        self._touch(key)
        return self.entry[key][0]

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        if key in self.entry:
            self.entry[key][0] = value
            self._touch(key)
            return
        if len(self.entry) == self.capacity:
            old, _ = self.buckets[self.min_freq].popitem(last=False)  # least frequent, then least recent
            del self.entry[old]
        self.entry[key] = [value, 1]
        self.buckets[1][key] = None
        self.min_freq = 1  # a brand-new key has the lowest frequency

What the code is doing, line by line:

1. Each frequency bucket keeps insertion order, so its first key is the least recently used at that frequency.
2. min_freq only grows by one when its bucket empties during a touch, and resets to 1 on every insert.
3. All operations are dictionary operations: O(1).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Capacity 0.
• Updating an existing key also counts as a use.
• Ties in frequency (evict the least recent).

Complexity: O(1) per operation, O(capacity) space.

Problem: Implement ls, mkdir, addContentToFile and readContentFromFile for an in-memory file system.

Solve it on LeetCode ↗ (Premium)

Constraints: 1 ≤ path.length, filePath.length ≤ 100 · path and filePath are absolute paths which begin with '/' and do not end with '/' except that the path is just "/" · You can assume that all directory names and file names only contain lowercase letters, and the same names will not exist in the same directory · You can assume that all operations will be passed valid parameters, and users will not attempt to retrieve file content or list a directory or file that does not exist · 1 ≤ content.length ≤ 50 · At most 300 calls will be made to ls, mkdir, addContentToFile, and readContentFromFile

From brute force to the pattern: A flat map of full paths needs a scan for ls; the trie lists children directly.

Spot it: Paths are sequences of names sharing prefixes → a trie whose children are a hash map by name. A node with content is a file.

Why not another pattern? Storing full path strings in one dict makes ls a scan over every path.

Approach:

1. walk(path): split by /, follow (creating) children.
2. ls: a file lists its own name; a directory lists its children sorted.
3. mkdir: walk with creation. addContentToFile: walk and append. readContentFromFile: walk and return.

class FileSystem:
    def __init__(self):
        self.root = {"children": {}, "content": None}  # content is None for directories

    def _walk(self, path):
        node = self.root
        for name in path.split("/"):
            if name:
                node = node["children"].setdefault(name, {"children": {}, "content": None})  # create on the way
        return node

    def ls(self, path: str) -> List[str]:
        node = self._walk(path)
        if node["content"] is not None:
            return [path.split("/")[-1]]  # a file lists itself
        return sorted(node["children"])

    def mkdir(self, path: str) -> None:
        self._walk(path)

    def addContentToFile(self, filePath: str, content: str) -> None:
        node = self._walk(filePath)
        node["content"] = (node["content"] or "") + content  # create or append

    def readContentFromFile(self, filePath: str) -> str:
        return self._walk(filePath)["content"]

What the code is doing, line by line:

1. Each /-separated name is one trie level.
2. Directories and files share the node shape; content tells them apart.
3. ls sorts names lexicographically as required.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• ls on a file.
• ls("/") on an empty system.
• Appending to an existing file.

Complexity: O(path length) per operation, plus O(k log k) for sorting k names in ls.

Problem: Typing characters one at a time, return the top 3 historical sentences with the typed prefix (by count, then ASCII). # ends the sentence, records it, and returns [].

Solve it on LeetCode ↗ (Premium)

Constraints: n == sentences.length · n == times.length · 1 ≤ n ≤ 100 · 1 ≤ sentences[i].length ≤ 100 · 1 ≤ times[i] ≤ 50 · c is a lowercase English letter, a hash '#', or space ' ' · Each tested sentence will be a sequence of characters c that end with the character '#' · Each tested sentence will have a length in the range [1, 200] · At most 5000 calls will be made to input

From brute force to the pattern: Filtering all sentences by prefix on each keystroke is slow; the trie jumps straight to the candidates.

Spot it: Prefix lookups → a trie. Each node stores the sentences passing through it with their counts (a hash map); the top 3 come from a small sort or heap.

Why not another pattern? Scanning every sentence on each keystroke is O(total sentences · length) per call.

Approach:

1. Insert each sentence: every node on its path records counts[sentence].
2. input(c): on #, add the typed sentence with +1 and reset. Otherwise extend the prefix and move down the trie (or fall off).
3. Return the 3 smallest by (−count, sentence) among the node's sentences.

import heapq

class AutocompleteSystem:
    def __init__(self, sentences: List[str], times: List[int]):
        self.root = {"next": {}, "hot": {}}  # hot: sentence -> count, for sentences under this node
        for s, t in zip(sentences, times):
            self._add(s, t)
        self.typed = ""
        self.node = self.root

    def _add(self, sentence, count):
        node = self.root
        for ch in sentence:
            node = node["next"].setdefault(ch, {"next": {}, "hot": {}})
            node["hot"][sentence] = node["hot"].get(sentence, 0) + count  # every prefix node knows it

    def input(self, c: str) -> List[str]:
        if c == "#":
            self._add(self.typed, 1)  # record the finished sentence
            self.typed = ""
            self.node = self.root
            return []
        self.typed += c
        if self.node is not None:
            self.node = self.node["next"].get(c)  # None once no sentence has this prefix
        if self.node is None:
            return []
        return heapq.nsmallest(3, self.node["hot"], key=lambda s: (-self.node["hot"][s], s))  # hottest, then ASCII

What the code is doing, line by line:

1. Each trie node keeps the counts of all sentences with that prefix, so a lookup needs no subtree walk.
2. Once the prefix leaves the trie, node stays None until #.
3. nsmallest with key (−count, sentence) ranks by count descending, then lexicographically.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A prefix nobody has typed.
• Ties in count (ASCII order, space before letters).
• A new sentence becoming hot after #.

Complexity: input: O(k log 3) for k sentences under the node; inserting a sentence is O(length).

Problem: Design a multiset with insert, remove (one copy) and getRandom (probability proportional to copies), all average O(1).

Solve it on LeetCode ↗

Constraints: -2³¹ ≤ val ≤ 2³¹ - 1 · At most 2 * 10⁵ calls in total will be made to insert, remove, and getRandom. · There will be at least one element in the data structure when getRandom is called.

From brute force to the pattern: A plain list makes remove O(n); swap-with-last plus index sets keeps it O(1).

Spot it: Random access needs an array; O(1) removal from an array means swap with the last and pop. With duplicates, the hash map stores a set of positions per value so any copy can be found.

Why not another pattern? A map of counts can't pick a random element in O(1); a list alone can't find a value in O(1).

Approach:

1. insert: append; add the index to pos[val]; return whether it was absent.
2. remove: take any index i of val; move the last value into i (update its index set); pop.
3. getRandom: random.choice(values).

import random
from collections import defaultdict

class RandomizedCollection:
    def __init__(self):
        self.values = []
        self.pos = defaultdict(set)  # value -> indices where it sits in values

    def insert(self, val: int) -> bool:
        self.pos[val].add(len(self.values))
        self.values.append(val)
        return len(self.pos[val]) == 1  # True if it wasn't present before

    def remove(self, val: int) -> bool:
        if not self.pos[val]:
            return False
        i = self.pos[val].pop()  # any copy of val
        last = self.values[-1]
        self.values[i] = last  # move the last element into the hole
        self.pos[last].add(i)
        self.pos[last].discard(len(self.values) - 1)
        self.values.pop()
        return True

    def getRandom(self) -> int:
        return random.choice(self.values)  # each copy equally likely

What the code is doing, line by line:

1. Adding i to last's set before discarding its old index handles the case where val == last (or i is the last index).
2. getRandom picks uniformly among copies, so a value with more copies is proportionally more likely.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Removing the last element itself.
• Removing a value that isn't present.
• Many duplicates.

Complexity: O(1) average per operation, O(n) space.

Problem: Support inc(key), dec(key), getMaxKey(), getMinKey(), all in O(1).

Solve it on LeetCode ↗

Constraints: 1 ≤ key.length ≤ 10 · key consists of lowercase English letters. · It is guaranteed that for each call to dec, key is existing in the data structure. · At most 5 * 10⁴ calls will be made to inc, dec, getMaxKey, and getMinKey.

From brute force to the pattern: Scanning all keys for max/min is O(n) per query; the bucket list is O(1).

Spot it: Counts change by ±1, so a key only moves to the adjacent count. Keep buckets of keys sorted by count in a doubly linked list (head = min, tail = max) and a hash map from key to its bucket — the same design idea as an LFU cache.

Why not another pattern? A heap gives O(log n) and can't update counts in place; scanning a map for max/min is O(n).

Approach:

1. inc: the key's bucket has count c (or the head sentinel for a new key). Use the next bucket if its count is c + 1, else insert one. Move the key; delete the old bucket if empty.
2. dec: symmetric toward c − 1; a count of 0 removes the key.
3. getMaxKey / getMinKey: any key of the last / first real bucket.

class Bucket:
    def __init__(self, count):
        self.count = count
        self.keys = set()
        self.prev = self.next = None


class AllOne:
    def __init__(self):
        self.head = Bucket(0)  # sentinel before the smallest count
        self.tail = Bucket(0)  # sentinel after the largest count
        self.head.next, self.tail.prev = self.tail, self.head
        self.where = {}  # key -> its bucket

    def _insert_after(self, node, count):
        b = Bucket(count)
        b.prev, b.next = node, node.next
        node.next.prev = b
        node.next = b
        return b

    def _drop_if_empty(self, b):
        if not b.keys and b is not self.head:
            b.prev.next, b.next.prev = b.next, b.prev  # unlink the empty bucket

    def inc(self, key: str) -> None:
        cur = self.where.get(key, self.head)
        nxt = cur.next
        if nxt is self.tail or nxt.count != cur.count + 1:
            nxt = self._insert_after(cur, cur.count + 1)  # the bucket for count + 1
        nxt.keys.add(key)
        self.where[key] = nxt
        if cur is not self.head:
            cur.keys.discard(key)
            self._drop_if_empty(cur)

    def dec(self, key: str) -> None:
        cur = self.where[key]
        cur.keys.discard(key)
        if cur.count == 1:
            del self.where[key]  # count reaches 0: forget the key
        else:
            prv = cur.prev
            if prv is self.head or prv.count != cur.count - 1:
                prv = self._insert_after(cur.prev, cur.count - 1)  # the bucket for count - 1
            prv.keys.add(key)
            self.where[key] = prv
        self._drop_if_empty(cur)

    def getMaxKey(self) -> str:
        return next(iter(self.tail.prev.keys)) if self.tail.prev is not self.head else ""

    def getMinKey(self) -> str:
        return next(iter(self.head.next.keys)) if self.head.next is not self.tail else ""

What the code is doing, line by line:

1. Buckets stay sorted by count because new buckets are only ever created right next to the current one.
2. Empty buckets are unlinked immediately, so the first and last real buckets hold the min and max keys.
3. Every operation touches a constant number of buckets and map entries.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Decrementing to zero.
• Ties for max or min (any key).
• Empty structure → "".

Complexity: O(1) per operation, O(n) space.

Problem: Design an iterator over a nested list of integers: next() and hasNext().

Solve it on LeetCode ↗

Constraints: 1 ≤ nestedList.length ≤ 500 · The values of the integers in the nested list is in the range [-10⁶, 10⁶].

From brute force to the pattern: Pre-flattening is fine but eager; the stack is lazy.

Spot it: The nesting is a tree; iterate it lazily with a stack: push items in reverse so the next one is on top. hasNext() expands lists at the top until it finds an integer (or the stack empties).

Why not another pattern? Flattening everything up front uses O(total) memory immediately; lazy expansion only does work as needed.

Approach:

1. Stack = the top-level list reversed.
2. hasNext: while the top is a list, pop it and push its items reversed.
3. next: pop the integer on top.

class NestedIterator:
    def __init__(self, nestedList: List["NestedInteger"]):
        self.stack = nestedList[::-1]  # next item on top

    def next(self) -> int:
        return self.stack.pop().getInteger()  # hasNext() guaranteed an integer on top

    def hasNext(self) -> bool:
        while self.stack and not self.stack[-1].isInteger():
            items = self.stack.pop().getList()
            self.stack.extend(reversed(items))  # unpack the list in order
        return bool(self.stack)

What the code is doing, line by line:

1. Reversing keeps the original left-to-right order when popping.
2. Empty inner lists are unpacked into nothing and skipped.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Empty inner lists.
• Deep nesting.
• No integers at all.

Complexity: Amortised O(1) per call, O(depth + width) space.

Problem: Design an n × n Tic-Tac-Toe where move(row, col, player) returns the winner (0 if none) in better than O(n²).

Solve it on LeetCode ↗ (Premium)

Constraints: 2 ≤ n ≤ 100 · player is 1 or 2 · 0 ≤ row, col < n · (row, col) are unique for each different call to move · At most n² calls will be made to move

From brute force to the pattern: Board scans are O(n²) per move; line counters are O(1).

Spot it: A player wins when a whole line is theirs. Instead of scanning the board, keep a running sum per line: player 1 adds 1, player 2 subtracts 1. A line is won when its sum reaches ±n.

Why not another pattern? Checking the row, column and diagonals after each move is O(n); scanning the board is O(n²).

Approach:

1. rows[r], cols[c], diag, anti sums.
2. Add +1 or −1 for the move's lines.
3. If any becomes ±n, return the player.

class TicTacToe:
    def __init__(self, n: int):
        self.n = n
        self.rows = [0] * n
        self.cols = [0] * n
        self.diag = 0
        self.anti = 0

    def move(self, row: int, col: int, player: int) -> int:
        v = 1 if player == 1 else -1  # player 2 counts negatively
        self.rows[row] += v
        self.cols[col] += v
        if row == col:
            self.diag += v
        if row + col == self.n - 1:
            self.anti += v
        n = self.n
        if n in (abs(self.rows[row]), abs(self.cols[col]), abs(self.diag), abs(self.anti)):
            return player  # a full line of one player
        return 0

What the code is doing, line by line:

1. A mixed line can never reach ±n, because the signs cancel.
2. Moves are guaranteed valid, so each cell is counted once.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Win on a diagonal.
• Win on the last possible move.
• n = 1.

Complexity: O(1) per move, O(n) space.

Problem: Seats 0..n−1: seat() takes the seat maximising the distance to the closest person (lowest index on ties); leave(p) frees seat p.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 10⁹ · It is guaranteed that there is a student sitting at seat p. · At most 10⁴ calls will be made to seat and leave.

From brute force to the pattern: Scanning all n seats is infeasible for n = 10⁹; scanning occupied seats is O(k).

Spot it: Keep the occupied seats sorted. The best seat is the left end, the middle of the widest gap, or the right end; scanning the sorted list finds it. Insertions use binary search.

Why not another pattern? Scanning all n seats is O(n) per call with n up to 10⁹.

Approach:

1. If empty, take 0.
2. Candidates: seat 0 (distance first), the middle of each gap (a, b) (distance (b − a) // 2), and n − 1 (distance n − 1 − last).
3. Take the best (first wins ties); insort it.

from bisect import bisect_left, insort

class ExamRoom:
    def __init__(self, n: int):
        self.n = n
        self.seats = []  # occupied seats, sorted

    def seat(self) -> int:
        if not self.seats:
            choice = 0
        else:
            choice, best = 0, self.seats[0]  # sit at seat 0
            for a, b in zip(self.seats, self.seats[1:]):
                if (b - a) // 2 > best:
                    choice, best = a + (b - a) // 2, (b - a) // 2  # middle of this gap
            if self.n - 1 - self.seats[-1] > best:
                choice = self.n - 1  # the right end
        insort(self.seats, choice)
        return choice

    def leave(self, p: int) -> None:
        self.seats.pop(bisect_left(self.seats, p))

What the code is doing, line by line:

1. Within a gap the farthest seat from both neighbours is the middle (lower one on ties).
2. Strict > keeps the lowest index on ties because candidates are checked left to right.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Empty room → 0.
• Ends vs middle ties.
• Leaving and re-seating.

Complexity: O(k) per seat and leave for k occupied seats (a heap of gaps gives O(log k)).

Problem: Remove every folder that is inside another folder in the list; return the rest (any order).

Solve it on LeetCode ↗

Constraints: 1 ≤ folder.length ≤ 4 * 10⁴ · 2 ≤ folder[i].length ≤ 100 · folder[i] contains only lowercase letters and '/'. · folder[i] always starts with the character '/'. · Each folder name is unique.

From brute force to the pattern: All pairs: O(n² L); sort + one comparison per path: O(n log n · L).

Spot it: Paths form a trie of components. Sorting gives the same effect simply: a parent sorts right before its children, so compare each path with the last kept folder plus /.

Why not another pattern? Checking every pair of folders is O(n² · L).

Approach:

1. Sort.
2. Keep a path unless it starts with kept[-1] + '/'.

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        kept = []
        for path in sorted(folder):
            if not kept or not path.startswith(kept[-1] + "/"):
                kept.append(path)  # not inside the last kept folder
        return kept

What the code is doing, line by line:

1. The trailing / prevents /a/bc from looking like a child of /a/b.
2. In sorted order, every sub-folder comes after its parent and before unrelated folders.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Similar names (/a/b, /a/bc).
• Deep nesting.
• No sub-folders.

Complexity: O(n log n · L) time, O(n) space.

Problem: After each typed character of searchWord, suggest up to 3 lexicographically smallest products with that prefix.

Solve it on LeetCode ↗

Constraints: 1 ≤ products.length ≤ 1000 · 1 ≤ products[i].length ≤ 3000 · 1 ≤ sum(products[i].length) ≤ 2 * 10⁴ · All the strings of products are unique. · products[i] consists of lowercase English letters. · 1 ≤ searchWord.length ≤ 1000 · searchWord consists of lowercase English letters.

From brute force to the pattern: Filtering per prefix is O(nm); sorted + binary search is O(m log n) after sorting.

Spot it: Prefix lookups are a trie problem; with sorted products, words sharing a prefix are contiguous, so a binary search for the prefix gives the start of the block directly.

Why not another pattern? Filtering all products for every prefix is O(n · m) per character.

Approach:

1. Sort products.
2. For each prefix: i = bisect_left(products, prefix); take products[i:i + 3] that start with the prefix.

from bisect import bisect_left

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        products = sorted(products)
        result = []
        prefix = ""
        start = 0
        for ch in searchWord:
            prefix += ch
            start = bisect_left(products, prefix, start)  # first word >= prefix (never moves back)
            result.append([w for w in products[start:start + 3] if w.startswith(prefix)])
        return result

What the code is doing, line by line:

1. In sorted order, all words with a given prefix form one block starting at bisect_left(prefix).
2. Longer prefixes start at or after shorter ones, so the search can resume from start.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No matches for a prefix → [].
• Fewer than 3 matches.
• Duplicate products.

Complexity: O(n log n · L) to sort, O(m log n) for the searches.

Problem: Design FirstUnique(nums) with showFirstUnique() (first value seen exactly once, or −1) and add(value).

Solve it on LeetCode ↗ (Premium)

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁸ · 1 ≤ value ≤ 10⁸ · At most 50000 calls will be made to showFirstUnique and add

From brute force to the pattern: Scanning per query is O(n); lazy queue cleanup is amortised O(1).

Spot it: Values arrive in order; the answer is the earliest one with count 1. Keep counts in a hash map and arrival order in a queue; when asked, pop values from the front whose count is no longer 1 (lazy cleanup, each popped once).

Why not another pattern? Scanning all values for each query is O(n) per call.

Approach:

1. add: increment its count; append it to the queue if this is its first occurrence.
2. showFirstUnique: pop from the front while count > 1; return the front or −1.

from collections import Counter, deque

class FirstUnique:
    def __init__(self, nums: List[int]):
        self.count = Counter()
        self.queue = deque()  # values in arrival order (each once)
        for x in nums:
            self.add(x)

    def showFirstUnique(self) -> int:
        while self.queue and self.count[self.queue[0]] > 1:
            self.queue.popleft()  # no longer unique: drop it for good
        return self.queue[0] if self.queue else -1

    def add(self, value: int) -> None:
        self.count[value] += 1
        if self.count[value] == 1:
            self.queue.append(value)  # a new candidate

What the code is doing, line by line:

1. Once a value appears twice it can never be unique again, so dropping it from the queue is permanent.
2. Each value enters and leaves the queue at most once: amortised O(1).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All duplicates → −1.
• A duplicate arrives after the value was the answer.
• Empty start.

Complexity: Amortised O(1) per operation, O(n) space.

Problem: Design visit(url), back(steps) and forward(steps) for a browser tab.

Solve it on LeetCode ↗

Constraints: 1 ≤ homepage.length ≤ 20 · 1 ≤ url.length ≤ 20 · 1 ≤ steps ≤ 100 · homepage and url consist of '.' or lower case English letters. · At most 5000 calls will be made to visit, back, and forward.

From brute force to the pattern: A linked list walks steps nodes; the array jumps directly.

Spot it: History is a stack-like array with a cursor. Visiting a page cuts off the forward pages, so track a logical end instead of deleting.

Why not another pattern? Two stacks also work; a doubly linked list needs O(steps) moves.

Approach:

1. pages, cur, end.
2. visit: write at cur + 1 (append or overwrite), end = cur.
3. back/forward: move cur within [0, end].

class BrowserHistory:
    def __init__(self, homepage: str):
        self.pages = [homepage]
        self.cur = 0  # index of the current page
        self.end = 0  # last valid index (forward history ends here)

    def visit(self, url: str) -> None:
        self.cur += 1
        if self.cur == len(self.pages):
            self.pages.append(url)
        else:
            self.pages[self.cur] = url  # overwrite old forward history
        self.end = self.cur  # forward history is gone

    def back(self, steps: int) -> str:
        self.cur = max(0, self.cur - steps)
        return self.pages[self.cur]

    def forward(self, steps: int) -> str:
        self.cur = min(self.end, self.cur + steps)
        return self.pages[self.cur]

What the code is doing, line by line:

1. Old entries beyond end are ignored rather than deleted.
2. All operations are O(1).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Back past the homepage.
• Forward past the end.
• Visit after going back.

Complexity: O(1) per operation, O(n) space.

Problem: Design generate, renew and countUnexpiredTokens for tokens that live timeToLive seconds.

Solve it on LeetCode ↗

Constraints: 1 ≤ timeToLive ≤ 10⁸ · 1 ≤ currentTime ≤ 10⁸ · 1 ≤ tokenId.length ≤ 5 · tokenId consists only of lowercase letters. · All calls to generate will contain unique values of tokenId. · The values of currentTime across all the function calls will be strictly increasing. · At most 2000 calls will be made to all functions combined.

From brute force to the pattern: Event replay is unnecessary; expiry times answer everything.

Spot it: A hash map from token to its expiry time. A token is alive at time t if expiry > t (expiring exactly at t counts as expired).

Why not another pattern? Storing creation events and recomputing is more complicated than storing expiry times.

Approach:

1. generate: expiry[id] = t + ttl.
2. renew: only if expiry[id] > t.
3. count: number of expiries > t.

class AuthenticationManager:
    def __init__(self, timeToLive: int):
        self.ttl = timeToLive
        self.expiry = {}  # tokenId -> time it expires

    def generate(self, tokenId: str, currentTime: int) -> None:
        self.expiry[tokenId] = currentTime + self.ttl

    def renew(self, tokenId: str, currentTime: int) -> None:
        if self.expiry.get(tokenId, 0) > currentTime:  # still alive
            self.expiry[tokenId] = currentTime + self.ttl

    def countUnexpiredTokens(self, currentTime: int) -> int:
        return sum(1 for t in self.expiry.values() if t > currentTime)

What the code is doing, line by line:

1. Expiry happens before other actions at the same time, hence the strict >.
2. Counting scans the map; an ordered structure would make it O(log n).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Renewing an expired token (ignored).
• Expiry exactly at currentTime.
• Unknown token.

Complexity: O(1) for generate/renew, O(n) for count, O(n) space.

Problem: Design add(point) (duplicates allowed) and count(point): how many axis-aligned squares with positive area have the query as a corner.

Solve it on LeetCode ↗

Constraints: point.length == 2 · 0 ≤ x, y ≤ 1000 · At most 3000 calls in total will be made to add and count.

From brute force to the pattern: Checking all triples is cubic; fixing one side is O(k).

Spot it: Store point counts in a hash map (and points by x). For a query (x, y), every stored (x, y2) with y2 ≠ y fixes the side d; the other corners are (x ± d, y) and (x ± d, y2), found by lookups.

Why not another pattern? Trying all triples of stored points is cubic.

Approach:

1. count[(x, y)] += 1; by_x[x][y] += 1.
2. Query: for each y2 in by_x[x] (≠ y): d = y2 − y; for x2 = x + d and x − d: add by_x[x][y2] · count[(x2, y)] · count[(x2, y2)].

from collections import Counter, defaultdict

class DetectSquares:
    def __init__(self):
        self.points = Counter()  # (x, y) -> how many times added
        self.by_x = defaultdict(Counter)  # x -> Counter of y

    def add(self, point: List[int]) -> None:
        x, y = point
        self.points[(x, y)] += 1
        self.by_x[x][y] += 1

    def count(self, point: List[int]) -> int:
        x, y = point
        total = 0
        for y2, c in self.by_x[x].items():
            if y2 == y:
                continue  # zero-area square
            d = y2 - y  # side length (with sign)
            for x2 in (x + d, x - d):  # square to the right or to the left
                total += c * self.points[(x2, y)] * self.points[(x2, y2)]
        return total

What the code is doing, line by line:

1. Fixing the vertical side determines the square up to its direction (left or right).
2. Duplicates multiply the number of squares.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Duplicate points.
• The query point itself not stored.
• Squares on both sides.

Complexity: O(1) add, O(k) count where k is the number of distinct y values on that x.

Problem: Design add, edit, rmv and execTop (run the highest-priority task, ties by larger taskId, return its user).

Solve it on LeetCode ↗

Constraints: 1 ≤ tasks.length ≤ 10⁵ · 0 ≤ userId ≤ 10⁵ · 0 ≤ taskId ≤ 10⁵ · 0 ≤ priority ≤ 10⁹ · 0 ≤ newPriority ≤ 10⁹ · At most 2 * 10⁵ calls will be made in total to add, edit, rmv, and execTop methods. · The input is generated such that taskId will be valid.

From brute force to the pattern: Scanning for the top task is O(n); a lazy heap is O(log n).

Spot it: "Highest priority with updates" → a heap with lazy deletion: edits push a new entry, and stale entries (removed or outdated) are skipped when they reach the top. A hash map gives the current state of each task.

Why not another pattern? Scanning all tasks for execTop is O(n).

Approach:

1. info[taskId] = (userId, priority); push (−priority, −taskId).
2. edit: update the map, push a new entry. rmv: delete from the map.
3. execTop: pop until the top matches the map; remove it and return its user.

import heapq

class TaskManager:
    def __init__(self, tasks: List[List[int]]):
        self.info = {}  # taskId -> (userId, priority)
        self.heap = []  # (-priority, -taskId): highest priority, then highest id
        for user, task, prio in tasks:
            self.add(user, task, prio)

    def add(self, userId: int, taskId: int, priority: int) -> None:
        self.info[taskId] = (userId, priority)
        heapq.heappush(self.heap, (-priority, -taskId))

    def edit(self, taskId: int, newPriority: int) -> None:
        user, _ = self.info[taskId]
        self.add(user, taskId, newPriority)  # the old heap entry becomes stale

    def rmv(self, taskId: int) -> None:
        del self.info[taskId]

    def execTop(self) -> int:
        while self.heap:
            neg_p, neg_t = heapq.heappop(self.heap)
            task = -neg_t
            if task in self.info and self.info[task][1] == -neg_p:  # entry is current
                user, _ = self.info.pop(task)
                return user
        return -1

What the code is doing, line by line:

1. An entry is valid only if the task still exists with that exact priority.
2. Every pushed entry is popped at most once, so the extra work is amortised.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Editing to the same priority.
• Ties broken by larger taskId.
• Empty manager → −1.

Complexity: O(log N) amortised per operation, O(N) space for N heap entries.

Problem: Design push(x) and pop() that removes the most frequent element (most recent among ties).

Solve it on LeetCode ↗

Constraints: 0 ≤ val ≤ 10⁹ · At most 2 * 10⁴ calls will be made to push and pop. · It is guaranteed that there will be at least one element in the stack before calling pop.

From brute force to the pattern: A heap with timestamps is O(log n); level stacks are O(1).

Spot it: Each copy of x is pushed onto the stack for its frequency level (1st copy → level 1, 2nd → level 2, …). The answer is always the top of the highest non-empty level, which also breaks ties by recency.

Why not another pattern? A heap keyed by (frequency, time) works in O(log n); the level stacks are O(1).

Approach:

1. push: freq[x] += 1; push x onto levels[freq[x]]; update max_freq.
2. pop: pop from levels[max_freq]; decrement its frequency; lower max_freq if that level emptied.

from collections import Counter, defaultdict

class FreqStack:
    def __init__(self):
        self.freq = Counter()
        self.levels = defaultdict(list)  # frequency -> stack of values that reached it
        self.max_freq = 0

    def push(self, val: int) -> None:
        self.freq[val] += 1
        f = self.freq[val]
        self.levels[f].append(val)
        self.max_freq = max(self.max_freq, f)

    def pop(self) -> int:
        val = self.levels[self.max_freq].pop()  # most frequent, most recent
        self.freq[val] -= 1
        if not self.levels[self.max_freq]:
            self.max_freq -= 1  # that level is empty now
        return val

What the code is doing, line by line:

1. A value with frequency f appears on every level 1..f, so lower levels stay correct after a pop.
2. Within a level, the stack order is recency, which breaks ties.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Ties broken by recency.
• Popping until frequencies drop.
• One value repeated.

Complexity: O(1) per operation, O(n) space.

Problem: Design append, addAll(inc), multAll(m) and getIndex(i) (mod 10⁹ + 7), all fast.

Solve it on LeetCode ↗

Constraints: 1 ≤ val, inc, m ≤ 100 · 0 ≤ idx ≤ 10⁵ · At most 10⁵ calls total will be made to append, addAll, multAll, and getIndex.

From brute force to the pattern: Updating every element per operation is O(n); a global affine map is O(1).

Spot it: Every operation applies the same affine map x → a·x + b to all values. Keep one global (a, b). When appending v, store the value that the current map would turn into v: (v − b) · a⁻¹ (modular inverse, since the modulus is prime).

Why not another pattern? Updating every element on addAll / multAll is O(n) per call.

Approach:

1. a = 1, b = 0.
2. addAll(inc): b += inc. multAll(m): a *= m, b *= m.
3. append(v): store (v − b) · inverse(a).
4. getIndex(i): a · stored[i] + b.

class Fancy:
    MOD = 10**9 + 7

    def __init__(self):
        self.vals = []  # values "before" the global map
        self.a, self.b = 1, 0  # every real value = a * stored + b

    def append(self, val: int) -> None:
        inv = pow(self.a, self.MOD - 2, self.MOD)  # a is never 0 mod p (multipliers are 1..100)
        self.vals.append((val - self.b) * inv % self.MOD)

    def addAll(self, inc: int) -> None:
        self.b = (self.b + inc) % self.MOD

    def multAll(self, m: int) -> None:
        self.a = self.a * m % self.MOD
        self.b = self.b * m % self.MOD

    def getIndex(self, idx: int) -> int:
        if idx >= len(self.vals):
            return -1
        return (self.a * self.vals[idx] + self.b) % self.MOD

What the code is doing, line by line:

1. Composing affine maps keeps the form a·x + b, so one pair describes all operations so far.
2. A value appended later must not be affected by earlier operations, so it's stored pre-inverted under the current map.
3. Fermat's little theorem gives a⁻¹ = a^(p − 2) mod p.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• getIndex out of range → −1.
• Many multiplications.
• append right after multAll.

Complexity: O(1) per operation except append's O(log p) inverse, O(n) space.

Problem: For each query, return the index of the container word with the longest common suffix (ties: shortest, then earliest).

Solve it on LeetCode ↗

Constraints: 1 ≤ wordsContainer.length, wordsQuery.length ≤ 10⁴ · 1 ≤ wordsContainer[i].length ≤ 5 * 10³ · 1 ≤ wordsQuery[i].length ≤ 5 * 10³ · wordsContainer[i] consists only of lowercase English letters. · wordsQuery[i] consists only of lowercase English letters. · Sum of wordsContainer[i].length is at most 5 * 10⁵. · Sum of wordsQuery[i].length is at most 5 * 10⁵.

From brute force to the pattern: Pairwise comparison is O(q · n · L); the reversed trie is linear in the input size.

Spot it: Common suffixes are common prefixes of the reversed words → a trie. Store at every node the best container index passing through it; a query walks as deep as it can and reads the best index there.

Why not another pattern? Comparing each query with every container word is O(q · n · L).

Approach:

1. Insert each reversed word; at each node keep the index with the smallest (length, index).
2. The root also keeps the overall best (for an empty common suffix).
3. Query: walk the reversed query; return the last node's best.

class Solution:
    def stringIndices(self, wordsContainer: List[str], wordsQuery: List[str]) -> List[int]:
        def better(i, j):  # shorter word wins, then earlier index
            return i if (len(wordsContainer[i]), i) < (len(wordsContainer[j]), j) else j

        root = {"best": 0}
        for i, w in enumerate(wordsContainer):
            node = root
            node["best"] = better(i, node["best"])
            for ch in reversed(w):  # suffixes become prefixes
                node = node.setdefault(ch, {"best": i})
                node["best"] = better(i, node["best"])
        result = []
        for q in wordsQuery:
            node = root
            for ch in reversed(q):
                if ch not in node:
                    break  # the common suffix can't grow any further
                node = node[ch]
            result.append(node["best"])
        return result

What the code is doing, line by line:

1. Every node represents a suffix; the words passing through it all end with that suffix.
2. Walking as far as possible gives the longest common suffix, and the stored best handles the tie-breaks.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No common suffix (root's best).
• Ties on length (earliest).
• A query longer than every word.

Complexity: O(Σ container lengths + Σ query lengths) time and space.

Problem: Design a router with limited memory: add packets (no duplicates, evict the oldest when full), forward in FIFO order, and count stored packets for a destination in a time range.

Solve it on LeetCode ↗

Constraints: 2 ≤ memoryLimit ≤ 10⁵ · 1 ≤ source, destination ≤ 2 * 10⁵ · 1 ≤ timestamp ≤ 10⁹ · 1 ≤ startTime ≤ endTime ≤ 10⁹ · At most 10⁵ calls will be made to addPacket, forwardPacket, and getCount methods altogether. · queries for addPacket will be made in non-decreasing order of timestamp.

From brute force to the pattern: Scanning stored packets per count is linear; sorted lists with a start pointer make it logarithmic.

Spot it: FIFO storage → a queue; duplicate detection → a hash set. Timestamps arrive in order, so each destination's timestamps form a sorted list; removed packets are always the oldest, so a start pointer per destination plus binary search answers getCount.

Why not another pattern? Scanning all stored packets for each getCount is O(memory) per query.

Approach:

1. addPacket: reject duplicates; if full, forward (drop) the oldest; append to the queue, the set and times[dest].
2. forwardPacket: pop the oldest, remove from the set, advance start[dest].
3. getCount: bisect_right(end) − max(start, bisect_left(startTime)) on times[dest].

from bisect import bisect_left, bisect_right
from collections import defaultdict, deque

class Router:
    def __init__(self, memoryLimit: int):
        self.limit = memoryLimit
        self.queue = deque()  # packets in arrival order
        self.seen = set()  # packets currently stored
        self.times = defaultdict(list)  # destination -> timestamps (non-decreasing)
        self.start = defaultdict(int)  # destination -> index of its oldest stored timestamp

    def addPacket(self, source: int, destination: int, timestamp: int) -> bool:
        packet = (source, destination, timestamp)
        if packet in self.seen:
            return False  # duplicate
        if len(self.queue) == self.limit:
            self.forwardPacket()  # evict the oldest
        self.queue.append(packet)
        self.seen.add(packet)
        self.times[destination].append(timestamp)
        return True

    def forwardPacket(self) -> List[int]:
        if not self.queue:
            return []
        packet = self.queue.popleft()
        self.seen.discard(packet)
        self.start[packet[1]] += 1  # that destination's oldest packet is gone
        return list(packet)

    def getCount(self, destination: int, startTime: int, endTime: int) -> int:
        ts = self.times[destination]
        lo = max(self.start[destination], bisect_left(ts, startTime))
        hi = bisect_right(ts, endTime)
        return max(0, hi - lo)

What the code is doing, line by line:

1. The globally oldest packet is also the oldest for its destination, so removals always happen at the front of that destination's list.
2. Lists are never shrunk; the start pointer marks which entries are gone.
3. Two binary searches count the timestamps in [startTime, endTime] among the stored ones.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Duplicate packet → false.
• Eviction when full.
• Counting after forwards.

Complexity: O(1) amortised for add/forward, O(log n) for getCount, O(total packets) space.

Problem: Store logs with timestamps Year:Month:Day:Hour:Minute:Second; retrieve(start, end, granularity) returns ids within the range at that precision.

Solve it on LeetCode ↗ (Premium)

Constraints: 1 ≤ id ≤ 500 · 2000 ≤ Year ≤ 2017 · 1 ≤ Month ≤ 12 · 1 ≤ Day ≤ 31 · 0 ≤ Hour ≤ 23 · 0 ≤ Minute, Second ≤ 59 · granularity is one of the values ["Year", "Month", "Day", "Hour", "Minute", "Second"] · At most 500 calls will be made to put and retrieve

From brute force to the pattern: Parsing into datetimes works but is longer; prefix comparison is direct.

Spot it: The format is fixed-width, so string comparison orders timestamps correctly. Granularity just means comparing prefixes of a known length (Year → 4 characters, Month → 7, …). A list (or hash map) of logs is then scanned.

Why not another pattern? Parsing every timestamp into numbers is unnecessary; the strings already compare correctly.

Approach:

1. put: store (id, timestamp).
2. retrieve: k = prefix length for the granularity; return ids with start[:k] ≤ ts[:k] ≤ end[:k].

class LogSystem:
    PREFIX = {"Year": 4, "Month": 7, "Day": 10, "Hour": 13, "Minute": 16, "Second": 19}

    def __init__(self):
        self.logs = []  # (id, timestamp)

    def put(self, id: int, timestamp: str) -> None:
        self.logs.append((id, timestamp))

    def retrieve(self, start: str, end: str, granularity: str) -> List[int]:
        k = self.PREFIX[granularity]  # how many characters matter
        lo, hi = start[:k], end[:k]
        return [i for i, ts in self.logs if lo <= ts[:k] <= hi]

What the code is doing, line by line:

1. Zero-padded fixed-width fields make lexicographic order equal to time order.
2. Cutting at the granularity ignores the finer fields of both bounds and the timestamp.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Boundaries equal at the granularity.
• Year granularity.
• No logs in range.

Complexity: O(1) put, O(n) retrieve.

Problem: Design allocate(size, mID) (leftmost block of free units, or −1) and freeMemory(mID) (free every unit of that id, return the count).

Solve it on LeetCode ↗

Constraints: 1 ≤ n, size, mID ≤ 1000 · At most 1000 calls will be made to allocate and freeMemory.

From brute force to the pattern: This is the direct simulation, fast enough for n, calls ≤ 1000.

Spot it: With n ≤ 1000 and 1000 calls, a direct simulation over an array of owners is fast enough: scan for a run of free cells. A hash map of id → cells would speed up freeMemory, but scanning is fine here.

Why not another pattern? Interval trees or ordered maps of free blocks are overkill for these limits.

Approach:

1. mem[i] = owner id or 0.
2. allocate: count consecutive zeros; when the run reaches size, fill it and return its start.
3. freeMemory: zero every cell with that id and count them.

class Allocator:
    def __init__(self, n: int):
        self.mem = [0] * n  # 0 = free, otherwise the owner id

    def allocate(self, size: int, mID: int) -> int:
        run = 0  # length of the current stretch of free units
        for i, owner in enumerate(self.mem):
            run = run + 1 if owner == 0 else 0
            if run == size:
                start = i - size + 1  # leftmost block that fits
                for j in range(start, i + 1):
                    self.mem[j] = mID
                return start
        return -1

    def freeMemory(self, mID: int) -> int:
        freed = 0
        for i, owner in enumerate(self.mem):
            if owner == mID:
                self.mem[i] = 0
                freed += 1
        return freed

What the code is doing, line by line:

1. The first time a free run reaches size is the leftmost fit.
2. Several blocks may share an id, so freeing scans the whole array.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No block big enough → −1.
• Freeing an unused id → 0.
• Several blocks with one id.

Complexity: O(n) per call, O(n) space.