AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

Graph coding problems

Nodes and edges: build the adjacency list, then traverse it.

New to graph? Read the Graph Data Structure tutorial first.

107 problems · 5 easy · 60 medium · 42 hard · judged by hidden tests in 13 languages

107problems

5 easy

60 medium

42 hard

Sign in to tick off what you solve.

Study plan: 14 problems · about 8 h 10 min

Start the study plan

Next up: Find if Path Exists in Graph

How it works

Graph, step by step

Building an adjacency list from an edge list, one edge at a time

n = 5, edges = [[0,1], [0,2], [1,2], [1,3], [2,4], [3,4]]

edges0–10–21–21–32–43–401234adj[0][ ]adj[1][ ]adj[2][ ]adj[3][ ]adj[4][ ]entries stored: 0

An edge list names the joined pairs, but finding one node's neighbours would mean scanning all 6 edges. An adjacency list gives each of the 5 nodes its own list instead, filled in a single pass over the edges.

0:01 / 0:31Step 1 of 8
Transcript · 8 steps

Study plan

Learn graph in 8 days

14 of the 107 Graph problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 93 in the full list below are practice at your own pace. Then move on to Breadth-First Search.

  1. Day 1

    about 1 h 15 min

    Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

  2. Day 2

    about 55 min

    Medium problems: the same pattern with one twist each. Name the twist before you code.

  3. Day 3

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  4. Day 4

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  5. Day 5

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  6. Day 6

    about 50 min

    Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

  7. Day 7

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

  8. Day 8

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

    Next topic: Breadth-First Search

Graph Coding Problems: 107 Questions with Solutions

107 graph coding problems — 5 easy · 60 medium · 42 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.

  • Problems: 107
  • By difficulty: 5 easy · 60 medium · 42 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

Nodes and edges: build the adjacency list, then traverse it. These problems cover the representation choices (list, matrix, edge list), reachability and components, cycle detection in directed and undirected graphs, and the traversals that everything else is built on. Shortest paths and topological order have their own pages.

New to graph? Read the Graph Data Structure tutorial first.

How graph works, step by step

edges0–10–21–21–32–43–401234adj[0]12adj[1]023adj[2]014adj[3]14adj[4]23degree: 0→2 1→3 2→3 3→2 4→2neighbours(1) = adj[1] = [0, 2, 3]
Building an adjacency list from an edge list, one edge at a time. Example: n = 5, edges = [[0,1], [0,2], [1,2], [1,3], [2,4], [3,4]]
  1. An edge list names the joined pairs, but finding one node's neighbours would mean scanning all 6 edges. An adjacency list gives each of the 5 nodes its own list instead, filled in a single pass over the edges.
  2. Read edge 0–1: append 1 to adj[0], now [1], and 0 to adj[1], now [0]. The graph is undirected, so every edge is written twice, once from each end.
  3. Read edge 0–2: append 2 to adj[0], now [1, 2], and 0 to adj[2], now [0]. 2 had no neighbours until now; appending to the end of a list is O(1), however long it is.
  4. Read edge 1–2: append 2 to adj[1], now [0, 2], and 1 to adj[2], now [0, 1]. 1 and 2 were already linked through 1–0–2, so this edge closes a cycle; the lists still only record direct neighbours.
  5. Read edge 1–3: append 3 to adj[1], now [0, 2, 3], and 1 to adj[3], now [1]. A list's length is its node's degree: 1 now has 3 neighbours, while 3 gets its first.
  6. Read edge 2–4: append 4 to adj[2], now [0, 1, 4], and 2 to adj[4], now [2]. Only the two lists the edge names are touched, which is why the whole pass costs O(V + E).
  7. Read edge 3–4: append 4 to adj[3], now [1, 4], and 3 to adj[4], now [2, 3]. This closes a second cycle, 3–1–2–4–3, and is stored exactly like any other edge.
  8. All 6 edges are in, each stored twice, so the lists hold 12 entries: the degrees add up to 2E. Building took O(V + E), and now 1's neighbours are one lookup, adj[1] = [0, 2, 3], in O(degree) instead of an O(E) scan.

Graph study plan

14 of the 107 Graph problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 93 in the full list below are practice at your own pace. Then move on to Breadth-First Search.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 5

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 6

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Day 8

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Next topic: Breadth-First Search

Graph: the essentials

When to reach for it

Anything with pairwise relationships — roads between cities, prerequisites, friendships, trust, network links — even when the word "graph" never appears. Inputs usually arrive as an edge list ([[u, v], …]) or an adjacency matrix. Before writing anything, settle three things: are edges directed, do they carry weights, and are nodes numbered from 0 or from 1?

The pattern

Convert to an adjacency list, then choose the traversal: Breadth-First Search for the fewest edges, depth-first search for reachability and structure, union-find when edges arrive one at a time and only connectivity matters. Some questions need no traversal at all: in Find the Town Judge, the judge is the node with in-degree n − 1 and out-degree 0.

def build(n, edges, directed=False):
    adj = [[] for _ in range(n)]    # nodes 0..n-1
    for u, v in edges:
        adj[u].append(v)
        if not directed:
            adj[v].append(u)
    return adj

Cost

An adjacency list takes O(V + E) space and a full traversal O(V + E) time. An adjacency matrix takes O(V²) space and makes every traversal O(V²); it pays off only for dense graphs or constant-time edge checks.

Common mistakes

  • Adding an undirected edge in one direction only.
  • Missing isolated nodes: loop over range(n), not over the nodes that appear in edges, when counting components.
  • Undirected cycle detection that treats the edge back to the parent as a cycle.
  • Traversing from node 0 and assuming that reaches the whole graph.

Start with

All graph problems

Easy (5)

Medium (60)

Hard (42)

Companies that ask graph problems

Next topic: Breadth-First Search