Steps to the Nearest Zero

Medium

You are given a rectangular grid grid of zeros and ones. From any cell you can step to a cell that shares a side with it (up, down, left or right), and each step costs 1. For every cell, find how many steps it takes to reach the closest cell holding a zero. For the zeros themselves, that distance is 0. Return a grid of the same size where each cell holds its distance.

Example 1

grid=[[1, 1, 0], [1, 1, 1], [0, 1, 1]] → [[2, 1, 0], [1, 2, 1], [0, 1, 2]]

The zeros sit in the top-right and bottom-left corners. The center cell is two steps from either of them, and so is the bottom-right cell (up twice or left twice).

Example 2

grid=[[1, 1, 1, 0]] → [[3, 2, 1, 0]]

A single row: the distances just count down toward the zero on the right.

Example 3

grid=[[0, 0], [0, 0]] → [[0, 0], [0, 0]]

Constraints

1 ≤ rows, columns
rows × columns ≤ 10⁴
grid[i][j] is 0 or 1
The grid contains at least one 0

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Breadth-First Search Array Dynamic Programming Matrix

Similar problems

Farthest From Any Shore Medium Block the Only Route Medium Stones on a 3 × 3 Board Medium Longest Uphill Walk Hard Six-Cell Tile Slider Hard

Input

grid=[[1, 1, 0], [1, 1, 1], [0, 1, 1]]

Expected

[[2, 1, 0], [1, 2, 1], [0, 1, 2]]

Run checks the first 3 tests in your browser. Submit checks all 70 tests on the server, hidden ones included.