# Use a hash map for O(1) key lookups and a doubly linked list to manage recency.
III. Stacks & Queues
• Largest Rectangle in Histogram:
# Use a monotonic increasing stack to track indices of bars.
• Car Fleet: Calculate the number of car fleets that will arrive at the destination.
# Sort cars by position. Use a stack to merge fleets based on arrival time.
• Asteroid Collision:
# Use a stack to simulate collisions, handling different sizes and directions.
• Decode String (e.g.,
3[a2[c]]):# Use a stack to keep track of counts and previous strings.
• Simplify Path (Unix-style):
# Split by '/' and use a stack to handle '..' and '.'.
• Moving Average from Data Stream:
# Use a `collections.deque` with a fixed `maxlen` to efficiently calculate the sum.
• Basic Calculator II: Implement a calculator with
+, -, *, /.# Use a stack to handle operator precedence, processing `*` and `/` immediately.
IV. Trees & Graphs
• Binary Tree Zigzag Level Order Traversal:
# BFS with a deque. Alternate the direction of appending to the level result list.
• Construct Binary Tree from Preorder and Inorder Traversal:
# Use preorder to find the root and inorder to find the left/right subtrees. Recurse.
• Populating Next Right Pointers in Each Node:
# Use level-order traversal (BFS) or a clever DFS/recursive approach.
• Binary Tree Maximum Path Sum:
# Recursive DFS. At each node, return the max path down, but update a global max with the full path through that node.
• Balanced Binary Tree Check:
# DFS. For each node, get the height of left/right subtrees. If diff > 1, it's unbalanced.
• Symmetric Tree: Check if a tree is a mirror of itself.
# Use a recursive helper function that compares two nodes `is_mirror(t1, t2)`.
• Path Sum II: Find all root-to-leaf paths that sum to a target.
# Backtracking (DFS) with a path list and current sum.
• Validate IP Address:
# String parsing with careful checks for IPv4 (numeric ranges) and IPv6 (hex, length).
• Find Leaves of Binary Tree: Collect leaves, remove them, repeat.
# Use a modified DFS that returns the height of a node. Group nodes by height.
• Graph Valid Tree: Check if a graph is a valid tree.
# A valid tree has `n-1` edges and is fully connected (no cycles). Use DFS/BFS or Union-Find.
• Pacific Atlantic Water Flow:
# Start DFS/BFS from all cells on the ocean borders and find the intersection of reachable cells.
• Redundant Connection: Find a redundant edge in a graph that makes a cycle.
# Use Union-Find. The first edge that connects two nodes already in the same set is redundant.
• Network Delay Time: Find the time for a signal to reach all nodes.
# Dijkstra's algorithm to find the shortest path from the source to all other nodes.
• Cheapest Flights Within K Stops:
# Modified Dijkstra's or Bellman-Ford, keeping track of the number of stops.
• Alien Dictionary: Find the order of characters from a sorted list of words.
# Build a dependency graph, then perform a topological sort.
V. Dynamic Programming & Recursion
• Decode Ways: Number of ways to decode a string of digits.
# DP: `dp[i]` is the number of ways to decode `s[:i]`. Consider one and two-digit decodings.
• Partition Equal Subset Sum:
# DP (knapsack variation). Check if a subset sums to `total_sum / 2`.
• Best Time to Buy and Sell Stock II: You can buy and sell multiple times.