7 patterns · 34 problems
Graphs
Model things as nodes and edges, then traverse: components, shortest paths, cycles, ordering, and coloring.
Each pattern below starts with when to reach for it and the clue in the prompt that gives it away. Then it runs on real problems: pick one to watch the technique step by step, open its full solution, or practise it on an original problem with graded tests.
01Pattern
Finding Connected Components
Group nodes that can reach each other.
O(V + E)When to reach for it
- You're given a graph, and you need to identify distinct subgraphs where all vertices are connected to each other by paths.
Spot it in the prompt
Look for problems where you need to group nodes based on their connectivity, often involving DFS or BFS traversal.
Number of Islands
How to solve it
Scan the grid and launch DFS or BFS from each unvisited land cell, marking the whole island; count how many launches occur.
02Pattern
Shortest Path Finding
Reach a target with minimum total cost.
O((V + E) log V)When to reach for it
- Given a graph with weighted edges, you're tasked with finding the shortest path between two nodes.
Spot it in the prompt
Look for problems where you need to optimize distance or traversal time between two points, typically using Dijkstra's or Floyd-Warshall algorithms.
Network Delay Time
How to solve it
Animation shows the Shortest Path Finding techniqueRun Dijkstra from the source over the weighted edges; the answer is the maximum settled distance, or -1 if any node is unreachable.
Relay Broadcast Time is our own problem on the same technique: a new statement, graded in your browser.
03Pattern
Cycle Detection
Spot when traversal loops back on itself.
O(V + E)When to reach for it
- You're required to detect whether a graph contains cycles or not.
Spot it in the prompt
Look for problems where you need to ensure that no node is visited more than once during traversal, employing DFS or BFS to detect back edges.
Course Schedule
How to solve it
Animation shows the Cycle Detection techniqueBuild the prerequisite graph and run Kahn's topological sort; if every course gets ordered there is no cycle, so the schedule is feasible.
Apprenticeship Skill Plan is our own problem on the same technique: a new statement, graded in your browser.
04Pattern
Bipartite Graph Check
Two-color the graph without conflicts.
O(V + E)When to reach for it
- You need to determine if a given undirected graph is bipartite, i.e., it's possible to split the vertices into two independent sets such that no edge connects vertices of the same set.
Spot it in the prompt
Look for problems where you need to color nodes alternately while traversing the graph to detect any conflicts.
Is Graph Bipartite?
How to solve it
Animation shows the Bipartite Graph Check techniqueTraverse each component assigning alternating colors to neighbors; if an edge ever connects two same-colored nodes, the graph is not bipartite.
Two Shift Conflict Split is our own problem on the same technique: a new statement, graded in your browser.
05Pattern
Minimum Spanning Tree
Connect everything for the least total weight.
O(E log E)When to reach for it
- You're tasked with finding the minimum weight connected subtree that connects all vertices in a graph.
Spot it in the prompt
Look for problems involving weighted edges and the need to minimize the total weight to connect all nodes.
Min Cost to Connect All Points
How to solve it
Animation shows the Minimum Spanning Tree techniqueBuild a minimum spanning tree over the complete graph of Manhattan distances using Prim's heap or Kruskal with union-find.
Trenching the Sprinkler Valves is our own problem on the same technique: a new statement, graded in your browser.
06Pattern
Directed Acyclic Graph (DAG) Traversal
Order or explore edges that never loop.
O(V + E)When to reach for it
- You're given a directed graph without cycles, and you need to traverse it efficiently.
Spot it in the prompt
Look for problems where you need to perform a topological sort or find the longest path without revisiting nodes.
Alien Dictionary
How to solve it
Animation shows the Directed Acyclic Graph (DAG) Traversal techniqueDerive ordering edges from adjacent word pairs, then topologically sort the letters; a cycle or bad prefix means no valid order exists.
Lost Collation Order is our own problem on the same technique: a new statement, graded in your browser.
07Pattern
Graph Coloring
Color adjacent nodes differently.
When to reach for it
- You need to assign colors to the vertices of a graph such that no two adjacent vertices have the same color.
Spot it in the prompt
Look for problems where you need to color the graph with a minimum number of colors without violating the coloring rule.
Is Graph Bipartite?
How to solve it
Animation shows the Graph Coloring techniqueTwo-coloring is graph coloring with two colors: alternate colors along edges during traversal, and a same-color edge means it can't be done.
Two Shift Conflict Split is our own problem on the same technique: a new statement, graded in your browser.
After the pattern
Now solve one you haven't seen.
Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.
1,194 problems · 15,062 graded tests · free