DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Time & Space Complexity Common Mistakes Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Graph Practice Problems

How to Use This Problem List

Graph problems require identifying the algorithm family before writing code. The decision flows through three questions:

GRAPH PROBLEM DECISION TREE:

Is the graph WEIGHTED?
  NO (or all equal weights) → BFS for shortest path
  YES → is the source SINGLE or ALL-PAIRS?
    ALL-PAIRS → Floyd-Warshall
    SINGLE → are there NEGATIVE weights?
      YES → Bellman-Ford
      NO  → is it a DAG?
        YES → Topological DP / DAG shortest path O(V+E)
        NO  → Dijkstra's

Does the problem ask for ORDERING or SCHEDULING?
  → Topological sort (Kahn's or DFS post-order)

Does the problem ask if nodes are CONNECTED or SAME GROUP?
  → Union-Find (DSU) or BFS/DFS components

Does the problem ask for MINIMUM COST TO CONNECT ALL nodes?
  → Minimum Spanning Tree (Kruskal's or Prim's)

Does the problem have a GRID (2D matrix)?
  → BFS/DFS on grid with 4-directional / 8-directional adjacency

Does the problem ask about CYCLES?
  → DFS (undirected: parent check; directed: pathVisited)
  → Kahn's (directed: count < V)

If algorithm is correct, review these SIGNAL WORDS:
  "shortest path, minimum hops/edges"   → BFS (unweighted)
  "minimum cost path"                   → Dijkstra / Bellman-Ford
  "all nodes receive signal"            → Dijkstra + max(dist)
  "ordering respecting dependencies"    → Topological sort
  "can finish / valid schedule"         → Kahn's cycle detection
  "minimum cost to connect all"         → MST
  "connected / same group / component"  → DSU or BFS/DFS
  "cycle detection"                     → DFS pathVisited / Kahn's
  "reachable from target"               → Reverse graph + BFS/DFS

Pattern 1: BFS — Shortest Path & Level Order

BFS gives shortest path in unweighted graphs. Multi-source BFS finds minimum distance from the nearest source.

Problem	Difficulty	Recognition Clue	Key Insight
Number of Islands	Easy	Count connected groups of 1s in grid	BFS/DFS from each unvisited 1; mark component visited; count restarts
Flood Fill	Easy	Change connected region color in grid	BFS/DFS from starting cell; update all connected same-color cells
01 Matrix	Medium	Nearest 0 for each cell in binary matrix	Multi-source BFS: enqueue ALL 0s at distance 0 simultaneously
Rotting Oranges	Medium	Minutes until all oranges rotten	Multi-source BFS from all rotten oranges; answer = max level reached
Walls and Gates	Medium	Fill each empty room with distance to nearest gate	Multi-source BFS from all gates (distance 0)
Word Ladder	Hard	Minimum transformations between words	BFS on implicit graph; each word = vertex, edge if one letter differs
Shortest Path in Binary Matrix	Medium	Shortest 8-directional path in 0/1 grid	BFS with 8 directions; level = path length
Jump Game IV	Hard	Minimum jumps to reach last index	BFS on graph where same-value indices are connected
Open the Lock	Hard	Minimum turns to reach target combination	BFS on state space; each state is current digits
Pacific Atlantic Water Flow	Medium	Cells reachable to both oceans	Reverse BFS from each ocean boundary inward
Minimum Genetic Mutation	Medium	Minimum mutations between gene strings	BFS; each valid mutation = one edge
Bus Routes	Hard	Minimum buses to travel from source to target	BFS on routes (not stops); expand whole route when boarding

Recognition signal: "minimum steps", "minimum hops", "minimum edges", "nearest X", "level by level", "spread outward."

Pattern 2: DFS — Paths, Components & Backtracking

DFS explores all paths, finds connected components, and solves backtracking problems.

Problem	Difficulty	Recognition Clue	Key Insight
Clone Graph	Medium	Deep copy a graph	DFS/BFS with HashMap from original node → cloned node
Path Sum in Graph	Medium	Find all paths from source to target	DFS tracking current path; add to result when target reached
All Paths Source to Target	Medium	Enumerate all paths in DAG from 0 to n-1	DFS backtracking; DAG means no cycle risk
Word Search	Medium	Find word in character grid, no cell reuse	DFS backtracking; mark visited, unmark on backtrack
Number of Distinct Islands	Medium	Count unique island shapes	DFS + encode path shape; use set of shapes
Surrounded Regions	Medium	Capture surrounded O regions	DFS from border O cells; mark safe; convert remaining
Count Sub Islands	Medium	Islands in grid2 that are subsets of grid1 islands	DFS on grid2 islands; entire island must be land in grid1
Reorder Routes to Make All Paths Lead to City 0	Medium	Minimum edge reversals so all paths reach 0	Build undirected + direction tracking; DFS from 0; count wrong-direction edges
Maximum Area of Island	Medium	Largest connected island in grid	DFS returning component size; track max
Find if Path Exists in Graph	Easy	Simple connectivity check	DFS/BFS from source; check if target is reached
Keys and Rooms	Medium	Can you visit all rooms	DFS/BFS from room 0; rooms reached = components
Critical Connections in a Network	Hard	Find bridges (edges whose removal disconnects graph)	Tarjan's bridge-finding DFS with discovery time and low values

Recognition signal: "enumerate all paths", "explore all combinations", "grid word search", "reachable", "shape/structure matching."

Pattern 3: Cycle Detection

Detect cycles in directed and undirected graphs.

Problem	Difficulty	Recognition Clue	Key Insight
Detect Cycle Undirected (DFS)	Easy	"does undirected graph have a cycle"	DFS with parent parameter; visited AND ≠ parent → cycle
Detect Cycle Undirected (BFS)	Easy	Same as above, BFS version	Queue with (node, parent) Pair; visited ≠ parent → cycle
Detect Cycle Directed	Medium	"does directed graph have a cycle"	DFS with pathVisited[]; visited AND pathVisited → back edge
Course Schedule I	Medium	"can you finish all courses given prerequisites"	Kahn's: count == n → no cycle → can finish
Course Schedule II	Medium	Return a valid course order	Kahn's topological sort; if count < n → impossible
Find Eventual Safe States	Medium	"nodes that cannot reach a cycle"	DFS: safe = not on any cycle; reverse result of cycle detection
Redundant Connection	Medium	Find extra edge that creates a cycle	DSU: first edge where find(u)==find(v) is redundant
Redundant Connection II	Hard	Directed graph with one extra edge	More complex — handle cases: two parents for one node, or directed cycle

Recognition signal: "is there a cycle", "can we complete tasks", "safe nodes", "redundant edge", "extra connection."

Pattern 4: Topological Sort

Order vertices in a DAG such that all prerequisites come first.

Problem	Difficulty	Recognition Clue	Key Insight
Course Schedule I	Medium	Can you finish all courses	Kahn's: if count == n → valid DAG → yes
Course Schedule II	Medium	Return valid course order	Kahn's result = topological order
Alien Dictionary	Hard	Infer character order from sorted word list	Build DAG from adjacent word comparisons; topological sort
Sequence Reconstruction	Medium	Is target the UNIQUE topological sort	At each Kahn's step, queue must have exactly 1 element
Minimum Height Trees	Medium	Find roots for minimum height trees	Iteratively remove leaf nodes (like topological sort from leaves)
Parallel Courses	Medium	Minimum semesters to complete all courses	Topological sort level by level; levels = semesters
Largest Color in a Directed Graph	Hard	Maximum count of single color in any valid path	Topological sort + DP on DAG
Build Order	Medium	Order to build projects given dependencies	Kahn's topological sort; detect cycles
Task Scheduler	Medium	Minimum intervals to finish tasks with cooldowns	Greedy + ordering — not strictly topo but ordering-based
Sort Items by Groups Respecting Dependencies	Hard	Topological sort within groups and across groups	Two-level topological sort

Recognition signal: "ordering", "scheduling", "dependencies", "prerequisites", "after X comes Y", "build order", "valid sequence."

Pattern 5: Shortest Path

Find minimum cost/distance paths in weighted graphs.

Problem	Difficulty	Recognition Clue	Key Insight
Network Delay Time	Medium	Time for signal to reach all nodes	Dijkstra from source; answer = max(dist)
Cheapest Flights K Stops	Medium	Cheapest path with at most k stops	Modified Dijkstra/BFS: state = (cost, node, stops_left)
Path with Minimum Effort	Medium	Minimum max-height-difference path in grid	Dijkstra on grid; weight = max(abs(height diff))
Swim in Rising Water	Hard	Minimum time to swim from 0,0 to n-1,n-1	Dijkstra: weight = max elevation seen so far
Find the City with Smallest Number of Reachable Cities	Medium	City with fewest cities within threshold distance	Floyd-Warshall all-pairs; count reachable per city
Minimum Cost to Reach City	Medium	Minimum cost directed graph	Dijkstra single-source
Shortest Path with Alternating Colors	Medium	Shortest path alternating red/blue edges	BFS with state (node, last_edge_color)
Number of Ways to Arrive on Time	Medium	Count shortest paths from 0 to n-1	Dijkstra + DP count: ways[v] += ways[u] when dist[v] updated
Minimum Weighted Subgraph with Required Paths	Hard	Minimum weight subgraph connecting 3 nodes	Dijkstra from src1, src2, and reversed from dest; combine at each vertex
0-1 BFS (Minimum Edge Reversals)	Medium	Min edges to reverse for valid path	0-1 BFS: original direction = 0, reversed = 1; deque BFS
Dijkstra on Implicit Graph (Word Ladder II)	Hard	All shortest transformation sequences	BFS + backtracking from end

Recognition signal: "minimum cost", "cheapest path", "minimum time", "all pairs distance", "signal delay", "within distance threshold."

Pattern 6: Union-Find (DSU)

Dynamic connectivity — grouping elements and querying same-group membership.

Problem	Difficulty	Recognition Clue	Key Insight
Number of Provinces	Medium	Count friend circles / connected components	DSU or BFS/DFS; union friends; count roots
Redundant Connection	Medium	Extra edge that creates cycle	First edge (u,v) where find(u)==find(v)
Accounts Merge	Medium	Merge accounts sharing an email	DSU on emails; merge accounts with shared emails
Most Stones Removed with Same Row/Column	Medium	Remove stones sharing row/column	DSU on rows and cols; answer = stones - components
Satisfiability of Equality Equations	Medium	A==B and A!=B constraints	DSU: union all == pairs; check != pairs don't share root
Smallest String with Swaps	Medium	Minimum string after allowed position swaps	DSU on swappable positions; sort each component
Number of Islands II (dynamic)	Hard	Islands added one by one, count after each	DSU: add cell, union with adjacent land cells, track component count
Making Large Island	Hard	Largest island after flipping one 0 to 1	DSU all islands; for each 0, check adjacent component sizes
Swim in Rising Water (DSU)	Hard	Alternative to Dijkstra using DSU	Sort edges by max height; union until source and target connected
Regions Cut by Slashes	Medium	Count regions formed by / and \ in grid	Scale grid 3×; mark cells; count components
Earliest Moment Friends Know Each Other	Medium	First time all friends in one group	Process events sorted by time; DSU until one component
Graph Connectivity with Threshold	Hard	Nodes share a common divisor > threshold	Union all multiples of each number > threshold

Recognition signal: "same group", "connected", "merge", "union", "component size after change", "dynamic connectivity."

Pattern 7: Minimum Spanning Tree

Connect all nodes with minimum total edge weight.

Problem	Difficulty	Recognition Clue	Key Insight
Min Cost to Connect All Points	Medium	Minimum total Manhattan distance to connect points	Prim's or Kruskal's on complete graph; edge weight = Manhattan distance
Find Critical and Pseudo-Critical Edges	Hard	Edges always/sometimes in MST	Run MST; for each edge: force-include (pseudo) and force-exclude (critical)
Minimum Spanning Tree (classic)	Medium	Connect all nodes minimum total weight	Kruskal's: sort edges, DSU cycle check
Optimize Water Distribution in a Village	Hard	Wells + pipes, minimum cost for every house	Add virtual node 0 for wells; MST on extended graph
Minimum Cost to Supply Water	Hard	Same as above with well costs	Connect each house to virtual source at well cost; MST
Clustering (remove k-1 heaviest MST edges)	Medium	Split graph into k clusters	Build MST; remove k-1 largest edges

Recognition signal: "connect all nodes/points/cities minimum cost", "minimum total weight spanning", "maximum k clusters."

Pattern 8: Advanced Graph Problems

Problems combining multiple techniques or requiring creative modelling.

Problem	Difficulty	Recognition Clue	Key Insight
Strongly Connected Components	Hard	Groups where every node can reach every other	Kosaraju: DFS + reverse graph + DFS in finish order
Critical Connections (Bridges)	Hard	Edges whose removal disconnects graph	Tarjan's bridge detection: low[v] > disc[u]
Articulation Points	Hard	Vertices whose removal disconnects graph	Tarjan's AP detection: low[v] >= disc[u] for non-root
Bipartite Check	Medium	Can graph be 2-coloured	BFS/DFS: alternate colors; conflict = not bipartite
Maximum Bipartite Matching	Hard	Maximum matching in bipartite graph	Hungarian algorithm or Hopcroft-Karp
Vertex Cover	Hard	Minimum vertex set covering all edges	König's theorem: min vertex cover = max matching (bipartite)
Eulerian Path / Circuit	Medium	Path/circuit using every edge exactly once	Hierholzer's algorithm; check degree conditions
Hamiltonian Path	Hard	Path visiting every vertex exactly once	DFS backtracking with bitmask DP (NP-hard in general)
Travelling Salesman	Hard	Shortest tour visiting all cities	Bitmask DP: dp[mask][v] = min cost to visit set mask ending at v
Graph Coloring (k-colorable)	Hard	Assign colors such that no two adjacent nodes share color	Backtracking or greedy; bipartite = 2-colorable

Recognition signal: "every node reachable from every other", "remove one edge/vertex to disconnect", "2-colorable", "use every edge", "visit every city."

Pattern Recognition Quick Reference

Signal Word / Phrase	Algorithm	Template
Minimum hops / edges / steps	BFS	Queue + visited + level count
Nearest X (multi-source)	Multi-source BFS	Pre-load all sources at dist 0
Minimum cost path (positive weights)	Dijkstra	Min-heap + stale skip
Minimum cost path (any weights)	Bellman-Ford	Relax all edges V-1 times
All-pairs distances	Floyd-Warshall	3-nested loops over k, i, j
Ordering with dependencies	Topological sort	Kahn's (in-degree BFS)
Can schedule / valid DAG	Kahn's cycle check	count == V → valid
Connected groups / components	BFS/DFS outer loop	restart from each unvisited
Same group / dynamic merge	Union-Find	find + union + component count
Connect all minimum cost	MST (Kruskal/Prim)	Sort edges + DSU
Grid exploration	BFS/DFS on grid	4-dir or 8-dir adjacency
Word in grid (backtrack)	DFS backtracking	Mark + recurse + unmark
Cycle in directed graph	DFS pathVisited	visited[] + inStack[]
Cycle in undirected graph	DFS parent / BFS Pair	visited[] + parent param
Nodes safe from cycles	Reverse + DFS	Reverse edges; safe from cycle = eventually safe
Reach target (backward)	Reverse graph BFS	Reverse all edges; BFS from target
0/1 weighted edges	0-1 BFS	Deque: 0→front, 1→back

Recommended Study Order

WEEK 1 — BFS & DFS Foundations
  Pattern 1: Number of Islands, Flood Fill, Rotting Oranges, 01 Matrix
  Pattern 2: Clone Graph, All Paths Source to Target, Word Search
  Grid problems: Max Area Island, Surrounded Regions

WEEK 2 — Cycle Detection & Topological Sort
  Pattern 3: Course Schedule I & II, Redundant Connection
  Pattern 4: Alien Dictionary, Sequence Reconstruction, Parallel Courses

WEEK 3 — Weighted Graphs
  Pattern 5: Network Delay Time, Cheapest Flights, Path with Min Effort
  Dijkstra deep dive: Number of Ways to Arrive, Swim in Rising Water

WEEK 4 — DSU & MST
  Pattern 6: Number of Provinces, Accounts Merge, Satisfiability of Equality
  Pattern 7: Min Cost to Connect Points, Find Critical/Pseudo-Critical Edges

WEEK 5 — Advanced
  Pattern 8: Bipartite Check, Critical Connections, SCC
  Mixed: revisit hard problems from earlier patterns
  Mock: 2 graph problems under timed conditions

Difficulty Progression Reference

Stage	Problems	What to focus on
Foundation	Islands, BFS grids, DFS paths	Outer loop for disconnected; visited[] discipline
Early Intermediate	Course Schedule I/II, Clone Graph, Word Search	Pattern recognition; topological sort mechanics
Intermediate	Dijkstra variants, DSU applications, Accounts Merge	State design; algorithm selection
Late Intermediate	Alien Dictionary, Critical Connections, Cheapest Flights	Modelling problems as graphs; combining techniques
Advanced	TSP, Hamiltonian, Max Bipartite Matching, SCC	Specialized algorithms; NP-hard approximations

Common Interview Problem-Solving Checklist

BEFORE CODING:
  □ Is the graph directed or undirected?
  □ Is it weighted or unweighted?
  □ Can it be disconnected? (outer loop needed?)
  □ Is it guaranteed to be a DAG? (topological sort safe?)
  □ What is the graph size? (V, E estimate → algorithm time check)
  □ Does it fit one of the 8 patterns above?

CHOOSING THE DATA STRUCTURE:
  □ Adjacency list for sparse/general graphs
  □ Adjacency matrix for dense graphs or O(1) edge check needed
  □ Edge list for MST algorithms
  □ Grid as implicit graph (no explicit adjacency list needed)

COMMON MODELLING TRICKS:
  □ Grid → graph: cell (r,c) → node r*cols+c
  □ State machine → graph: each state = node, transitions = edges
  □ Bidirectional BFS for large graphs (meet in middle)
  □ Reverse graph: "can reach target" → "reachable from target reversed"
  □ Virtual source: multi-source BFS → add supersource at distance 0
  □ State expansion: Dijkstra with extra state (stops, fuel, cooldown)

EDGE CASES TO HANDLE:
  □ Single vertex (V=1) — no edges needed for spanning tree
  □ Disconnected graph — outer loop / check all components
  □ Self-loops — skip when checking cycle in undirected
  □ Multiple edges between same pair (multigraph)
  □ Negative weights — not valid for Dijkstra; use Bellman-Ford
  □ Target unreachable — dist[target] == ∞ → return -1

COMPLEXITY CHECK:
  BFS/DFS:           O(V + E) — acceptable for V,E ≤ 10^5
  Dijkstra (heap):   O((V+E) log V) — acceptable for V,E ≤ 10^5
  Bellman-Ford:      O(VE) — only for V,E ≤ 10^3
  Floyd-Warshall:    O(V³) — only for V ≤ 500
  Topological sort:  O(V + E) — always prefer over O(V²)
  Kruskal's MST:     O(E log E) — E ≤ 10^5 fine
  Bitmask DP (TSP):  O(2^V × V) — only for V ≤ 20

Algorithm Selection Summary

GRAPH SIZE    PROBLEM TYPE                    RECOMMENDED ALGORITHM
──────────────────────────────────────────────────────────────────────
V,E ≤ 10^5   Shortest unweighted             BFS
V,E ≤ 10^5   Shortest weighted positive      Dijkstra heap
V,E ≤ 10^3   Shortest any weights            Bellman-Ford
V ≤ 500      All-pairs shortest path         Floyd-Warshall
V,E ≤ 10^5   Connected components            BFS/DFS or DSU
V,E ≤ 10^5   Dependency ordering             Kahn's topological sort
V,E ≤ 10^5   Minimum spanning tree           Kruskal's or Prim's
V,E ≤ 10^5   Cycle detection (undirected)    DFS parent / BFS Pair
V,E ≤ 10^5   Cycle detection (directed)      DFS pathVisited / Kahn's
V ≤ 20       Visit all vertices minimum cost  Bitmask DP (TSP)
Grid N×M     Flood fill / component count    BFS/DFS with 4-dir
Grid N×M     Minimum path in grid            BFS or Dijkstra on grid

Progress Tracking

After solving each graph problem, record:

›Pattern — which of the 8 patterns does this belong to?
›Algorithm chosen — BFS, DFS, Dijkstra, Bellman-Ford, Floyd-Warshall, Topo sort, DSU, MST?
›State design — what did each node/state represent?
›Modelling trick — did you reverse the graph, add a virtual node, expand state?
›Edge cases — disconnected graph, unreachable target, negative weights?
›Time to solve — target 20 min easy, 35 min medium, 45 min hard

The decisive signal that graph pattern recognition is working: when you read "minimum cost to connect all points" and immediately think "MST — Kruskal's or Prim's, sort edges by Manhattan distance, DSU cycle check, stop at V-1 edges" — before reading the constraints or examples.

Suggested Quiz

Problem: 'given a 2D grid of 0s and 1s, count the number of islands (groups of connected 1s).' Which pattern does this follow?

1/6

←

PreviousUnion Find (DSU)

NextBacktracking Basics

→