CodeWithYash

Intermediate · Module 17 · Lesson 4

Grid graphs

Treat matrix cells and neighbor moves as a graph.

15–25 min readLesson 98 of 123

Lesson 98 of 123

1d streak

Theory lesson · Step-by-step

Understand Grid graphs

Treat matrix cells and neighbor moves as a graph.

Worked approach

Trace the reasoning step by step

  1. 1Choose a graph representation and define directedness and weights for Grid graphs.
  2. 2Initialize visited, distance, parent, color, indegree, or component state.
  3. 3Remove one frontier item and inspect each outgoing edge.
  4. 4Update only when an edge proves new or better information.
  5. 5Repeat from every unvisited vertex when the graph may be disconnected.

Concrete example

Count a 2×2 island of connected 1-cells.

  1. 1Start at one unvisited land cell.
  2. 2Visit its four-directional land neighbors.
  3. 3Mark each once.

All connected land cells form one component.

What must remain true (Loop Invariant)

Every vertex finalized by Grid graphs has the promised reachability, component, order, or distance property; frontier state represents discovered but unfinished work.

Cost Model

Complexity & Trade-offs

Grid traversal
O(rows × cols)
O(rows × cols)
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Networks, dependencies, connectivity, shortest paths, and grid movement.
  • Ordering prerequisite-constrained work.
  • Grouping reachable or mutually reachable states.

Common mistakes

  • Marking visited too late and enqueuing the same vertex repeatedly.
  • Ignoring disconnected components.
  • Using an algorithm whose weight assumptions do not match the graph.

Practice prompts

  • Reproduce the worked Grid graphs example without looking at the trace.
  • Change one input condition and explain whether the Grid graphs invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.