LeetCode 1091 Shortest Path in Binary Matrix - Example and Complexity Analysis

Trace the 3×3 grid.

Start: (0,0), length 1.

Level 1 (length 2): (0,1), (1,0)? (1,0) is blocked. Only (0,1).

Level 2 (length 3): from (0,1), reach (0,2), (1,2).

Level 3 (length 4): from (0,2), (1,2), reach... (1,2) can reach (2,2)!

Actually: (0,0) → (0,1) → (0,2) → (1,2) → (2,2) is 5 cells.

Wait, let me retrace. Level 4 (length 5): from (1,2), reach (2,2). Return 5.

Each cell visited once. $O(n^2)$ time. $O(n^2)$ space for queue.