Part 13 · Lesson 50 · read
Graph Traversal: BFS and DFS
Count islands, flood fill, rotting oranges and copy a graph.
On this page
Why we need a traversal
In lesson 49 we learned how to store graphs. Now we need to explore them. A traversal visits every vertex that you can reach from a starting vertex, each one exactly once. Two orders cover almost every interview question: breadth-first search (BFS) and depth-first search (DFS). Both take O(V + E) time on an adjacency list. Each vertex is handled once, and each edge is looked at once (twice if the graph is undirected).
Both need the same safety net: a visited set (a list of vertices you have already seen). A graph can have cycles. Without the set, you would go around the same loop forever.
Breadth-first search
BFS explores in ripples, like the rings on water when you drop a stone. First the start. Then everything one edge away. Then everything two edges away, and so on. The tool is a queue (first in, first out, like a line at a shop). New vertices join the back of the line, and we always explore the one at the front. In JavaScript, queue.shift() is slow (O(n)) because it moves every item. So we keep a head number that points to the front, and we just add 1 to it.
// Visit vertices in order of distance from start: first start, then its neighbours, then their neighbours...function bfs(graph, start) { const visited = new Set([start]); const queue = [start]; let head = 0; // take items out by moving an index: queue.shift() would be O(n) const order = []; while (head < queue.length) { const v = queue[head++]; order.push(v); for (const next of graph.get(v)) { if (!visited.has(next)) { visited.add(next); // mark it NOW, when it joins the queue queue.push(next); } } } return order;}const graph = new Map([ [0, [1, 2]], [1, [0, 3]], [2, [0, 3, 4]], [3, [1, 2, 5]], [4, [2, 5]], [5, [3, 4]],]);console.log(bfs(graph, 0)); // [ 0, 1, 2, 3, 4, 5 ]Vertices leave the queue in order of their distance from the start. So BFS finds the fewest edges to every vertex you can reach, in an unweighted graph (or a grid where every move costs the same):
// BFS also gives the fewest edges from start to every vertex we can reach (unweighted graphs only).function distances(graph, start) { const dist = new Map([[start, 0]]); // also works as the visited set const queue = [start]; let head = 0; while (head < queue.length) { const v = queue[head++]; for (const next of graph.get(v)) { if (!dist.has(next)) { dist.set(next, dist.get(v) + 1); queue.push(next); } } } return dist;}const graph = new Map([ [0, [1, 2]], [1, [0, 3]], [2, [0, 3, 4]], [3, [1, 2, 5]], [4, [2, 5]], [5, [3, 4]],]);console.log(distances(graph, 0)); // Map(6) { 0 => 0, 1 => 1, 2 => 1, 3 => 2, 4 => 2, 5 => 3 }Mark visited when you enqueue
You can mark a vertex as visited at two moments: when it joins the queue, or when it leaves the queue. Mark it when you enqueue it (put it in the queue). If you wait, each of its neighbours can add it again before its own turn comes. Then the queue holds the same vertex many times. In a dense graph (one with many edges), this can use up to E queue entries instead of V. On a grid problem it can be slow enough to time out. Marking early also keeps distances correct, because the first vertex to find it is the closest one.
const graph = new Map([[0, [1, 2]], [1, [0, 2, 3]], [2, [0, 1, 3]], [3, [1, 2]]]);function markOnDequeue() { // the tempting version that wastes work const queue = [0], visited = new Set(); let head = 0; while (head < queue.length) { const v = queue[head++]; if (visited.has(v)) continue; // a vertex can be in the queue several times visited.add(v); for (const next of graph.get(v)) if (!visited.has(next)) queue.push(next); } return queue;}function markOnEnqueue() { // the right habit const queue = [0], visited = new Set([0]); let head = 0; while (head < queue.length) { const v = queue[head++]; for (const next of graph.get(v)) { if (!visited.has(next)) { visited.add(next); queue.push(next); } } } return queue;}console.log(markOnDequeue()); // [ 0, 1, 2, 2, 3, 3 ] six entries for four verticesconsole.log(markOnEnqueue()); // [ 0, 1, 2, 3 ] exactly one per vertexTraced: BFS on a small graph
Mark the start as seen right away.
▶const visited = new Set([start]);2const queue = [start];3let head = 0;4while (head < queue.length) {5 const v = queue[head++];6 for (const next of graph.get(v)) {7 if (!visited.has(next)) {8 visited.add(next);9 queue.push(next);10 }11 }12}| start | 0 |
| visited | [0] |
Depth-first search
DFS goes as deep as it can before it goes back. Pick a neighbour, then one of its neighbours, and so on. Stop when a vertex has no neighbours you have not visited. Then go back to the previous vertex and try its next neighbour. The easiest way to write it is recursion (a function that calls itself). The call stack is the language's own list of waiting function calls. It remembers where to come back to. A stack is a list where you add and remove items at the same end, so the last item added is the first one removed (like a pile of plates). The difference in one line: a queue serves the oldest item first, and a stack serves the newest item first.
function dfs(graph, start) { const visited = new Set(); const order = []; function visit(v) { visited.add(v); order.push(v); for (const next of graph.get(v)) { if (!visited.has(next)) visit(next); // go as deep as possible before trying the next neighbour } } visit(start); return order;}const graph = new Map([ [0, [1, 2]], [1, [0, 3]], [2, [0, 3, 4]], [3, [1, 2, 5]], [4, [2, 5]], [5, [3, 4]],]);console.log(dfs(graph, 0)); // [ 0, 1, 3, 2, 4, 5 ]The recursion can go as deep as V levels. In JavaScript, a path of about ten thousand vertices or more may overflow the call stack (run out of room and crash). For huge inputs, write DFS with your own array as the stack:
// The same walk without recursion: the call stack becomes an array that you manage.function dfsIterative(graph, start) { const visited = new Set(); const stack = [start]; const order = []; while (stack.length) { const v = stack.pop(); if (visited.has(v)) continue; // with a stack we mark when we pop (a vertex may be pushed more than once) visited.add(v); order.push(v); const nbrs = graph.get(v); for (let i = nbrs.length - 1; i >= 0; i--) stack.push(nbrs[i]); // pushed in reverse, so the first neighbour is popped first } return order;}const graph = new Map([ [0, [1, 2]], [1, [0, 3]], [2, [0, 3, 4]], [3, [1, 2, 5]], [4, [2, 5]], [5, [3, 4]],]);console.log(dfsIterative(graph, 0)); // [ 0, 1, 3, 2, 4, 5 ]BFS or DFS?
| BFS | DFS | |
|---|---|---|
| Data structure | queue (first in, first out) | stack (last in, first out) or recursion |
| Visit order | closest vertices first, level by level | goes deep, then goes back when stuck |
| Fewest edges to a target (unweighted) | yes: the first time you reach it | no |
| Count components, flood a region, detect a path | works | works (often the shortest to write) |
| Extra memory | up to the width of one level | up to the length of the longest path |
| Time | O(V + E) | O(V + E) |
If the question says shortest, fewest steps or fewest moves in an unweighted setting, use BFS. For everything else (can I reach it? how many pieces? how big is the region?), either one works.
Connected components
One traversal visits exactly one connected component. To count them all, try every vertex as a start. Each time you find a vertex that is not visited yet, you have found a new component. Count it, and then traverse to mark the whole piece.
function countComponents(n, edges) { const graph = Array.from({ length: n }, () => []); for (const [a, b] of edges) { graph[a].push(b); graph[b].push(a); } const visited = new Array(n).fill(false); let count = 0; for (let start = 0; start < n; start++) { if (visited[start]) continue; count++; // a vertex that nobody has reached yet starts a new component visited[start] = true; const queue = [start]; let head = 0; while (head < queue.length) { const v = queue[head++]; for (const next of graph[v]) { if (!visited[next]) { visited[next] = true; queue.push(next); } } } } return count;}console.log(countComponents(6, [[0, 1], [1, 2], [3, 4]])); // 3 ({0,1,2}, {3,4}, {5})The outer loop adds only O(V). Every vertex and edge is still handled once in total, so the time stays O(V + E).
Grids: islands and flood fill
On a grid, the vertices are cells, and the neighbours are the four directions. Check the grid edges first (lesson 49). The classic task is to count islands. An island is a component of land cells. Walk over the grid. When you find a land cell you have not seen, add one to the count. Then traverse and erase the whole island, so it is not counted again. Changing the cell to water is the visited mark, so you do not need an extra set. Copy the grid first if the caller needs it unchanged.
// Count islands of '1' in a grid of '1' (land) and '0' (water).function numIslands(grid) { const rows = grid.length, cols = grid[0].length; const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]; let islands = 0; function sink(r, c) { // DFS: turn every connected land cell into water if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== "1") return; grid[r][c] = "0"; // also works as the visited mark for (const [dr, dc] of dirs) sink(r + dr, c + dc); } for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] === "1") { islands++; sink(r, c); } } } return islands;}console.log(numIslands([ ["1", "1", "0", "0"], ["1", "0", "0", "1"], ["0", "0", "1", "1"],])); // 2Flood fill (the paint-bucket tool in a drawing app) is the same walk. It repaints cells instead of counting. There is one trap. If the new colour is the same as the old colour, painting changes nothing. Then you cannot tell a visited cell from an unvisited one, and the recursion never ends.
// Flood fill: repaint the group of same-coloured cells that touches (sr, sc).function floodFill(image, sr, sc, color) { const old = image[sr][sc]; if (old === color) return image; // without this check, the fill would never stop function fill(r, c) { if (r < 0 || r >= image.length || c < 0 || c >= image[0].length || image[r][c] !== old) return; image[r][c] = color; // the new colour also marks the cell as visited fill(r + 1, c); fill(r - 1, c); fill(r, c + 1); fill(r, c - 1); } fill(sr, sc); return image;}console.log(floodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2)); // [ [ 2, 2, 2 ], [ 2, 2, 0 ], [ 2, 0, 1 ] ]r and c with the grid size before you read grid[r][c]. Reading grid[-1][0] throws an error, because grid[-1] is undefined.Multi-source BFS: rotting oranges
Sometimes the search starts from many places at once. Every minute, each rotten orange makes its fresh neighbours rot. Put all the rotten oranges into the queue at the start, and run BFS as usual. It works as if one start vertex were connected to all the sources. Each level of the search is one minute. Process the queue one level at a time (note where the level ends before you begin), and count the levels.
// Multi-source BFS: every rotten orange is in the queue at the start; each "round" is one minute.function orangesRotting(grid) { const rows = grid.length, cols = grid[0].length; const queue = []; let fresh = 0; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] === 2) queue.push([r, c]); else if (grid[r][c] === 1) fresh++; } } let head = 0, minutes = 0; while (head < queue.length && fresh > 0) { const levelEnd = queue.length; // everything in the queue now belongs to this minute while (head < levelEnd) { const [r, c] = queue[head++]; for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) { const nr = r + dr, nc = c + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) { grid[nr][nc] = 2; // mark when we enqueue fresh--; queue.push([nr, nc]); } } } minutes++; } return fresh === 0 ? minutes : -1;}console.log(orangesRotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]])); // 4console.log(orangesRotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]])); // -1 (the orange at the bottom-left cannot be reached)| Minute | Grid after it | What happened |
|---|---|---|
| 0 | 2 1 1 / 1 1 0 / 0 1 1 | the start: one rotten orange (top-left) |
| 1 | 2 2 1 / 2 1 0 / 0 1 1 | the top-left orange makes its fresh neighbours (0,1) and (1,0) rot |
| 2 | 2 2 2 / 2 2 0 / 0 1 1 | the two new rotten oranges make (0,2) and (1,1) rot |
| 3 | 2 2 2 / 2 2 0 / 0 2 1 | (1,1) makes (2,1) rot |
| 4 | 2 2 2 / 2 2 0 / 0 2 2 | (2,1) makes (2,2) rot. No fresh oranges are left, so the answer is 4 |
The loop stops as soon as no fresh orange is left, so the answer is 4 and not 5. If fresh oranges are still left when the queue is empty, they can never be reached. Then return -1.
Cloning a graph
To make a deep copy of a graph (a full copy that shares nothing with the original), you create a new node for each original node. Then you connect the copies to each other, not to the originals. A Map from each original node to its copy does two jobs. It is the visited set. It also lets you find the copy of any neighbour, so you can connect to it. The traversal can be BFS or DFS.
class Node { constructor(val, neighbors = []) { this.val = val; this.neighbors = neighbors; }}function cloneGraph(node) { if (!node) return null; const copies = new Map(); // original node -> its copy; also works as the visited set copies.set(node, new Node(node.val)); const queue = [node]; let head = 0; while (head < queue.length) { const orig = queue[head++]; for (const nb of orig.neighbors) { if (!copies.has(nb)) { copies.set(nb, new Node(nb.val)); queue.push(nb); } copies.get(orig).neighbors.push(copies.get(nb)); // connect copy to copy } } return copies.get(node);}// square 1 - 2 - 3 - 4 - 1const n1 = new Node(1), n2 = new Node(2), n3 = new Node(3), n4 = new Node(4);n1.neighbors = [n2, n4]; n2.neighbors = [n1, n3]; n3.neighbors = [n2, n4]; n4.neighbors = [n3, n1];const copy = cloneGraph(n1);console.log(copy.val, copy.neighbors.map((x) => x.val)); // 1 [ 2, 4 ]console.log(copy !== n1, copy.neighbors[0] !== n2); // true true (new objects, not the originals)Practice questions
First decide three things. What is a vertex? What are its neighbours? Do I need the shortest distance (BFS), or do I just need to cover a region (either one)?
You get a grid of "1" (land) and "0" (water) characters. Count the islands. An island is a group of land cells connected left-right or up-down.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
Look at every cell. At a land cell, count one island. Then use recursion (a function that calls itself) to turn that cell and all the land connected to it into water.
function numIslands(grid) { const rows = grid.length, cols = grid[0].length; let count = 0; function sink(r, c) { if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== "1") return; grid[r][c] = "0"; sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1); } for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] === "1") { count++; sink(r, c); } } } return count;}console.log(numIslands([["1", "1", "0", "0"], ["1", "1", "0", "0"], ["0", "0", "1", "0"], ["0", "0", "0", "1"]])); // 3console.log(numIslands([["1", "1", "1"], ["0", "1", "0"], ["1", "1", "1"]])); // 1It takes O(rows × cols) time, because every cell is visited a fixed number of times. The space is the recursion depth, which can be up to rows × cols for an island shaped like a snake. It changes the input. If that is not allowed, copy the grid first or use a visited array.
Use the same scan, but explore each island with a queue. Keep the input unchanged by using a separate grid of true/false values. Mark cells when you enqueue them.
function numIslands(grid) { const rows = grid.length, cols = grid[0].length; const visited = Array.from({ length: rows }, () => new Array(cols).fill(false)); const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]; let count = 0; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] !== "1" || visited[r][c]) continue; count++; visited[r][c] = true; const queue = [[r, c]]; let head = 0; while (head < queue.length) { const [cr, cc] = queue[head++]; for (const [dr, dc] of dirs) { const nr = cr + dr, nc = cc + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === "1" && !visited[nr][nc]) { visited[nr][nc] = true; queue.push([nr, nc]); } } } } } return count;}console.log(numIslands([["1", "1", "0", "0"], ["1", "1", "0", "0"], ["0", "0", "1", "0"], ["0", "0", "0", "1"]])); // 3console.log(numIslands([["1", "1", "1"], ["0", "1", "0"], ["1", "1", "1"]])); // 1It takes O(rows × cols) time and space. The queue only holds the cells at the edge of the search, and there is no deep recursion, so there is no risk of stack overflow. The input stays unchanged.
Recursive DFS is the shortest to write. Use BFS (or your own stack) when the grid is so large that deep recursion could be a problem, or when you must not change the input. (LeetCode 200.)
An image is a grid of numbers, and each number is a colour. Start at pixel (sr, sc). Change that pixel to color. Also change every pixel connected to it (up, down, left, right) that has the same original colour. Return the image.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
Paint the cell. Then use recursion on each neighbour that still has the old colour.
function floodFill(image, sr, sc, color) { const old = image[sr][sc]; if (old === color) return image; function fill(r, c) { if (r < 0 || r >= image.length || c < 0 || c >= image[0].length || image[r][c] !== old) return; image[r][c] = color; fill(r + 1, c); fill(r - 1, c); fill(r, c + 1); fill(r, c - 1); } fill(sr, sc); return image;}console.log(floodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2)); // [ [ 2, 2, 2 ], [ 2, 2, 0 ], [ 2, 0, 1 ] ]console.log(floodFill([[0, 0, 0], [0, 0, 0]], 0, 0, 0)); // [ [ 0, 0, 0 ], [ 0, 0, 0 ] ]It takes O(rows × cols) time. The new colour works as the visited mark. If it were the same as the old colour, painted cells would still look unpainted, and the recursion would never end. That is why we return early.
Paint the start and put it in the queue. For each cell you take out of the queue, paint the neighbours that have the old colour and put them in the queue.
function floodFill(image, sr, sc, color) { const old = image[sr][sc]; if (old === color) return image; image[sr][sc] = color; const queue = [[sr, sc]]; let head = 0; while (head < queue.length) { const [r, c] = queue[head++]; for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const nr = r + dr, nc = c + dc; if (nr >= 0 && nr < image.length && nc >= 0 && nc < image[0].length && image[nr][nc] === old) { image[nr][nc] = color; // painting when we enqueue = marking as visited queue.push([nr, nc]); } } } return image;}console.log(floodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2)); // [ [ 2, 2, 2 ], [ 2, 2, 0 ], [ 2, 0, 1 ] ]It is also O(rows × cols). It uses a queue instead of the call stack, so a huge region cannot overflow it.
Both are equally good. Pick the recursion because it is shorter. (LeetCode 733.)
In a grid, 0 is an empty cell, 1 is a fresh orange, and 2 is a rotten orange. Every minute, a fresh orange next to a rotten one (up, down, left or right) becomes rotten. Return the number of minutes until no fresh orange is left. Return −1 if that can never happen.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
Repeat this: look at the whole grid and make every fresh orange next to a rotten one rot. Use a copy of the grid, so that one minute is exactly one step. Stop when nothing changes.
function orangesRotting(grid) { const rows = grid.length, cols = grid[0].length; let minutes = 0; while (true) { const next = grid.map((row) => [...row]); let changed = false; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] !== 1) continue; for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const nr = r + dr, nc = c + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 2) { next[r][c] = 2; changed = true; break; } } } } if (!changed) break; grid = next; minutes++; } return grid.some((row) => row.includes(1)) ? -1 : minutes;}console.log(orangesRotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]])); // 4console.log(orangesRotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]])); // -1console.log(orangesRotting([[0, 2]])); // 0Each minute looks at the whole grid again, and there can be up to rows × cols minutes. So the worst case is O((rows × cols)²).
Put every rotten orange in the queue. Then process the queue one level at a time. Each level is one minute, and every orange is touched once.
function orangesRotting(grid) { const rows = grid.length, cols = grid[0].length; const queue = []; let fresh = 0; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] === 2) queue.push([r, c]); else if (grid[r][c] === 1) fresh++; } } let head = 0, minutes = 0; while (head < queue.length && fresh > 0) { const levelEnd = queue.length; while (head < levelEnd) { const [r, c] = queue[head++]; for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const nr = r + dr, nc = c + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) { grid[nr][nc] = 2; fresh--; queue.push([nr, nc]); } } } minutes++; } return fresh === 0 ? minutes : -1;}console.log(orangesRotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]])); // 4console.log(orangesRotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]])); // -1console.log(orangesRotting([[0, 2]])); // 0It takes O(rows × cols) time and space. We stop when fresh reaches 0, so we do not count an extra empty minute at the end.
Use multi-source BFS. (LeetCode 994.)
There are n cities. isConnected[i][j] = 1 means that cities i and j are directly connected. The matrix is the same when you swap rows and columns (symmetric). A province is a group of cities connected directly or indirectly. Return the number of provinces.
Hint 1
isConnected[i][j] = 1 means there is an edge between i and j. A province is a connected component.Hint 2
Show all 2 solutions with explanations
For each city you have not visited, add one to the count. Then use DFS to go to every city j where isConnected[city][j] === 1.
function findCircleNum(isConnected) { const n = isConnected.length; const visited = new Array(n).fill(false); function visit(city) { visited[city] = true; for (let j = 0; j < n; j++) { if (isConnected[city][j] === 1 && !visited[j]) visit(j); } } let provinces = 0; for (let i = 0; i < n; i++) { if (!visited[i]) { provinces++; visit(i); } } return provinces;}console.log(findCircleNum([[1, 1, 0], [1, 1, 0], [0, 0, 1]])); // 2console.log(findCircleNum([[1, 0, 0], [0, 1, 0], [0, 0, 1]])); // 3It takes O(n²) time, because each city scans its whole matrix row once. The input is a matrix, so scanning a row is the way to find the neighbours. You do not need to build a list.
Use the same counting loop, with a queue to explore each province.
function findCircleNum(isConnected) { const n = isConnected.length; const visited = new Array(n).fill(false); let provinces = 0; for (let i = 0; i < n; i++) { if (visited[i]) continue; provinces++; visited[i] = true; const queue = [i]; let head = 0; while (head < queue.length) { const city = queue[head++]; for (let j = 0; j < n; j++) { if (isConnected[city][j] === 1 && !visited[j]) { visited[j] = true; queue.push(j); } } } } return provinces;}console.log(findCircleNum([[1, 1, 0], [1, 1, 0], [0, 0, 1]])); // 2console.log(findCircleNum([[1, 0, 0], [0, 1, 0], [0, 0, 1]])); // 3console.log(findCircleNum([[1, 0, 1], [0, 1, 0], [1, 0, 1]])); // 2It is also O(n²). Union-find (lesson 53) is a data structure that keeps items in groups and can quickly merge two groups. It solves the same problem, and it is the better tool when edges arrive one at a time.
Either traversal works. The key is to see that "groups of cities connected directly or indirectly" means connected components. (LeetCode 547.)
You get one node of a connected undirected graph. Each node has a val and a list of neighbors. Return a deep copy of the whole graph (a full copy that shares nothing with the original).
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
To clone a node: if it is already in the Map, return its copy. If not, create the copy and store it. Then clone each neighbour and attach it.
class Node { constructor(val) { this.val = val; this.neighbors = []; }}function cloneGraph(node) { const copies = new Map(); function clone(orig) { if (!orig) return null; if (copies.has(orig)) return copies.get(orig); const copy = new Node(orig.val); copies.set(orig, copy); // save it BEFORE the recursive calls, so cycles can find it for (const nb of orig.neighbors) copy.neighbors.push(clone(nb)); return copy; } return clone(node);}// helper functions for testing: nodes are numbered 1..n, adjList[i] holds the neighbour values of node i+1function fromAdjList(adj) { const nodes = adj.map((_, i) => new Node(i + 1)); adj.forEach((nbs, i) => { nodes[i].neighbors = nbs.map((v) => nodes[v - 1]); }); return nodes[0];}function toAdjList(start) { const seen = new Map(); const queue = [start]; seen.set(start, true); for (let h = 0; h < queue.length; h++) { for (const nb of queue[h].neighbors) if (!seen.has(nb)) { seen.set(nb, true); queue.push(nb); } } return queue.sort((a, b) => a.val - b.val).map((x) => x.neighbors.map((n) => n.val));}const original = fromAdjList([[2, 4], [1, 3], [2, 4], [1, 3]]);const copy = cloneGraph(original);console.log(toAdjList(copy)); // [ [ 2, 4 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3 ] ]console.log(copy !== original); // trueconsole.log(toAdjList(cloneGraph(fromAdjList([[]])))); // [ [] ]It takes O(V + E) time and space (the Map, plus recursion up to V levels deep). We save the copy before visiting its neighbours. That stops the recursion from running forever on cycles.
Copy the start and put it in the queue. For each original node you take out of the queue, make sure each neighbour has a copy. If a neighbour is new, create its copy and queue it. Then connect the copies.
class Node { constructor(val) { this.val = val; this.neighbors = []; }}function cloneGraph(node) { if (!node) return null; const copies = new Map([[node, new Node(node.val)]]); const queue = [node]; let head = 0; while (head < queue.length) { const orig = queue[head++]; for (const nb of orig.neighbors) { if (!copies.has(nb)) { copies.set(nb, new Node(nb.val)); queue.push(nb); } copies.get(orig).neighbors.push(copies.get(nb)); } } return copies.get(node);}function fromAdjList(adj) { const nodes = adj.map((_, i) => new Node(i + 1)); adj.forEach((nbs, i) => { nodes[i].neighbors = nbs.map((v) => nodes[v - 1]); }); return nodes[0];}function toAdjList(start) { const seen = new Set([start]); const queue = [start]; for (let h = 0; h < queue.length; h++) { for (const nb of queue[h].neighbors) if (!seen.has(nb)) { seen.add(nb); queue.push(nb); } } return queue.sort((a, b) => a.val - b.val).map((x) => x.neighbors.map((n) => n.val));}const original = fromAdjList([[2, 4], [1, 3], [2, 4], [1, 3]]);const copy = cloneGraph(original);console.log(toAdjList(copy)); // [ [ 2, 4 ], [ 1, 3 ], [ 2, 4 ], [ 1, 3 ] ]console.log(copy !== original); // trueIt is also O(V + E), without deep recursion. Every original neighbour list is walked once. Each step adds one entry to the copy's list, in the same order.
Both are fine. BFS avoids problems with deep recursion. Be ready to explain what the Map is for. (LeetCode 133.)
In a grid of 0s (water) and 1s (land), return the area (number of cells) of the biggest island. Return 0 if there is no island.
Hint 1
Hint 2
Show all 2 solutions with explanations
At each land cell you have not visited, run a DFS that returns 1 plus the area it can reach through its neighbours. Keep the largest result.
function maxAreaOfIsland(grid) { const rows = grid.length, cols = grid[0].length; function area(r, c) { if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== 1) return 0; grid[r][c] = 0; // visited return 1 + area(r + 1, c) + area(r - 1, c) + area(r, c + 1) + area(r, c - 1); } let best = 0; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) best = Math.max(best, area(r, c)); } return best;}console.log(maxAreaOfIsland([[0, 1, 1, 0], [0, 1, 0, 0], [1, 0, 0, 1]])); // 3console.log(maxAreaOfIsland([[0, 0, 0]])); // 0It takes O(rows × cols) time. Water cells return 0 right away, so it is fine to call area on every cell. Cells that were already sunk return 0 when we see them again.
Explore each island with a queue. The area of the island is the number of cells that were ever in the queue.
function maxAreaOfIsland(grid) { const rows = grid.length, cols = grid[0].length; const visited = Array.from({ length: rows }, () => new Array(cols).fill(false)); let best = 0; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] !== 1 || visited[r][c]) continue; visited[r][c] = true; const queue = [[r, c]]; let head = 0; while (head < queue.length) { const [cr, cc] = queue[head++]; for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const nr = cr + dr, nc = cc + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1 && !visited[nr][nc]) { visited[nr][nc] = true; queue.push([nr, nc]); } } } best = Math.max(best, queue.length); // every cell of the island went through the queue } } return best;}console.log(maxAreaOfIsland([[0, 1, 1, 0], [0, 1, 0, 0], [1, 0, 0, 1]])); // 3console.log(maxAreaOfIsland([[0, 0, 0]])); // 0It takes O(rows × cols) time and space. It does not change the input, and it has no recursion limit.
The recursive DFS is the shortest. (LeetCode 695.)
A grid of heights is an island. The Pacific Ocean touches its top and left edges, and the Atlantic Ocean touches its bottom and right edges. Rain on a cell flows to a neighbour whose height is the same or lower. Return every cell from which water can reach both oceans.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
For each cell, run a DFS that only goes to the same or lower heights. Record whether it touched a Pacific edge and an Atlantic edge.
function pacificAtlantic(heights) { const rows = heights.length, cols = heights[0].length; const result = []; for (let r0 = 0; r0 < rows; r0++) { for (let c0 = 0; c0 < cols; c0++) { const seen = new Set(); let pacific = false, atlantic = false; const stack = [[r0, c0]]; seen.add(r0 * cols + c0); while (stack.length) { const [r, c] = stack.pop(); if (r === 0 || c === 0) pacific = true; if (r === rows - 1 || c === cols - 1) atlantic = true; for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const nr = r + dr, nc = c + dc; if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue; if (heights[nr][nc] > heights[r][c] || seen.has(nr * cols + nc)) continue; // water cannot flow uphill seen.add(nr * cols + nc); stack.push([nr, nc]); } } if (pacific && atlantic) result.push([r0, c0]); } } return result;}console.log(pacificAtlantic([[1, 2, 2, 3, 5], [3, 2, 3, 4, 4], [2, 4, 5, 3, 1], [6, 7, 1, 4, 5], [5, 1, 1, 2, 4]])); // [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]console.log(pacificAtlantic([[1]])); // [[0,0]]It is correct, but each cell starts its own O(rows × cols) search. So the total is O((rows × cols)²).
Start from all cells along the Pacific edges. Move to neighbours that have the same height or a higher one (the opposite of how water flows). Mark everything you reach. Do the same for the Atlantic edges. The answer is the cells marked by both.
function pacificAtlantic(heights) { const rows = heights.length, cols = heights[0].length; function reach(starts) { const seen = Array.from({ length: rows }, () => new Array(cols).fill(false)); const queue = []; for (const [r, c] of starts) { seen[r][c] = true; queue.push([r, c]); } let head = 0; while (head < queue.length) { const [r, c] = queue[head++]; for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const nr = r + dr, nc = c + dc; if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || seen[nr][nc]) continue; if (heights[nr][nc] < heights[r][c]) continue; // water could not flow from there down to here seen[nr][nc] = true; queue.push([nr, nc]); } } return seen; } const pacificStarts = [], atlanticStarts = []; for (let r = 0; r < rows; r++) { pacificStarts.push([r, 0]); atlanticStarts.push([r, cols - 1]); } for (let c = 0; c < cols; c++) { pacificStarts.push([0, c]); atlanticStarts.push([rows - 1, c]); } const pac = reach(pacificStarts), atl = reach(atlanticStarts); const result = []; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) if (pac[r][c] && atl[r][c]) result.push([r, c]); } return result;}console.log(pacificAtlantic([[1, 2, 2, 3, 5], [3, 2, 3, 4, 4], [2, 4, 5, 3, 1], [6, 7, 1, 4, 5], [5, 1, 1, 2, 4]])); // [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]console.log(pacificAtlantic([[1]])); // [[0,0]]There are two multi-source searches, each O(rows × cols), plus one pass to combine them. We run the flow backwards from the ocean. This turns "many cells each search for the sea" into "the sea searches once for all cells". Walking uphill is allowed when the next height is the same as or greater than the current one.
Use the reverse search. The same "start from the destination" trick appears in many grid problems. (LeetCode 417.)
Make it stick
- Write BFS from memory with a queue, a head number and a visited set.
- Explain why you mark a vertex as visited when it is enqueued.
- Write DFS two ways: with recursion, and with your own stack.
- Say when BFS is the right tool, and when either one works.
- Explain how multi-source BFS counts the minutes in rotting oranges.
- Explain what the Map does when you clone a graph.
Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.
What's next
So far, we treated edges as two-way, or we ignored their direction. Lesson 51 uses directed edges to put things in order. Topological sort lists tasks so that every prerequisite comes first. It can also detect cycles.
Practise on LeetCode
Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.
Published by Jainik · Last updated · How these lessons are made
Keep learning
Part of the study guide
Related series