01 Matrix

Problem

Given a matrix of 0s and 1s, return a matrix where each cell holds the distance to the nearest 0, with distances measured by four-directional moves.

Seed a multi-source BFS with every 0 at distance 0 and expand outward to unvisited cells. Assume the matrix contains at least one 0.

Hint

Every cell is reached exactly once because BFS processes cells in increasing distance order.

case 1

in: [[[0,0,0],[0,1,0],[0,0,0]]]

expected: [[0,0,0],[0,1,0],[0,0,0]]

case 2

in: [[[0,0,0],[0,1,0],[1,1,1]]]

expected: [[0,0,0],[0,1,0],[1,2,1]]

case 3

in: [[[0]]]

expected: [[0]]

case 4

in: [[[1,0]]]

expected: [[1,0]]

case 5

in: [[[0,1,1],[1,1,1]]]

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

Starter codePython

def update_matrix(mat):
    # Your code here
    pass

5 test cases · run your code against them in the editor