Skip to main content

Pattern · 25 problems

Graph Interview Problems

Graph problems start with the adjacency list. Once it exists, I ask whether the job is traversal, ordering or grouping.

Get the link for your laptop

Free: write the code and run it, no sign-up.

When I reach for it

  • The input is edges, prerequisites or connections.
  • You need cycles, an ordering or connected groups.
  • The nodes are not numbered nicely, or the graph is never handed to you.

Problems, easiest first

0 easy · 19 medium · 6 hard. Open one to read it, then write it in the free editor.

  1. Clone GraphmediumBFS & DFS
  2. Number of Connected Components in an Undirected GraphmediumBFS & DFS
  3. Course SchedulemediumHeapsBFS & DFS
  4. Graph Valid TreemediumBFS & DFS
  5. Longest Consecutive SequencemediumArrays & Hashing
  6. Number of IslandsmediumBFS & DFSArrays & Hashing
  7. Pacific Atlantic Water FlowmediumBFS & DFSArrays & Hashing
  8. Cheapest Flights Within K StopsmediumHeapsDynamic Programming
  9. Course Schedule IImediumBFS & DFS
  10. Max Area of IslandmediumBFS & DFSArrays & Hashing
  11. Min Cost to Connect All PointsmediumGreedyHeaps
  12. Network Delay TimemediumHeapsBFS & DFS
  13. Redundant ConnectionmediumBFS & DFSArrays & Hashing
  14. Rotting OrangesmediumBFS & DFSArrays & Hashing
  15. Surrounded RegionsmediumBFS & DFSArrays & Hashing
  16. Walls and GatesmediumBFS & DFSArrays & Hashing
  17. Accounts MergemediumStringsBFS & DFS
  18. Minimum Height TreesmediumBFS & DFS
  19. Web CrawlermediumDesignStrings
  20. Alien DictionaryhardStringsBFS & DFS
  21. Longest Increasing Path in a MatrixhardDynamic ProgrammingBFS & DFS
  22. Reconstruct ItineraryhardBacktrackingBFS & DFS
  23. Swim in Rising WaterhardBinary SearchHeaps
  24. Word LadderhardStringsBFS & DFS
  25. Design Excel Sum FormulahardDesignStrings

The idea

Build the graph first. Then say which of three jobs this is: walk it, order it, or group its pieces. Each job has a standard tool.

Prerequisites mean a directed graph and a question about cycles or order. Connections mean groups, and a traversal or union-find counts them.

from collections import defaultdict

graph = defaultdict(list)
for a, b in edges:
    graph[a].append(b)
    graph[b].append(a)    # undirected: add the reverse edge too
Build an undirected graph from an edge list. Drop the second line when the edges are one-way. Python shown; the idea carries to every language in the editor.

Where it goes wrong

  • Missing disconnected pieces. Loop over every node, not only node 0.
  • Treating a directed graph as undirected.
  • Revisiting nodes because there is no visited set.

Say this before you type. Say whether the edges are directed, and which of the three jobs you are doing.

Where Coco comes in

Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.

Questions people ask

How do I detect a cycle?
In an undirected graph, reaching a visited node that is not your parent means a cycle. In a directed graph, track the nodes on your current path.
What is a topological order?
An order where every prerequisite comes before what needs it. It exists only when the graph has no cycle.

Meet these next

Fin and Coco are characters, not people. strongyes.io is independent. Leo builds it with AI agents.