Part 13 · Lesson 49 · read
What a Graph Is
Vertices, edges and the adjacency list (each vertex's list of neighbours).
On this page
What is a graph?
A graph is a set of things and the connections between them. The things are called vertices (one thing is a vertex; you will also hear the word nodes). Each connection is an edge. Here are some examples. Cities are vertices and the roads between them are edges. People are vertices and friendships are edges. Web pages are vertices and links are edges. Courses are vertices and prerequisites (courses you must finish first) are edges. All of these are graphs.
You already know two special graphs. A linked list is a graph where each vertex has one edge going out. A tree is a connected graph with no cycles (no way to walk in a loop). A general graph has no such limits: any vertex can connect to any other. That freedom is why graphs describe so many real problems. It is also why walking through them needs some care, because you can reach the same vertex twice.
We usually write V for the number of vertices and E for the number of edges. We give running times using these letters, for example O(V + E). (Big-O notation, such as O(V + E), is a way to say how the work grows when the input grows.)
Directed, undirected, weighted
- Undirected: an edge is a two-way street. If A - B exists, you can go from A to B and from B to A. Friendship on most social networks works like this.
- Directed: an edge has a direction, drawn as an arrow from A to B. You can go from A to B, but not back (unless there is also an edge from B to A). Examples: "follows" on a social network, or "course A must be finished before course B".
- Weighted: each edge has a number on it, called its weight. It can be a distance or a cost. Both directed and undirected graphs can be weighted.
Degree, path, cycle, component
- The degree of a vertex is the number of edges that touch it. In a directed graph we split it in two: in-degree (edges coming in) and out-degree (edges going out).
- A path is a list of vertices where each pair next to each other is joined by an edge. If there is a path from A to B, we say B is reachable from A.
- A cycle is a path that ends where it started, without using the same edge twice. For example, A to B to C and back to A. A graph with no cycles is called acyclic.
- A connected component (in an undirected graph) is a group of vertices that can all reach each other, with no connection to the rest of the graph. A graph in one piece is called connected. A graph with several pieces has several components.
Two ways to store a graph
An adjacency list stores, for every vertex, the list of its neighbours (adjacent means "directly connected"). In JavaScript this is a Map from each vertex to an array. If the vertices are numbered 0 to n-1, it can also be just an array of arrays. An adjacency matrix is a table with V rows and V columns. Cell [a][b] tells you whether the edge from a to b exists. A Map is a JavaScript object that stores key-value pairs and finds a value by its key quickly. A Set is a JavaScript collection that keeps each value only once and can check quickly whether a value is inside.
| Operation | Adjacency list | Adjacency matrix |
|---|---|---|
| Memory | O(V + E) | O(V²) |
| Is there an edge a - b? | O(degree of a): scan the list | O(1): read matrix[a][b] |
| List the neighbours of a | O(degree of a): just read the list | O(V): scan a whole row |
| Add an edge | O(1): push | O(1): set a cell |
| Good for | sparse graphs (few edges), which is the usual case | dense graphs (many edges), or many questions like 'is there an edge?' |
A graph is sparse when it has few edges (E is much smaller than V²) and dense when it has many (E is close to V²). Most interview graphs are sparse. So the adjacency list is the default choice. Use the matrix when V is small, or when the input already comes as a matrix.
// matrix[a][b] is 1 when there is an edge a - b.function buildMatrix(n, edges) { const matrix = Array.from({ length: n }, () => new Array(n).fill(0)); for (const [a, b] of edges) { matrix[a][b] = 1; matrix[b][a] = 1; // undirected: the matrix is symmetric (the same when flipped over its diagonal) } return matrix;}const m = buildMatrix(5, [[0, 1], [0, 2], [1, 2], [3, 4]]);console.log(m[0]); // [ 0, 1, 1, 0, 0 ]console.log(m[1][2]); // 1 (edge test in O(1))console.log(m[0][3]); // 0For a weighted graph, put the weight next to each neighbour:
// Weighted: store the weight next to each neighbour.const weighted = new Map([ ["A", [["B", 4], ["C", 1]]], ["B", [["D", 2]]], ["C", [["B", 2], ["D", 7]]], ["D", []],]);for (const [city, roads] of weighted) { console.log(city, "->", roads.map(([to, w]) => to + "(" + w + ")").join(" "));}// A -> B(4) C(1)// B -> D(2)// C -> B(2) D(7)// D ->Building from an edge list
Interview problems almost always give the graph as an edge list. This is n plus pairs such as [[0, 1], [0, 2], [1, 2], [3, 4]]. Your first job is to turn it into an adjacency list. First, make an empty list for every vertex, so that vertices with no edges still exist. Then add each edge. For an undirected graph, add the edge in both directions. For a directed graph, add it in one direction only.
// n vertices numbered 0 .. n-1, edges given as [a, b] pairs.function buildGraph(n, edges, directed = false) { const graph = new Map(); for (let v = 0; v < n; v++) graph.set(v, []); // every vertex starts with no neighbours for (const [a, b] of edges) { graph.get(a).push(b); // a -> b if (!directed) graph.get(b).push(a); // undirected: also b -> a } return graph;}const edges = [[0, 1], [0, 2], [1, 2], [3, 4]];console.log(buildGraph(5, edges)); // Map(5) { 0 => [ 1, 2 ], 1 => [ 0, 2 ], 2 => [ 0, 1 ], 3 => [ 4 ], 4 => [ 3 ] }console.log(buildGraph(5, edges, true)); // Map(5) { 0 => [ 1, 2 ], 1 => [ 2 ], 2 => [], 3 => [ 4 ], 4 => [] }When the vertices are exactly 0 to n-1, an array of arrays is shorter and faster:
// The same thing with a plain array of arrays (good when vertices are 0 .. n-1).function buildGraphArray(n, edges) { const graph = Array.from({ length: n }, () => []); // NOT new Array(n).fill([]) - that uses one shared array for (const [a, b] of edges) { graph[a].push(b); graph[b].push(a); } return graph;}console.log(buildGraphArray(5, [[0, 1], [0, 2], [1, 2], [3, 4]])); // [ [ 1, 2 ], [ 0, 2 ], [ 0, 1 ], [ 4 ], [ 3 ] ]new Array(n).fill([]) puts the same array in every slot. So if you push to one neighbour list, you change all of them. Always build with Array.from({ length: n }, () => []).Traced: edge list to adjacency list
The Map will hold one entry for each vertex: the vertex, and the list of its neighbours.
▶const graph = new Map();2for (let v = 0; v < n; v++) graph.set(v, []);3for (const [a, b] of edges) {4 graph.get(a).push(b);5 graph.get(b).push(a);6}| n | 5 |
| edges | [[0, 1], [0, 2], [1, 2], [3, 4]] |
| graph | Map(0) {} |
Building takes O(V + E) time and space. It needs one pass over the vertices and one pass over the edges. Each undirected edge is stored twice, so the lists hold 2E entries in total. The degrees of all vertices add up to 2E.
Counting degrees
You do not need a graph structure to count degrees. One pass over the edge list is enough. Some problems, such as finding a "celebrity" (someone everyone knows) or the centre of a star graph, are solved just by counting degrees.
function degrees(n, edges) { const deg = new Array(n).fill(0); for (const [a, b] of edges) { deg[a]++; deg[b]++; } // undirected: each edge touches two vertices return deg;}console.log(degrees(5, [[0, 1], [0, 2], [1, 2], [3, 4]])); // [ 2, 2, 2, 1, 1 ]function inOutDegrees(n, edges) { const inDeg = new Array(n).fill(0); const outDeg = new Array(n).fill(0); for (const [from, to] of edges) { outDeg[from]++; inDeg[to]++; } return { inDeg, outDeg };}console.log(inOutDegrees(3, [[0, 1], [0, 2], [1, 2]])); // { inDeg: [ 0, 1, 2 ], outDeg: [ 2, 1, 0 ] }A first walk through a graph
Suppose you ask, "can I get from A to B?" You walk outwards from A. Visit a vertex, then visit each of its neighbours. A graph can have cycles, so you also keep a visited set (a list of places you have already been). Without it, you would walk around a triangle forever. This is a first look at depth-first search (DFS, which means going as deep as you can before turning back). Lesson 50 explains it fully, together with breadth-first search.
// Is there a path from start to target? Walk outwards and remember where you have been.function hasPath(graph, start, target) { const visited = new Set(); function visit(v) { if (v === target) return true; visited.add(v); // without this, a cycle would make us loop forever for (const next of graph.get(v)) { if (!visited.has(next) && visit(next)) return true; } return false; } return visit(start);}const g = buildGraph(5, [[0, 1], [0, 2], [1, 2], [3, 4]]);console.log(hasPath(g, 0, 2)); // trueconsole.log(hasPath(g, 0, 4)); // false (4 is in another component)function buildGraph(n, edges) { const graph = new Map(); for (let v = 0; v < n; v++) graph.set(v, []); for (const [a, b] of edges) { graph.get(a).push(b); graph.get(b).push(a); } return graph;}If you start a new walk from each vertex you have not seen yet, you can count the connected components:
// Count connected components: start a walk from every vertex we have not seen yet.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 seen = new Array(n).fill(false); function visit(v) { seen[v] = true; for (const next of graph[v]) if (!seen[next]) visit(next); } let count = 0; for (let v = 0; v < n; v++) { if (!seen[v]) { count++; visit(v); } // a new start means a new component } return count;}console.log(countComponents(5, [[0, 1], [0, 2], [1, 2], [3, 4]])); // 2console.log(countComponents(4, [])); // 4Both take O(V + E) time. Every vertex is visited once, and every edge is looked at at most twice. The recursion (a function that calls itself) can go as deep as V levels. That is fine for interview sizes. Lesson 50 shows another way that uses a stack you manage yourself.
Grids are graphs too
A 2-D grid (a maze, a map of land and water, or a game board) is a graph that you never have to build. Each cell (r, c) is a vertex. Its neighbours are the cells above, below, left and right, if they exist. Keep the four direction steps in an array, and check the grid edges before you use a neighbour. If a problem says "8-directional", add the four diagonal steps to the array.
// A grid cell (r, c) is a vertex. Its neighbours are the cells up, down, left and right.const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];function neighbours(grid, r, c) { const out = []; for (const [dr, dc] of DIRS) { const nr = r + dr, nc = c + dc; if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length) out.push([nr, nc]); // bounds check } return out;}const grid = [ [1, 1, 0], [0, 1, 0], [1, 0, 1],];console.log(neighbours(grid, 0, 0)); // [ [ 1, 0 ], [ 0, 1 ] ] (a corner has 2 neighbours)console.log(neighbours(grid, 1, 1)); // [ [ 0, 1 ], [ 2, 1 ], [ 1, 0 ], [ 1, 2 ] ] (the middle has 4)r * cols + c numbers, a grid of true/false values, or you can overwrite the cell.Practice questions
First ask: what are the vertices, and what are the edges? When you can answer that, the rest is usually counting degrees or a short walk.
A star graph has one centre vertex that is connected to every other vertex, and nothing else. You get its edges (the vertices are numbered 1 to n). Return the centre.
Hint 1
Hint 2
Show all 2 solutions with explanations
Count how many edges touch each vertex. The centre is in all of the edges, so its degree equals the number of edges.
function findCenter(edges) { const degree = new Map(); for (const [a, b] of edges) { degree.set(a, (degree.get(a) ?? 0) + 1); degree.set(b, (degree.get(b) ?? 0) + 1); } for (const [v, d] of degree) if (d === edges.length) return v;}console.log(findCenter([[1, 2], [2, 3], [4, 2]])); // 2console.log(findCenter([[1, 2], [5, 1], [1, 3], [1, 4]])); // 1It takes O(E) time and O(V) space. This is the general pattern for "find the vertex with a given degree".
The centre is in every edge, so it is the one vertex that the first two edges share.
function findCenter(edges) { const [a, b] = edges[0]; const [c, d] = edges[1]; return a === c || a === d ? a : b;}console.log(findCenter([[1, 2], [2, 3], [4, 2]])); // 2console.log(findCenter([[1, 2], [5, 1], [1, 3], [1, 4]])); // 1It takes O(1) time. The two edges are different, so they share exactly one vertex, and that vertex must be the centre. If a is in the second edge, it is the shared vertex. If not, b must be.
Use the first two edges for the shortest answer. But also know the degree count, because it works whenever you need a vertex with a certain degree. (LeetCode 1791.)
A town has n people, numbered 1 to n. There may be a secret judge. The judge trusts nobody, and everybody else trusts the judge. Each [a, b] in trust means that a trusts b. Return the judge's number, or −1 if there is no judge.
Hint 1
Hint 2
Show all 2 solutions with explanations
Store who trusts whom in an n × n matrix. For each person, check that they trust nobody and that everyone else trusts them.
function findJudge(n, trust) { const m = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(false)); for (const [a, b] of trust) m[a][b] = true; for (let p = 1; p <= n; p++) { let ok = true; for (let q = 1; q <= n && ok; q++) { if (q === p) continue; if (m[p][q] || !m[q][p]) ok = false; // p trusts someone, or someone does not trust p } if (ok) return p; } return -1;}console.log(findJudge(2, [[1, 2]])); // 2console.log(findJudge(3, [[1, 3], [2, 3]])); // 3console.log(findJudge(3, [[1, 3], [2, 3], [3, 1]])); // -1It takes O(n² + E) time and O(n²) space. It is correct, but the matrix is much more than the problem needs.
Give each person a score: +1 for every person who trusts them, and −1 for every person they trust. Only the judge can reach n − 1.
function findJudge(n, trust) { const score = new Array(n + 1).fill(0); for (const [a, b] of trust) { score[a]--; // a trusts someone, so a can never be the judge score[b]++; // b is trusted by someone } for (let p = 1; p <= n; p++) if (score[p] === n - 1) return p; return -1;}console.log(findJudge(2, [[1, 2]])); // 2console.log(findJudge(3, [[1, 3], [2, 3]])); // 3console.log(findJudge(3, [[1, 3], [2, 3], [3, 1]])); // -1console.log(findJudge(1, [])); // 1The score is in-degree minus out-degree. The most in-degree anyone can have is n − 1. To reach a score of n − 1, the out-degree must be 0. The pairs are all different, so no repeated edge can raise the score. It takes O(n + E) time and O(n) space. For n = 1, the one person has score 0 = n − 1, so the answer is 1.
Use the score array: one pass and one array. (LeetCode 997.)
You get an undirected graph with n vertices numbered 0 to n − 1, as an edge list. Return whether there is a path from source to destination.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
Start with only the source marked as reachable. Go over the edge list again and again. Whenever an edge has one reachable end, mark the other end as reachable too. Stop when a full pass changes nothing.
function validPath(n, edges, source, destination) { const reach = new Array(n).fill(false); reach[source] = true; let changed = true; while (changed) { changed = false; for (const [a, b] of edges) { if (reach[a] && !reach[b]) { reach[b] = true; changed = true; } else if (reach[b] && !reach[a]) { reach[a] = true; changed = true; } } } return reach[destination];}console.log(validPath(3, [[0, 1], [1, 2], [2, 0]], 0, 2)); // trueconsole.log(validPath(6, [[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]], 0, 5)); // falseYou do not need a graph structure. But each pass costs O(E), and there can be up to V passes. So the worst case is O(V · E), which is too slow for big inputs.
Build the adjacency list. Then walk from the source with a visited array. Return true as soon as you reach the destination.
function validPath(n, edges, source, destination) { const graph = Array.from({ length: n }, () => []); for (const [a, b] of edges) { graph[a].push(b); graph[b].push(a); } const seen = new Array(n).fill(false); const stack = [source]; // our own stack avoids deep recursion seen[source] = true; while (stack.length) { const v = stack.pop(); if (v === destination) return true; for (const next of graph[v]) { if (!seen[next]) { seen[next] = true; stack.push(next); } } } return false;}console.log(validPath(3, [[0, 1], [1, 2], [2, 0]], 0, 2)); // trueconsole.log(validPath(6, [[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]], 0, 5)); // falseconsole.log(validPath(1, [], 0, 0)); // trueIt takes O(V + E) time and space. Each vertex is pushed at most once, because it is marked as seen when it is pushed. Lesson 50 explains the stack and queue versions. Later, union-find (lesson 53) can answer many such questions on one graph.
Use the walk over an adjacency list. BFS (breadth-first search) or recursive DFS (depth-first search) both work. (LeetCode 1971.)
A grid has 1 for land and 0 for water. It has exactly one island (land cells connected up, down, left or right) and no lakes inside it. Cells outside the grid count as water. Return the perimeter (the length of the outer edge) of the island.
Hint 1
Hint 2
Show all 2 solutions with explanations
For each land cell, count the sides where the cell next to it is outside the grid or is water.
function islandPerimeter(grid) { const rows = grid.length, cols = grid[0].length; const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]; let perimeter = 0; 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 dirs) { const nr = r + dr, nc = c + dc; if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] === 0) perimeter++; } } } return perimeter;}console.log(islandPerimeter([[0, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0], [1, 1, 0, 0]])); // 16console.log(islandPerimeter([[1]])); // 4console.log(islandPerimeter([[1, 0]])); // 4It takes O(rows × cols) time. You do not need to walk the island, because there is exactly one island. You only look at the neighbours of each cell.
Every land cell adds 4 sides. Each pair of land cells next to each other hides 2 sides (one from each). Count the land cells. Count the pairs by looking only right and down, so no pair is counted twice.
function islandPerimeter(grid) { let land = 0, pairs = 0; for (let r = 0; r < grid.length; r++) { for (let c = 0; c < grid[0].length; c++) { if (grid[r][c] !== 1) continue; land++; if (r + 1 < grid.length && grid[r + 1][c] === 1) pairs++; if (c + 1 < grid[0].length && grid[r][c + 1] === 1) pairs++; } } return 4 * land - 2 * pairs;}console.log(islandPerimeter([[0, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0], [1, 1, 0, 0]])); // 16console.log(islandPerimeter([[1]])); // 4It is also O(rows × cols), with half the neighbour checks. In the first example, 7 land cells and 6 pairs give 28 − 12 = 16.
Either one is fine. The second one shows the "count vertices and edges" view of a grid graph. (LeetCode 463.)
There are n cities and a list of two-way roads. The network rank of two different cities is the total number of roads connected to either of them. A road that joins both cities counts once. Return the largest network rank over all pairs of cities.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
For each pair of cities, go through the road list. Count the roads that touch at least one of the two cities.
function maximalNetworkRank(n, roads) { let best = 0; for (let a = 0; a < n; a++) { for (let b = a + 1; b < n; b++) { let count = 0; for (const [x, y] of roads) if (x === a || x === b || y === a || y === b) count++; best = Math.max(best, count); } } return best;}console.log(maximalNetworkRank(4, [[0, 1], [0, 3], [1, 2], [1, 3]])); // 4It takes O(n² · E) time. It is clear but slow, because it reads every road again for every pair.
Work out the degree of each city, and a matrix of direct roads. The rank of a pair is deg[a] + deg[b], minus 1 if the two cities are directly connected.
function maximalNetworkRank(n, roads) { const deg = new Array(n).fill(0); const linked = Array.from({ length: n }, () => new Array(n).fill(false)); for (const [a, b] of roads) { deg[a]++; deg[b]++; linked[a][b] = linked[b][a] = true; } let best = 0; for (let a = 0; a < n; a++) { for (let b = a + 1; b < n; b++) { best = Math.max(best, deg[a] + deg[b] - (linked[a][b] ? 1 : 0)); } } return best;}console.log(maximalNetworkRank(4, [[0, 1], [0, 3], [1, 2], [1, 3]])); // 4console.log(maximalNetworkRank(5, [[0, 1], [0, 3], [1, 2], [1, 3], [2, 3], [2, 4]])); // 5console.log(maximalNetworkRank(8, [[0, 1], [1, 2], [2, 3], [2, 4], [5, 6], [5, 7]])); // 5It takes O(n² + E) time and O(n²) space. This is exactly where the matrix helps, because it answers "are they directly connected?" in O(1) time.
Use the degrees and the matrix. (LeetCode 1615.)
An array of n different values was lost. But you get every pair of values that were next to each other in it. The pairs come in any order, and each pair can be written either way round. Rebuild the array (either direction is accepted).
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
Try every value as the start. Look at the last value you placed. Scan the pair list for an unused pair that contains it, and add the other value. If the result has n values, the start was an end.
function restoreArray(pairs) { const n = pairs.length + 1; const values = [...new Set(pairs.flat())]; for (const start of values) { const used = new Array(pairs.length).fill(false); const out = [start]; let extended = true; while (extended) { extended = false; const last = out[out.length - 1]; for (let i = 0; i < pairs.length; i++) { if (used[i]) continue; if (pairs[i][0] === last) { out.push(pairs[i][1]); used[i] = true; extended = true; break; } if (pairs[i][1] === last) { out.push(pairs[i][0]); used[i] = true; extended = true; break; } } } if (out.length === n) return out; }}console.log(restoreArray([[2, 1], [3, 4], [3, 2]])); // [ 1, 2, 3, 4 ]console.log(restoreArray([[4, -2], [1, 4], [-3, 1]])); // [ -2, 4, 1, -3 ]If you start in the middle, you can only grow in one direction, so you end up with too few values. Only an end gives all n values. Each try takes O(n²) time, and there can be n tries, so the total is O(n³). It is fine as a first idea, but far too slow for a large n.
Build a Map from each value to its neighbours. Pick a value with exactly one neighbour as the start. Then keep moving to the neighbour that is not the previous value.
function restoreArray(pairs) { const graph = new Map(); for (const [a, b] of pairs) { if (!graph.has(a)) graph.set(a, []); if (!graph.has(b)) graph.set(b, []); graph.get(a).push(b); graph.get(b).push(a); } let start; for (const [v, nbrs] of graph) if (nbrs.length === 1) { start = v; break; } const out = [start]; let prev = null, cur = start; while (out.length < graph.size) { const next = graph.get(cur).find((x) => x !== prev); // the neighbour we did not just come from out.push(next); prev = cur; cur = next; } return out;}console.log(restoreArray([[2, 1], [3, 4], [3, 2]])); // [ 1, 2, 3, 4 ]console.log(restoreArray([[4, -2], [1, 4], [-3, 1]])); // [ -2, 4, 1, -3 ]It takes O(n) time and space. All the values are different, so "the neighbour that is not prev" is always clear.
Use the adjacency list. The key step is to see that this is a path graph and to start at a vertex with degree 1. (LeetCode 1743.)
There are n teams in a tournament. In an n × n matrix, grid[i][j] = 1 means that team i is stronger than team j. For any two different teams, exactly one of grid[i][j] and grid[j][i] is 1. There are no cycles of strength (no loop where A beats B, B beats C and C beats A). Return the champion: the team that no other team is stronger than.
Hint 1
grid[i][j] = 1 as a directed edge from i to j ("i is stronger than j"). The champion is a vertex that no edge points to.Hint 2
Hint 3
Show all 2 solutions with explanations
A team is the champion when no team is stronger than it. This means its column has no 1.
function findChampion(grid) { const n = grid.length; for (let team = 0; team < n; team++) { let beaten = false; for (let other = 0; other < n; other++) { if (grid[other][team] === 1) { beaten = true; break; } // an edge other -> team } if (!beaten) return team; } return -1;}console.log(findChampion([[0, 1], [0, 0]])); // 0console.log(findChampion([[0, 0, 1], [1, 0, 1], [0, 0, 0]])); // 1It takes O(n²) time. This is "find the vertex with in-degree 0" on an adjacency matrix.
Start with team 0 as the possible champion. For each next team i: if i beats the possible champion, that team is out and i takes over. Otherwise the possible champion beats i (one of them must win), so i is out.
function findChampion(grid) { let champ = 0; for (let i = 1; i < grid.length; i++) { if (grid[i][champ] === 1) champ = i; // i is stronger, so the old possible champion cannot be the champion } return champ;}console.log(findChampion([[0, 1], [0, 0]])); // 0console.log(findChampion([[0, 0, 1], [1, 0, 1], [0, 0, 0]])); // 1Only O(n) cells are read. Every comparison rules out exactly one team. The real champion is never ruled out, because nobody beats it. This depends on the promise that every pair has a winner.
The scan that rules out teams is the cleverest. The column check is the safest one to explain first. (LeetCode 2923.)
Make it stick
- Explain vertex, edge, directed, undirected and weighted in your own words.
- Say when you would choose an adjacency matrix instead of an adjacency list.
- Write the loop that turns an edge list into an adjacency list, and explain why an undirected edge is pushed twice.
- Explain what the visited set prevents.
- List the steps to find the neighbours of a grid cell, including the check for the grid edges.
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
Lesson 50 turns the walk you just saw into the two main graph algorithms. Breadth-first search (BFS) visits the closest vertices first. It uses a queue, which is a list where the first item added is the first item removed.Depth-first search uses a stack, which is a list where the last item added is the first item removed, or it uses recursion. You will use them on islands, flood fill, rotting oranges and cloning a graph.
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