Graph Traversal And Constrained Pathfinding

What's being tested

These problems test grid graph traversal and constrained shortest-path thinking: encoding extra resources (health, swaps, gravity state) into the search state and choosing the right traversal algorithm. Interviewers probe correctness under edge cases, time/space tradeoffs, and clean state pruning.

Patterns & templates

• BFS on a grid using deque for unweighted moves — O(V+E) time; store visited as (r,c) or richer state when needed.
• State-augmented BFS: include resource counters in the state tuple, e.g., (r,c,health,swaps); visited becomes a set of tuples.
• Dijkstra / A* with a priority queue (heapq) for weighted costs or heuristics; use admissible heuristic for A* to guarantee optimality.
• 0-1 BFS when edge costs are only 0 or 1 — use deque push-left/push-right to achieve O(V+E).
• Multi-source BFS to initialize simultaneous starts (or precompute distances) in O(V+E).
• Simulation loop for gravity/blocks: apply deterministic drop until stable, then treat resulting grid as a new node; memoize grid signatures to avoid repeats.
• Bitmasking to track small sets (collected items/keys) — O(2^k * N) states; watch exponential blowup when k>20.

Common pitfalls

Pitfall: Forgetting to include remaining resources in the visited key — leads to incorrect pruning and missed valid paths.

Pitfall: Using plain BFS for non-uniform costs — yields wrong shortest paths; prefer Dijkstra/A* or 0-1 BFS when applicable.

Pitfall: Not bounding state space (e.g., unbounded health accumulation) — always clamp/normalize state and argue complexity.

Practice these
the practice cards below cover the canonical variants — solve all of them and time yourself.