AlgoH2

Cheatsheet Content

1. Word Ladder Problem Type: BFS, Graph Concept: Find the shortest transformation sequence from `beginWord` to `endWord` by changing one letter at a time, such that each transformed word exists in `wordList`. Notes: Build a graph where nodes are words and an edge exists if words differ by one character. BFS finds the shortest path. Pre-processing `wordList` into a dictionary of generic words (e.g., `h*t` for `hot`) can optimize neighbor lookup. Snippet (BFS): from collections import deque, defaultdict def ladderLength(beginWord, endWord, wordList): wordSet = set(wordList) if endWord not in wordSet: return 0 queue = deque([(beginWord, 1)]) visited = {beginWord} while queue: current_word, level = queue.popleft() if current_word == endWord: return level for i in range(len(current_word)): for char_code in range(ord('a'), ord('z') + 1): next_word = list(current_word) next_word[i] = chr(char_code) next_word = "".join(next_word) if next_word in wordSet and next_word not in visited: visited.add(next_word) queue.append((next_word, level + 1)) return 0 2. Sort Items by Groups Respecting Dependencies Problem Type: Topological Sort, Graph (Multi-level) Concept: Given items, their groups, and dependencies, sort them such that items in the same group are together, and dependencies are met. Notes: This requires two levels of topological sort: one for groups and one for items within groups. Create a "super-graph" for group dependencies and individual graphs for item dependencies. Handle items not assigned to any group by giving them unique "virtual" groups. Snippet (Conceptual): from collections import defaultdict, deque def sortItems(n, m, group, beforeItems): # Assign new group IDs for items without a group next_group_id = m for i in range(n): if group[i] == -1: group[i] = next_group_id next_group_id += 1 # Build group and item adjacency lists and in-degrees group_adj = defaultdict(list) group_in_degree = defaultdict(int) item_adj = defaultdict(list) item_in_degree = defaultdict(int) for i in range(n): for prev_item in beforeItems[i]: item_adj[prev_item].append(i) item_in_degree[i] += 1 if group[i] != group[prev_item]: group_adj[group[prev_item]].append(group[i]) group_in_degree[group[i]] += 1 # Topological sort helper function def topo_sort(nodes, adj, in_degree): queue = deque([node for node in nodes if in_degree[node] == 0]) result = [] while queue: node = queue.popleft() result.append(node) for neighbor in adj[node]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) return result if len(result) == len(nodes) else [] # Get all unique group IDs and item IDs all_groups = set(group) all_items = set(range(n)) # Perform topological sort on groups sorted_groups = topo_sort(all_groups, group_adj, group_in_degree) if not sorted_groups: return [] # Group items by their group ID items_in_group = defaultdict(list) for i in range(n): items_in_group[group[i]].append(i) final_order = [] for g_id in sorted_groups: # Perform topological sort on items within each group group_items = items_in_group[g_id] if not group_items: continue # Empty group # Filter item dependencies relevant to this group sub_item_adj = defaultdict(list) sub_item_in_degree = defaultdict(int) for item in group_items: for neighbor in item_adj[item]: if group[neighbor] == g_id: # Only consider intra-group dependencies sub_item_adj[item].append(neighbor) sub_item_in_degree[neighbor] += 1 # Need to ensure all items in the group are considered for topo sort input # Correctly initialize in_degrees for items within the current group current_group_item_in_degree = {item: 0 for item in group_items} for item in group_items: for prev_item in beforeItems[item]: if prev_item in current_group_item_in_degree: # Only count intra-group dependencies current_group_item_in_degree[item] += 1 sorted_group_items = topo_sort(group_items, item_adj, current_group_item_in_degree) # Use original item_adj/in_degree for calculation, but filter for current group if not sorted_group_items: return [] final_order.extend(sorted_group_items) return final_order 3. Minimize Malware Spread Problem Type: Union-Find, Graph (Connected Components) Concept: Given a graph and initial infected nodes, remove one initial infected node to minimize the total number of infected nodes. Notes: Use Union-Find to find connected components and their sizes. For each component, count how many initial infected nodes it contains. If a component has only one initial infected node, removing that node prevents the entire component from being infected. Prioritize removing the node that saves the largest such component. If multiple components have the same max size, remove the infected node with the smallest index. Snippet (Union-Find): class DSU: def __init__(self, n): self.parent = list(range(n)) self.size = [1] * n def find(self, i): if self.parent[i] == i: return i self.parent[i] = self.find(self.parent[i]) return self.parent[i] def union(self, i, j): root_i = self.find(i) root_j = self.find(j) if root_i != root_j: if self.size[root_i] max_saved: max_saved = current_saved node_to_remove = node elif current_saved == max_saved: # If tied in saved nodes, choose the one with smaller index if node_to_remove == -1 or node 4. Swim in Rising Water Problem Type: Dijkstra's Algorithm, BFS/DFS with Priority Queue, Minimum Spanning Tree (Prim's/Kruskal's adaptation) Concept: Find the minimum maximum depth encountered to reach the bottom-right cell from the top-left in a grid where each cell has an elevation. Notes: This is a variation of finding the path with the minimum "bottleneck" edge. Dijkstra's algorithm is suitable, where the "cost" of moving to a cell is the maximum of the current path's max elevation and the new cell's elevation. A min-priority queue stores `(max_elevation_so_far, r, c)`. Snippet (Dijkstra): import heapq def swimInRisingWater(grid): n = len(grid) # (max_elevation_so_far, r, c) pq = [(grid[0][0], 0, 0)] visited = set([(0, 0)]) # Directions: right, left, down, up directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] while pq: max_t, r, c = heapq.heappop(pq) if r == n - 1 and c == n - 1: return max_t for dr, dc in directions: nr, nc = r + dr, c + dc if 0 5. Reconstruct Itinerary Problem Type: Eulerian Path/Circuit, DFS Concept: Given a list of airline tickets, reconstruct the itinerary starting from "JFK" that visits all airports exactly once in lexicographical order. Notes: This is an Eulerian path problem. Sort destinations lexicographically for each departure airport. Use DFS to traverse, adding airports to the result in reverse order as the path is completed. A stack can be used to manage the path. Snippet (DFS/Hierholzer's Algorithm): from collections import defaultdict def findItinerary(tickets): # Build graph: departure -> list of destinations (sorted) graph = defaultdict(list) for origin, dest in sorted(tickets): # Sort tickets to ensure lexicographical order graph[origin].append(dest) # Sort destinations for each origin in reverse to make popping efficient for origin in graph: graph[origin].sort(reverse=True) # Sort lexicographically ascending # but process from end of list for stack-like behavior path = [] def dfs(airport): while graph[airport]: next_airport = graph[airport].pop() dfs(next_airport) path.append(airport) # Add airport to path after all its outgoing edges are visited dfs("JFK") return path[::-1] # Reverse the path as it's built in reverse order 6. Cracking the Safe Problem Type: Eulerian Path/Circuit, De Bruijn Sequence, DFS Concept: Find the shortest string that contains all possible $k^n$ combinations of $n$ digits from $0$ to $k-1$ as substrings. Notes: This is equivalent to finding a De Bruijn sequence. Construct a directed graph where nodes are all possible $(n-1)$-length prefixes/suffixes. An edge exists from node $u$ to node $v$ if $u$'s suffix matches $v$'s prefix, and the edge label is the last digit of $v$. An Eulerian path in this graph gives the De Bruijn sequence. Use DFS. Snippet (DFS): def crackingTheSafe(n, k): if n == 1: return "".join(str(i) for i in range(k)) visited = set() ans = [] def dfs(node): for i in range(k): new_node = node + str(i) if new_node not in visited: visited.add(new_node) dfs(new_node[1:]) # The next node is the suffix of length n-1 ans.append(str(i)) # Add the digit that created the new_node # Start with n-1 zeros as the initial node start_node = "0" * (n - 1) dfs(start_node) # Prepend the initial (n-1) zeros to form the full sequence return "".join(ans[::-1]) + start_node 7. Russian Doll Envelopes Problem Type: Dynamic Programming, Longest Increasing Subsequence (LIS) Concept: Given a set of envelopes `(width, height)`, find the maximum number of envelopes you can "russian doll" (put one inside another). Notes: Sort envelopes by width in ascending order. If widths are equal, sort by height in descending order to avoid considering envelopes of the same width for LIS (an envelope cannot contain another of the same width). Then, find the Longest Increasing Subsequence (LIS) of heights. This reduces the 2D problem to a 1D LIS problem. Snippet (LIS with Binary Search): import bisect def maxEnvelopes(envelopes): # Sort by width ascending, then by height descending envelopes.sort(key=lambda x: (x[0], -x[1])) # Find the LIS of heights tails = [] # tails[i] is the smallest tail of all increasing subsequences of length i+1 for w, h in envelopes: idx = bisect.bisect_left(tails, h) if idx == len(tails): tails.append(h) else: tails[idx] = h return len(tails) 8. Burst Balloons Problem Type: Dynamic Programming (Interval DP) Concept: Given balloons with values, burst them to maximize coins. When balloon $i$ is burst, you get `nums[left] * nums[i] * nums[right]` coins. Notes: The key is to think about the *last* balloon burst in an interval `(i, j)`. If `k` is the last balloon burst in `(i, j)`, then `i` and `j` become adjacent. The problem then breaks into two independent subproblems: `(i, k)` and `(k, j)`. Add dummy balloons with value 1 at both ends to handle boundaries. Let `dp[i][j]` be the maximum coins from bursting balloons in `(i, j)` (exclusive). `dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])` for `i Snippet (Interval DP): def maxCoins(nums): n = len(nums) # Add dummy balloons at ends nums = [1] + nums + [1] # dp[i][j] stores the maximum coins from bursting balloons # in the open interval (i, j) dp = [[0] * (n + 2) for _ in range(n + 2)] # Length of the interval (excluding i and j) for length in range(1, n + 1): # i is the left boundary (exclusive) for i in range(n - length + 1): j = i + length + 1 # j is the right boundary (exclusive) # k is the last balloon to burst in (i, j) for k in range(i + 1, j): coins = nums[i] * nums[k] * nums[j] dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + coins) return dp[0][n + 1] 9. Maximum Profit in Job Scheduling Problem Type: Dynamic Programming, Binary Search, Sorting Concept: Given jobs with `(startTime, endTime, profit)`, find the maximum profit from non-overlapping jobs. Notes: Sort jobs by `endTime`. For each job `i`, we have two choices: 1. Don't include job `i`: profit is `dp[i-1]`. 2. Include job `i`: profit is `profit[i]` + profit from the latest non-overlapping job before `startTime[i]`. Use binary search (or `bisect_right`) to find this "previous" job. `dp[i]` represents max profit considering jobs up to index `i`. Snippet (DP with Binary Search): import bisect def jobScheduling(startTime, endTime, profit): jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1]) n = len(jobs) # dp[i] = max profit considering jobs[0...i-1] # dp[0] = 0 dp_profit = [0] * (n + 1) # end_times_list stores the end times of jobs, used for binary search end_times_list = [job[1] for job in jobs] for i in range(n): s, e, p = jobs[i] # Option 1: Don't take current job profit_not_taken = dp_profit[i] # Option 2: Take current job # Find the latest job that ends before or at s # bisect_right returns insertion point, so it's the index AFTER the last valid job # We need the index of the last valid job, which is index - 1 # The result of bisect_right is 0-indexed, and dp_profit is 1-indexed. # So, if bisect returns k, it means jobs[k-1] is the last job whose end_time s`. # `bisect_right` returns an index `k` such that all `jobs[x][1]` for `x 10. Cherry Pickup Problem Type: Dynamic Programming, Multi-State DP Concept: Find the maximum cherries two people can collect starting from `(0,0)`, reaching `(N-1,N-1)` and returning to `(0,0)`, such that a cell's cherry is collected only once. Notes: This is equivalent to two people moving from `(0,0)` to `(N-1,N-1)` simultaneously. The state can be `dp[r1][c1][r2][c2]`, representing max cherries when robot 1 is at `(r1,c1)` and robot 2 is at `(r2,c2)`. Since total steps `r+c` must be equal for both robots, simplify state to `dp[steps][r1][r2]`. `c1 = steps - r1`, `c2 = steps - r2`. Careful with cherry collection: if `(r1,c1) == (r2,c2)`, collect cherries only once. Snippet (DP): def cherryPickup(grid): N = len(grid) # dp[r1][c1][r2] stores max cherries when robot1 is at (r1, c1) and robot2 is at (r2, c2) # where c2 = r1 + c1 - r2 (since both take same number of steps) # Initialize with -infinity for unreachable states dp = [[[-float('inf')] * N for _ in range(N)] for _ in range(N)] # Base case: both robots start at (0,0) dp[0][0][0] = grid[0][0] # Iterate over total steps (r1 + c1) from 1 to 2*(N-1) for t in range(1, 2 * N - 1): for r1 in range(N): for r2 in range(N): c1 = t - r1 c2 = t - r2 # Check if r1, c1, r2, c2 are valid coordinates if not (0 0 and r2 > 0: prev_max = max(prev_max, dp[r1-1][r2-1][r1-1]) # Robot 1 moves down, Robot 2 moves right if r1 > 0 and c2 > 0: prev_max = max(prev_max, dp[r1-1][r2][r1-1]) # dp[r1-1][r2][r1-1] -> prev_r1=r1-1, prev_r2=r2 # Robot 1 moves right, Robot 2 moves down if c1 > 0 and r2 > 0: prev_max = max(prev_max, dp[r1][r2-1][r1]) # dp[r1][r2-1][r1] -> prev_r1=r1, prev_r2=r2-1 # Robot 1 moves right, Robot 2 moves right if c1 > 0 and c2 > 0: prev_max = max(prev_max, dp[r1][r2][r1]) # dp[r1][r2][r1] -> prev_r1=r1, prev_r2=r2 if prev_max != -float('inf'): dp[r1][r2][r1] = max(dp[r1][r2][r1], prev_max + cherries) return max(0, dp[N-1][N-1][N-1]) # Ensure non-negative result 11. Longest Increasing Path in a Matrix Problem Type: Dynamic Programming, DFS with Memoization Concept: Find the length of the longest increasing path in a matrix, moving horizontally or vertically. Notes: Use DFS with memoization. `dp[i][j]` stores the longest increasing path starting from `(i,j)`. When calculating `dp[i][j]`, recursively call DFS on its valid neighbors `(nr, nc)` where `matrix[nr][nc] > matrix[i][j]`. The result for `dp[i][j]` will be `1 + max(dp[nr][nc])` over such neighbors. Snippet (DFS with Memoization): def longestIncreasingPath(matrix): if not matrix or not matrix[0]: return 0 rows, cols = len(matrix), len(matrix[0]) memo = {} # Stores (r, c) -> length of LIP starting at (r,c) def dfs(r, c): if (r, c) in memo: return memo[(r, c)] max_len = 1 # Minimum length is 1 (the cell itself) # Directions: up, down, left, right directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] for dr, dc in directions: nr, nc = r + dr, c + dc if 0 matrix[r][c]: max_len = max(max_len, 1 + dfs(nr, nc)) memo[(r, c)] = max_len return max_len overall_max = 0 for r in range(rows): for c in range(cols): overall_max = max(overall_max, dfs(r, c)) return overall_max 12. Wildcard Matching Problem Type: Dynamic Programming, Two Pointers (Greedy) Concept: Implement wildcard pattern matching with `?` (matches any single character) and `*` (matches any sequence of characters, including empty sequence). Notes: DP Approach: `dp[i][j]` is true if `s[0...i-1]` matches `p[0...j-1]`. - If `p[j-1]` is `?` or `s[i-1] == p[j-1]`: `dp[i][j] = dp[i-1][j-1]`. - If `p[j-1]` is `*`: `dp[i][j] = dp[i-1][j]` (match `*` with `s[i-1]`) OR `dp[i][j-1]` (match `*` with empty string). Greedy Approach (Two Pointers): More complex to implement correctly but can be faster. Maintain pointers for `s` and `p`, and `star_idx` for the last `*` encountered and `match_idx` for the position in `s` corresponding to `star_idx`. Snippet (DP): def isMatch(s, p): m, n = len(s), len(p) dp = [[False] * (n + 1) for _ in range(m + 1)] # Base cases dp[0][0] = True # Empty string matches empty pattern # Handle patterns like "a*", "*", "**" matching empty string for j in range(1, n + 1): if p[j-1] == '*': dp[0][j] = dp[0][j-1] for i in range(1, m + 1): for j in range(1, n + 1): if p[j-1] == '?': dp[i][j] = dp[i-1][j-1] elif p[j-1] == '*': # '*' matches empty string (dp[i][j-1]) # OR '*' matches s[i-1] (dp[i-1][j]) dp[i][j] = dp[i][j-1] or dp[i-1][j] else: # p[j-1] is a regular character dp[i][j] = dp[i-1][j-1] and (s[i-1] == p[j-1]) return dp[m][n] 13. Distinct Subsequences Problem Type: Dynamic Programming Concept: Given two strings `s` and `t`, count the number of distinct subsequences of `s` that equal `t`. Notes: `dp[i][j]` is the number of distinct subsequences of `s[0...i-1]` that equal `t[0...j-1]`. - If `s[i-1] == t[j-1]`: `dp[i][j] = dp[i-1][j-1]` (match `s[i-1]` with `t[j-1]`) + `dp[i-1][j]` (don't match `s[i-1]` with `t[j-1]`, try to form `t[0...j-1]` using `s[0...i-2]`). - If `s[i-1] != t[j-1]`: `dp[i][j] = dp[i-1][j]` (must skip `s[i-1]`). Base cases: `dp[i][0] = 1` (empty string `t` is always a subsequence of any `s`), `dp[0][j] = 0` for `j > 0`. Snippet (DP): def numDistinct(s, t): m, n = len(s), len(t) # dp[i][j] is the number of distinct subsequences of s[:i] which equals t[:j] dp = [[0] * (n + 1) for _ in range(m + 1)] # Base case: empty string t is always a subsequence of any s (1 way) for i in range(m + 1): dp[i][0] = 1 for i in range(1, m + 1): for j in range(1, n + 1): if s[i-1] == t[j-1]: # Case 1: Match s[i-1] with t[j-1] # Then we need to find subsequences of s[:i-1] that match t[:j-1] # Case 2: Don't match s[i-1] with t[j-1] # Then we need to find subsequences of s[:i-1] that match t[:j] dp[i][j] = dp[i-1][j-1] + dp[i-1][j] else: # s[i-1] cannot match t[j-1], so we must discard s[i-1] # Find subsequences of s[:i-1] that match t[:j] dp[i][j] = dp[i-1][j] return dp[m][n] 14. Palindrome Partitioning II Problem Type: Dynamic Programming Concept: Given a string `s`, partition `s` such that every substring of the partition is a palindrome. Return the minimum cuts needed. Notes: 1. Precompute `is_palindrome[i][j]` (boolean) indicating if `s[i...j]` is a palindrome. This can be done with another DP. 2. `dp[i]` is the minimum cuts needed for `s[0...i-1]`. `dp[i] = min(dp[j] + 1)` for `0 Snippet (DP): def minCut(s): n = len(s) # Step 1: Precompute all palindromic substrings is_palindrome = [[False] * n for _ in range(n)] for i in range(n): is_palindrome[i][i] = True # Single characters are palindromes for i in range(n - 1): is_palindrome[i][i+1] = (s[i] == s[i+1]) # Two characters for length in range(3, n + 1): for i in range(n - length + 1): j = i + length - 1 is_palindrome[i][j] = (s[i] == s[j] and is_palindrome[i+1][j-1]) # Step 2: Calculate minimum cuts # dp[i] = minimum cuts for s[0...i-1] # To handle base case (s[0...k] is a palindrome, 0 cuts), # we can say dp[i] is min cuts for s[0...i]. # Then dp[i] = 0 if s[0...i] is palindrome. # Else dp[i] = min(dp[j] + 1) for j 15. Binary Tree Cameras Problem Type: Tree DP, Greedy, DFS Concept: Place minimum cameras on nodes in a binary tree such that every node is covered (either has a camera, or its parent/child has a camera). Notes: This is a greedy problem best solved with a post-order DFS. For each node, return a state: - `0`: Node has a camera. - `1`: Node is covered but has no camera. - `2`: Node is not covered (needs a camera, or its parent needs one to cover it). When processing a node, based on its children's states, decide its own state and update the total camera count. If a child is `2` (uncovered), the current node *must* have a camera (`state=0`). If a child is `0` (has camera), the current node is covered (`state=1`). Otherwise, the current node is `2` (uncovered). The root node needs special handling if it ends up in state `2`. Snippet (DFS Greedy): # Definition for a binary tree node. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def minCameraCover(self, root: Optional[TreeNode]) -> int: self.cameras = 0 # States: # 0: Node has a camera # 1: Node is covered, but has no camera # 2: Node is not covered, needs a camera from parent or self def dfs(node): if not node: return 1 # Null node is considered covered (doesn't need a camera) left_state = dfs(node.left) right_state = dfs(node.right) if left_state == 2 or right_state == 2: # If any child is not covered, current node MUST have a camera self.cameras += 1 return 0 # Current node has a camera if left_state == 0 or right_state == 0: # If any child has a camera, current node is covered return 1 # Current node is covered, no camera # If children are covered (state 1) or null (state 1), # current node is not covered by children, needs parent camera return 2 # Current node is not covered # After DFS, if the root is not covered, it needs a camera if dfs(root) == 2: self.cameras += 1 return self.cameras 16. Sum of Distances in Tree Problem Type: Tree DP, Two DFS passes Concept: Given an undirected tree, return an array `ans` where `ans[i]` is the sum of distances between node `i` and all other nodes in the tree. Notes: 1. First DFS (post-order): Calculate `count[node]` (number of nodes in subtree rooted at `node`) and `sum_dist_subtree[node]` (sum of distances from `node` to all nodes in its subtree). `count[node] = 1 + sum(count[child])` `sum_dist_subtree[node] = sum(sum_dist_subtree[child] + count[child])` 2. Second DFS (pre-order): Calculate `ans[node]`. `ans[root]` is `sum_dist_subtree[root]`. For any other node `child` of `parent`: `ans[child] = ans[parent] - count[child] + (N - count[child])` Explanation: When moving from `parent` to `child`, all nodes in `child`'s subtree are now 1 unit closer to `child` (so subtract `count[child]`). All nodes *outside* `child`'s subtree are now 1 unit farther from `child` (so add `N - count[child]`). Snippet (Two DFS): from collections import defaultdict def sumOfDistancesInTree(n, edges): adj = defaultdict(list) for u, v in edges: adj[u].append(v) adj[v].append(u) count = [0] * n # Number of nodes in subtree rooted at i ans = [0] * n # sum of distances from i to all nodes (final result) # DFS1: Post-order traversal to calculate count and sum_dist_subtree (from node to its subtree) def dfs1(node, parent): count[node] = 1 for child in adj[node]: if child != parent: dfs1(child, node) count[node] += count[child] ans[node] += ans[child] + count[child] # Subtree sum of distances # DFS2: Pre-order traversal to calculate final ans for all nodes def dfs2(node, parent): for child in adj[node]: if child != parent: # ans[child] = ans[parent] - count[child] + (N - count[child]) ans[child] = ans[node] - count[child] + (n - count[child]) dfs2(child, node) dfs1(0, -1) # Start DFS1 from node 0 with no parent dfs2(0, -1) # Start DFS2 from node 0 with no parent return ans 17. Shortest Path Visiting All Nodes Problem Type: BFS, Bitmask DP Concept: Find the shortest path length to visit all nodes in a graph. You can start and end at any node. Notes: This is a variation of TSP. Use BFS. State in BFS queue: `(node, mask, dist)`. - `node`: current node. - `mask`: bitmask representing visited nodes (e.g., `1 Snippet (BFS with Bitmask): from collections import deque def shortestPathLength(graph): n = len(graph) if n == 1: return 0 # (node, mask, dist) queue = deque() # visited state: (node, mask) visited = set() # Initialize with all possible starting nodes for i in range(n): initial_mask = (1 18. Number of Digit One Problem Type: Digit DP Concept: Count the total number of digit 1 appearing in all non-negative integers less than or equal to `n`. Notes: A classic digit DP problem. Break down `n` into digits. Consider contributions of '1' at each digit position. For a given digit position `d` (e.g., units, tens, hundreds): - Count how many times '1' appears at this position due to lower digits varying. - Count how many times '1' appears at this position due to higher digits varying. Can be solved by iterating through digit positions and calculating contributions. Example: `n=13`. Units place: `1, 11`. `(13 // 10) * 1 + min(max(0, 13 % 10 - 1 + 1), 1)` Tens place: `10, 11, 12, 13`. `(13 // 100) * 10 + min(max(0, 13 % 100 - 10 + 1), 10)` General formula for `countDigitOne(n)`: Iterate `i` from `1` to `n` (by powers of 10): `ans += (n // (i * 10)) * i` (full blocks) `ans += min(max(0, n % (i * 10) - i + 1), i)` (partial block) Snippet (Mathematical Approach): def countDigitOne(n: int) -> int: if n n // 10: # Avoid overflow if power_of_10 * 10 exceeds max int break power_of_10 *= 10 return count 19. Numbers At Most N Given Digit Set Problem Type: Digit DP Concept: Given a sorted set of digits `D`, find the count of positive integers that can be formed using these digits, which are less than or equal to a given integer `N`. Notes: Convert `N` to a string. Use a recursive DFS function with memoization. The state includes `idx` (current digit position), `tight` (boolean, true if current number is restricted by `N`'s digits), `is_leading_zero` (boolean, true if current number is still forming leading zeros). The `tight` constraint means the current digit cannot exceed `N[idx]`. `is_leading_zero` is for handling numbers shorter than `N` (e.g., if `N=100`, count `1, 2, ..., 9` as well). Snippet (Digit DP): def atMostNGivenDigitSet(digits, n): S = [d for d in digits] # Convert to list for easier iteration N_str = str(n) L = len(N_str) # memo[idx][tight][is_leading_zero] memo = {} def dp(idx, tight, is_leading_zero): if idx == L: return 1 if not is_leading_zero else 0 # 1 if a valid number was formed, 0 if it's just leading zeros if (idx, tight, is_leading_zero) in memo: return memo[(idx, tight, is_leading_zero)] ans = 0 upper_bound = int(N_str[idx]) if tight else 9 for d_str in S: d_int = int(d_str) if d_int > upper_bound: break # Digits are sorted, so no need to check further # If we are currently forming leading zeros and the current digit is 0, # we can continue forming leading zeros. if is_leading_zero and d_int == 0: ans += dp(idx + 1, tight and (d_int == upper_bound), True) else: # If d_int is not 0 (or we are past leading zeros), # this digit contributes to a non-zero prefix. ans += dp(idx + 1, tight and (d_int == upper_bound), False) # If we are still forming leading zeros, we can also choose to not place a digit # at this position, effectively forming a shorter number. # This part handles numbers shorter than N. E.g., if N=234, we count 1-digit and 2-digit numbers. # This is typically handled by a separate loop or a different structure in digit DP. # Let's adjust the DP definition slightly for common patterns: # A common way to handle shorter numbers: # dp(idx, tight, is_started) where is_started means we've placed a non-zero digit. # If is_started is False, we can either place a digit or skip (to form shorter number). # Let's refine the dp state and base cases. memo[(idx, tight, is_leading_zero)] = ans return ans # The standard digit DP approach usually counts numbers in a range [0, N] # and handles shorter numbers by allowing an "empty" choice for digits. # A simpler way to count numbers upper_limit: break if not is_num and d_int == 0: # If it's a leading zero, and we haven't started a number # We already handled the "skip" case with dfs(idx+1, False, False) # If we place a 0 here, it's still considered a leading zero # We should only proceed if d_int > 0 or if is_num is already True continue res += dfs(idx + 1, is_tight and (d_int == upper_limit), True) dp_memo[idx][is_tight][is_num] = res return res return dfs(0, True, False) # Start from index 0, tight=True, is_num=False 20. Best Time to Buy and Sell Stock III Problem Type: Dynamic Programming Concept: Maximize profit by completing at most two transactions (buy then sell). Notes: `dp[k][i]` = max profit with at most `k` transactions up to day `i`. `dp[k][i] = max(dp[k][i-1], prices[i] - prices[j] + dp[k-1][j-1])` for `0 Snippet (DP with O(1) space optimization for 2 transactions): def maxProfit(prices): buy1 = float('-inf') sell1 = 0 buy2 = float('-inf') sell2 = 0 for price in prices: # Max profit after first buy (minimize cost of buying) buy1 = max(buy1, -price) # Max profit after first sell (max of not selling or selling now) sell1 = max(sell1, buy1 + price) # Max profit after second buy (minimize cost of buying after first sell) buy2 = max(buy2, sell1 - price) # Max profit after second sell (max of not selling or selling now) sell2 = max(sell2, buy2 + price) return sell2 21. Shortest Palindrome Problem Type: String, KMP (Knuth-Morris-Pratt) Algorithm, Palindrome Concept: Given a string `s`, add characters to the beginning of it to make it a palindrome with the minimum number of characters. Notes: The problem is to find the longest palindromic prefix of `s`. If `s = "abacaba"`, the longest palindromic prefix is `s` itself. If `s = "aacecaaa"`, the longest palindromic prefix is `aacecaa`. The remaining suffix `a` needs to be reversed and prepended. This can be found using KMP's LPS (Longest Proper Prefix which is also a Suffix) array. Construct a new string `temp = s + '#' + s_reversed`. The last element of the LPS array for `temp` gives the length of the longest palindromic prefix of `s`. Let `len_lps` be this length. The characters to prepend are `s[len_lps:]` reversed. Snippet (KMP): def shortestPalindrome(s: str) -> str: n = len(s) if n == 0: return "" rev_s = s[::-1] # Construct the KMP string: s + '#' + rev_s # '#' is a separator character not present in s temp = s + "#" + rev_s m = len(temp) # Compute the LPS (Longest Proper Prefix which is also a Suffix) array for temp lps = [0] * m length = 0 # Length of the previous longest prefix suffix i = 1 while i 22. Count of Smaller Numbers After Self Problem Type: Divide and Conquer (Merge Sort), Fenwick Tree (BIT), Segment Tree Concept: For each element `nums[i]`, count the number of elements `nums[j]` such that `j > i` and `nums[j] Notes: - Merge Sort: While merging two sorted halves `left` and `right`, if an element `x` from `left` is greater than an element `y` from `right`, then `y` is smaller than `x`. All elements remaining in `right` after `y` are also smaller than `x`. Update counts accordingly. Store `(value, original_index)` pairs. - Fenwick Tree (BIT) / Segment Tree: Coordinate compress `nums` values. Iterate `nums` from right to left. For each `nums[i]`, query the sum in BIT for values less than `nums[i]`. Then update BIT by adding 1 at `nums[i]`'s compressed value. Snippet (Merge Sort): def countSmaller(nums): n = len(nums) result = [0] * n # Store (value, original_index) pairs indexed_nums = [] for i in range(n): indexed_nums.append((nums[i], i)) def merge_sort(arr): if len(arr) 23. Max Points on a Line Problem Type: Geometry, Math, Hash Map Concept: Given an array of points `(x, y)`, find the maximum number of points that lie on the same straight line. Notes: Iterate through each pair of points to define a line. For each line, count how many other points lie on it. To represent a line uniquely: - Calculate slope `(y2-y1) / (x2-x1)`. Use `gcd` to simplify the fraction to avoid floating-point issues (e.g., `1/2` vs `2/4`). - Handle vertical lines `(x1 == x2)` separately (slope is infinity). - Handle duplicate points: if multiple points are at the same `(x,y)`, they all count towards the max. Use a hash map to store `slope -> count`. Reset map for each starting point. Snippet (Hash Map & GCD): import math from collections import defaultdict def maxPoints(points): n = len(points) if n count for lines passing through points[i] slopes = defaultdict(int) duplicates = 1 # Count of points identical to points[i] for j in range(i + 1, n): if points[i][0] == points[j][0] and points[i][1] == points[j][1]: duplicates += 1 else: # Calculate slope (dy, dx) and simplify using GCD dy = points[j][1] - points[i][1] dx = points[j][0] - points[i][0] # Handle vertical lines if dx == 0: slopes['vertical'] += 1 else: common_divisor = math.gcd(dy, dx) slopes[(dy // common_divisor, dx // common_divisor)] += 1 # Max points on a line for lines passing through points[i] # Includes duplicates max_for_point_i = 0 if slopes: max_for_point_i = max(slopes.values()) max_overall = max(max_overall, max_for_point_i + duplicates) return max_overall 24. Minimum Interval to Include Each Query Problem Type: Heap (Priority Queue), Sorting, Sweep Line Concept: Given intervals `[li, ri]` and queries `[qi]`, find the minimum-length interval that contains each query point. If no such interval exists, return -1. Notes: 1. Sort `intervals` by `li`. 2. Create `(query_value, original_index)` pairs for queries and sort them by `query_value`. 3. Use a min-heap to store active intervals, prioritized by their length `(ri - li + 1)`. 4. Iterate through sorted queries: - Add all intervals `[L, R]` to the heap where `L Snippet (Heap + Sorting): import heapq def minInterval(intervals, queries): intervals.sort() # Sort intervals by start time # Store queries as (value, original_index) and sort by value sorted_queries = sorted([(q, i) for i, q in enumerate(queries)]) result = [-1] * len(queries) # Min-heap to store (interval_length, end_point) for active intervals # An active interval is one whose start_point 25. The Skyline Problem Problem Type: Sweep Line, Heap (Priority Queue) Concept: Given a list of rectangular buildings, return the skyline formed by their outer contours. Notes: 1. Convert buildings into "events": `(x_coordinate, height, type)`. - `type = -height` for start of building (entering a building). - `type = height` for end of building (leaving a building). 2. Sort events: primarily by x-coordinate. For ties: - Start events `(-height)` before end events `(height)`. - For multiple start events at same x, taller buildings first. - For multiple end events at same x, shorter buildings first. - Start event before end event if `height`s are equal (to process "overlapping" edges correctly). 3. Use a max-heap (or `collections.Counter` acting as a multiset for heights) to keep track of active building heights. The top of the heap is the current max height. 4. Iterate through sorted events: - If start event: add height to heap. - If end event: remove height from heap. - If current max height changes from `prev_max_height`, add `(x_coordinate, current_max_height)` to result. Snippet (Sweep Line + Heap/Multiset): import heapq from collections import defaultdict def getSkyline(buildings): # Create events: (x, height, type) # type: -height for start of building, height for end of building # Negative height for start helps in sorting: start events come before end events # And for same x, taller starts are processed first. # For end events, positive height, shorter ends are processed first. events = [] for l, r, h in buildings: events.append((l, -h)) # Start of building events.append((r, h)) # End of building # Sort events: # 1. By x-coordinate # 2. If x-coordinates are equal: # - Start events before end events (negative height 0. # Current heights of active buildings active_heights = [0] # Initialize with ground level (0) prev_max_height = 0 for x, h_type in events: if h_type 26. Longest Duplicate Substring Problem Type: String, Binary Search, Rabin-Karp (Rolling Hash), Suffix Array/Tree Concept: Find the longest substring that appears at least twice in the string. Notes: 1. Binary Search on Length: The length of the longest duplicate substring can be binary searched. If a duplicate substring of length `L` exists, then duplicate substrings of length `L-1` also exist. 2. Check Function: For a given length `L`, check if a duplicate substring of length `L` exists. - Use Rabin-Karp (rolling hash) to calculate hashes of all substrings of length `L`. Store hashes in a set. If a hash is seen twice, a duplicate exists. Handle hash collisions with a second hash or by comparing strings. - A suffix array/tree can also solve this efficiently by finding the longest common prefix (LCP) array. Snippet (Binary Search + Rolling Hash): def longestDupSubstring(s: str) -> str: n = len(s) # Binary search for the length of the longest duplicate substring low = 0 high = n - 1 # Max possible length is n-1 ans_len = 0 ans_start_idx = 0 # Base for rolling hash (a prime number, often 26 or 31 for lowercase English) BASE = 26 # Modulo for rolling hash to prevent overflow (a large prime number) MOD = 1_000_000_007 # Helper function to check if a duplicate substring of given length exists def check(length): if length == 0: return -1 # No duplicate substring of length 0 # Calculate initial hash for substring s[0:length] current_hash = 0 for i in range(length): current_hash = (current_hash * BASE + (ord(s[i]) - ord('a'))) % MOD # Precompute power of BASE for removing leading digit power_base_L = pow(BASE, length, MOD) # Store hashes and their starting indices seen_hashes = {current_hash: 0} for i in range(1, n - length + 1): # Update hash for s[i : i + length] # Remove hash contribution of s[i-1] current_hash = (current_hash * BASE - (ord(s[i-1]) - ord('a')) * power_base_L + (ord(s[i+length-1]) - ord('a'))) % MOD if current_hash