Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

147. 01 Matrix

MediumDay 43 of 60Graphs

Given an m x n binary matrix mat, return a matrix of the same size where each cell holds the distance to the nearest 0 in mat. The distance between two neighbouring cells (up, down, left, right) is 1. There is at least one 0 in the matrix.

Example 1
Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]
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 cell is 2 steps away from the nearest 0.
Constraints
  • 1 <= m, n and m * n <= 10^4
  • mat[i][j] is 0 or 1
  • At least one 0 exists
Hints
Frequently asked at: Amazon, Google, Uber
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min