42 articles
Master Tarjan's SCC algorithm: a single DFS pass with discovery times, low-link values, and an explicit stack to identify all strongly connected components in O(V + E). The interview gold standard for directed graph decomposition, asked at Google, Meta, and Uber.
Use Tarjan's low-link technique to find every bridge (critical edge) and articulation point (cut vertex) in an undirected graph in O(V + E). The interview pattern behind LeetCode 1192 Critical Connections, asked at Google, Meta, and Amazon.
Master advanced topological sort: DFS post-order, Kahn's BFS algorithm, cycle detection, lexicographically smallest order, and parallel level scheduling. The pattern behind LeetCode 210 Course Schedule II, asked at Google, Amazon, and Meta.
Master bipartite checking and graph coloring: a single BFS or DFS pass that 2-colors a graph and proves it is bipartite, or finds an odd cycle. The pattern behind LeetCode 785 Is Graph Bipartite and LeetCode 886 Possible Bipartition, asked at Google, Meta, and Amazon.
Master LeetCode 1192 Critical Connections in a Network: a textbook Tarjan bridge-finding algorithm using DFS with discovery times and low-link values to detect every edge whose removal disconnects the graph. A FAANG hard graph interview classic at Google, Amazon, and Meta.
Master LeetCode 332 Reconstruct Itinerary using Hierholzer's algorithm: a single DFS that traverses every edge exactly once and assembles an Eulerian path via post-order insertion. A FAANG hard interview classic asked at Google, Meta, and Amazon, and the foundational pattern for de Bruijn sequences and DNA fragment assembly.
Master BFS and DFS on graphs and grids with the seven core patterns that show up in 90 percent of FAANG graph interviews. Learn flood fill, multi-source BFS, shortest path on unweighted graphs, and connected components with Python and JavaScript code.
Solve LeetCode 200 Number of Islands with DFS flood fill in O(m*n) time. The most asked grid traversal problem at Amazon, Google, and Meta — covers DFS, BFS, and Union-Find approaches with Python and JavaScript.
Solve LeetCode 733 Flood Fill with simple DFS in O(m*n) time. The paint bucket tool from MS Paint reduced to a five-line recursion — the cleanest introduction to grid traversal you can give an interviewer.
Solve LeetCode 463 Island Perimeter in O(m*n) without DFS or BFS. The trick: every land cell contributes 4 edges, minus 2 for each shared edge with another land cell. Pure counting beats traversal.
LC 1020 Number of Enclaves asks you to count land cells that cannot reach the grid boundary. The trick is to flip the problem: flood-fill from the boundary inward, eliminating all reachable land, then count what remains.
LC 1905 Count Sub Islands asks how many islands in grid2 are subsets of islands in grid1. The critical trap is short-circuiting DFS on the first invalid cell — you must always complete the traversal to mark the whole island visited, while tracking validity separately.
Determine whether a word can be spelled by traversing adjacent cells without reusing any cell. The canonical DFS-with-backtracking template every grid-search interview problem builds on.
Count islands with unique shapes by encoding each DFS traversal path as a string and storing shapes in a set. A classic interview problem testing DFS + hashing.
Count land islands fully surrounded by water (no border touch). Flood-fill border land first to eliminate open islands, then count remaining closed components.
Find the minimum number of 0s to flip to connect two islands. Use DFS to color the first island, then multi-source BFS to expand outward until hitting the second island.
Find the path from top-left to bottom-right that minimizes the maximum absolute difference between consecutive cells. Dijkstra treats effort as edge weight; binary search + BFS checks feasibility for each candidate effort.
LC 743 Network Delay Time asks for the time a signal takes to reach all n nodes from source k. Single-source shortest path via Dijkstra gives every distance in O(E log V); the answer is the maximum among them.
LC 787 Cheapest Flights Within K Stops asks for the cheapest route from src to dst using at most k intermediate stops. Bellman-Ford with exactly k+1 relaxation rounds handles the stop constraint cleanly without Dijkstra getting confused by the layered state.
Complete cheatsheet for BFS and DFS on graphs and grids: 7 patterns, complexity table, common pitfalls, and problem index.
LC 430 Flatten a Multilevel Doubly Linked List is a medium interview problem at Microsoft and Amazon that uses DFS or an explicit stack to inline child sub-lists into the main list. Learn the iterative stack approach and the recursive approach with Python and JavaScript, step-by-step dry run, and interview tips.
Solve LeetCode 200 Number of Islands using BFS with a queue or DFS with a stack. The most asked grid interview question at Amazon, Google, Meta, and Microsoft, teaching connected components and flood fill.
Word Search II (LC 212) is the canonical FAANG hard combining trie data structures with grid backtracking. Build a trie from the dictionary, DFS each cell, and prune aggressively to convert an exponential brute force into a fast practical algorithm.
LC 437 Path Sum III counts all paths in a binary tree summing to a target. The optimal O(n) solution mirrors the subarray sum equals k trick — use a prefix sum frequency map with DFS backtracking, a pattern tested at Amazon and Google.
LC 114 Flatten Binary Tree to Linked List rearranges a binary tree into a right-skewed linked list in pre-order. The optimal O(1) space solution uses a Morris-like pointer manipulation trick tested at Amazon and Microsoft.
LC 863 All Nodes Distance K in Binary Tree finds all nodes exactly K edges from a target. The key insight is converting the tree to an undirected graph by recording parent pointers, then running BFS from the target — a pattern tested at Amazon and Google.
Solve LeetCode 129 Sum Root to Leaf Numbers with the carry-and-accumulate DFS pattern asked at Meta, Amazon, Google, and Microsoft. Includes Python and JavaScript code, dry run, and follow-ups.
Solve LeetCode 1448 Count Good Nodes in Binary Tree with the DFS carry-max pattern asked at Microsoft, Meta, and Amazon. Includes Python and JavaScript code, complexity analysis, and FAANG-style follow-ups.
LC 337 House Robber III extends the classic House Robber DP to a binary tree where adjacent nodes cannot both be robbed. The optimal O(n) solution uses post-order DFS returning a (rob, skip) pair — a fundamental tree DP pattern tested at Amazon and Microsoft.
LC 968 Binary Tree Cameras asks for the minimum number of cameras to monitor all nodes. The O(n) greedy solution assigns three states per node in a bottom-up DFS — delay camera placement as high as possible, a pattern tested at Amazon and Google.
LC 979 Distribute Coins in Binary Tree asks for minimum moves to give each node exactly one coin. The O(n) solution tracks coin excess flowing through each edge via post-order DFS — a pattern tested at Amazon and Google that elegantly converts a counting problem into a flow problem.
LC 124 Binary Tree Maximum Path Sum finds the highest-value path in a binary tree where the path can start and end at any node. The O(n) solution uses a post-order DFS that tracks the global max while returning only one branch to the parent — a critical FAANG interview problem at Amazon, Google, and Facebook.
LC 297 Serialize and Deserialize Binary Tree is a top FAANG hard problem asked at Facebook, Amazon, and Google. The DFS preorder approach with null markers gives a compact O(n) codec; BFS level-order is more intuitive. Both are valid interview answers.
LC 1373 Maximum Sum BST in Binary Tree finds the highest sum among all BST subtrees of a binary tree. The O(n) solution uses post-order DFS returning a 4-tuple of (is_bst, min, max, sum) metadata — a hard FAANG problem tested at Amazon and Google.
LC 1008 Construct BST from Preorder Traversal reconstructs a binary search tree in O(n) using min-max bounds to decide left vs right placement — a clean recursion problem tested at Amazon and Google that showcases BST property exploitation.
LC 366 Find Leaves of Binary Tree groups nodes by their height (distance from the nearest leaf) using a post-order DFS — a problem asked at Amazon and LinkedIn that reveals an elegant alternative to iterative leaf removal.
Find the minimum seconds to collect all apples in an undirected tree using post-order DFS — include a subtree path only when it contains at least one apple.
Find the maximum |a - b| for any ancestor-descendant pair by tracking the running minimum and maximum along every root-to-leaf path during DFS.
Find the longest zigzag path in a binary tree by DFS — track the current direction and length, reset when the direction breaks, and update a global maximum.
LC 993 Cousins in Binary Tree checks if two nodes are at the same depth with different parents. The clean O(n) BFS solution processes one level at a time — a foundational tree problem tested at Amazon and Microsoft.
LC 589 N-ary Tree Preorder and LC 590 Postorder Traversal generalize binary tree DFS to trees with any number of children. These easy problems build the foundation for harder n-ary tree problems asked at Amazon and Google.
LeetCode 2265 (Medium). Count every node whose value equals the floor average of its own subtree using a single postorder DFS that returns sum and count to the parent.