What is the brute force approach and complexity for 01 Matrix?

For each 1, run a BFS until the first 0 comes out of the queue with time complexity O((R · C)²) and space complexity O(R · C).

What is the optimal approach and complexity for 01 Matrix?

Put all the 0s in the queue at distance 0; one BFS gives every cell its distance with optimal time complexity O(R · C) and space complexity O(R · C).

How do you identify the pattern for 01 Matrix?

Look for key signals in the prompt: "distance to the nearest 0" indicates Many starting points (every 0), and each cell wants the nearest one. That is a multi-source BFS.; "one step to a cell that shares a side" indicates Each move costs one step, so BFS gives shortest distances.; "return a grid of the same size" indicates Every cell is an answer. One BFS fills them all, so there is no search per cell..

01 Matrix

Medium·LeetCode #542 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You get a grid made of 0s and 1s. For every cell, find the distance to the nearest 0. Two cells are one step apart when they share a side (up, down, left or right).

Return a grid of the same size. Each cell holds its distance to the nearest 0. A 0 is at distance 0 from itself.

Input

mat, an m × n grid of 0s and 1s.

Output

An m × n grid. Each cell holds the number of steps to its nearest 0.

Example 1

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

Output: [[0,0,0],[0,1,0],[0,0,0]]

The only 1 is in the centre. It touches a 0 on all four sides, so its distance is 1.

Example 2

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

Output: [[0,0,0],[0,1,0],[1,2,1]]

The bottom-middle 1 has no 0 next to it. Its nearest 0 is two steps away, through the centre 1.

Example 3

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

Output: [[3,2,1,0]]

The 0 is at the right end. Each 1 is one step further from it than the 1 to its right.

Constraints

• The grid has m rows and n columns, with 1 ≤ m, n ≤ 10^4 and 1 ≤ m · n ≤ 10^4.
• Each cell is 0 or 1.
• There is at least one 0 in the grid.

Pattern Recognition Clues

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

“distance to the nearest 0”

→ Many starting points (every 0), and each cell wants the nearest one. That is a multi-source BFS.

“one step to a cell that shares a side”

→ Each move costs one step, so BFS gives shortest distances.

“return a grid of the same size”

→ Every cell is an answer. One BFS fills them all, so there is no search per cell.

Approach Complexity Ladder

Brute Force — one BFS from every 1O((R · C)²)O(R · C)

For each 1, run a BFS until the first 0 comes out of the queue

Optimal — multi-source BFS from every 0O(R · C)O(R · C)

Put all the 0s in the queue at distance 0; one BFS gives every cell its distance

Brute Force Intuition

For each cell that holds a 1, run a BFS from that cell. The first 0 that comes out of the queue is its nearest 0, so the BFS depth at that point is the answer for that cell. A 0 gets 0. Each BFS starts from scratch, so the same cells are searched again and again.

Recognition rule for this sub-pattern:

Many starting points spread at the same time — push all of them into the queue first.

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

Rotting Oranges Walls and Gates