What is the brute force approach and complexity for Shortest Path in Binary Matrix?

DFS over every simple clear path; keep the fewest cells that reach the end with time complexity O(7^(n²)) and space complexity O(n²).

What is the optimal approach and complexity for Shortest Path in Binary Matrix?

BFS from the top-left cell with 8 directions; the first pop of the end cell is the answer with optimal time complexity O(n²) and space complexity O(n²).

Shortest Path in Binary Matrix

Q: How do you identify the pattern for Shortest Path in Binary Matrix?

Look for key signals in the prompt: "clear path, cells with 1 are blocked" indicates Only 0 cells can be stepped on. The 1 cells are walls.; "shortest path, every move costs the same" indicates Unweighted, so a BFS gives the shortest path: the first arrival at a cell is its shortest.; "eight directions, including diagonals" indicates Only the neighbour list changes. The BFS stays the same.; "number of cells on the path" indicates The start cell counts as 1, so the answer is one more than the number of moves..

Medium·LeetCode #1091 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You are given an n × n grid of 0s (open) and 1s (blocked). Find the shortest clear path from the top-left cell to the bottom-right cell.

A clear path uses only open cells. Each step can go to any of the eight neighbours of the current cell: the four straight ones and the four diagonal ones. Diagonal steps are allowed.

Return the number of cells on the shortest clear path, start and end included. Return -1 if there is no clear path. If the start or the end cell is blocked, there is no path.

Input

grid, an n × n grid of 0 and 1.

Output

The number of cells on the shortest clear path, or -1.

Example 1

Input: grid = [[0,1],[1,0]]

Output: 2

Step diagonally from (0,0) to (1,1). The path has 2 cells.

Example 2

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]

Output: 4

Go right to (0,1), then diagonally to (1,2), then down to (2,2). That is 4 cells.

Example 3

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]

Output: -1

The start cell is blocked, so there is no clear path.

Constraints

• 1 ≤ n ≤ 100
• Each cell is 0 or 1.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“clear path, cells with 1 are blocked”

→ Only 0 cells can be stepped on. The 1 cells are walls.

“shortest path, every move costs the same”

→ Unweighted, so a BFS gives the shortest path: the first arrival at a cell is its shortest.

“eight directions, including diagonals”

→ Only the neighbour list changes. The BFS stays the same.

“number of cells on the path”

→ The start cell counts as 1, so the answer is one more than the number of moves.

Approach Complexity Ladder

Brute Force — try every clear path, keep the shortestO(7^(n²))O(n²)

DFS over every simple clear path; keep the fewest cells that reach the end

Optimal — BFS in 8 directions, counting cellsO(n²)O(n²)

BFS from the top-left cell with 8 directions; the first pop of the end cell is the answer

Brute Force Intuition

Walk every clear path from the top-left cell that never reuses a cell. When a path reaches the bottom-right cell, record its cell count. The answer is the smallest count. Every path is walked to its end, so the work grows exponentially with the grid.

Recognition rule for this sub-pattern:

Unweighted grid → BFS. Extra state (keys, obstacles removed) becomes part of the node.

Remember this · Graph BFS / DFS

Trigger

Grid of cells, islands, regions, "minimum steps", transformations between states, connected components.

Think

What is a node, what is an edge, and do I need the shortest path or just reachability?

Key question

How do I mark visited so I never process a node twice?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Graph BFS / DFS translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Food Delivery System (Zomato / DoorDash)

Geospatial indexing and shortest dispatch routing for delivery partners.

Explore Track

C++ Internals

Virtual Method Table (vtable) & Dynamic Dispatch

Polymorphic graph nodes and state machine execution overhead.

Explore Track

Nearest Exit from Entrance in Maze Shortest Path in a Grid with Obstacles Elimination