This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.**Example 1: **

Input:

0 0 0 0 1 0 0 0 0Output:

0 0 0 0 1 0 0 0 0

**Example 2: **

Input:

0 0 0 0 1 0 1 1 1Output:

0 0 0 0 1 0 1 2 1

**Note:**

- The number of elements of the given matrix will not exceed 10,000.
- There are at least one 0 in the given matrix.
- The cells are adjacent in only four directions: up, down, left and right.

b'

\n## Solution

\n

\n#### Approach #1 Brute force [Time Limit Exceeded]

\n

\n#### Approach #2 Using BFS [Accepted]

\n

\n#### Approach #3 DP Approach [Accepted]

\n

\n

'
\n\n

\n\n

**Intuition**

Do what the question says.

\n**Algorithm**

- \n
- Initialize
`dist[i][j]=INT_MAX`

for all`{i,j}`

cells. \n - Iterate over the matrix. \n
- If cell is
`0`

,`dist[i][j]=0`

, \n - Else, for each
`1`

cell,- \n
- Iterate over the entire matrix \n
- If the cell is
`0`

, calculate its distance from current cell as`abs(k-i)+abs(l-j)`

. \n - If the distance is smaller than the current distance, update it. \n

\n

**Complexity Analysis**

- \n
- \n
Time complexity: .\nIterating over the entire matrix for each

\n`1`

in the matrix. \n - \n
Space complexity: .\nNo extra space required than the

\n`vector<vector<int> > dist`

\n

\n

**Intuition**

*A better brute force*:\nLooking over the entire matrix appears wasteful and hence, we can use Breadth First Search(BFS) to limit the search to the nearest `0`

found for each `1`

. As soon as a `0`

appears during the BFS, we know that the `0`

is nearest, and hence, we move to the next `1`

.

*Think again*:\nBut, in this approach, we will only be able to update the distance of one `1`

using one BFS, which could in fact, result in slightly higher complexity than the Approach #1 brute force.\nBut hey,this could be optimised if we start the BFS from `0`

s and thereby, updating the distances of all the `1`

s in the path.

**Algorithm**

- \n
- For our BFS routine, we keep a queue,
`q`

to maintain the queue of cells to be examined next. \n - We start by adding all the cells with
`0`

s to`q`

. \n - Intially, distance for each
`0`

cell is`0`

and distance for each`1`

is`INT_MAX`

, which is updated during the BFS. \n - Pop the cell from queue, and examine its neighbours. If the new calculated distance for neighbour
`{i,j}`

is smaller, we add`{i,j}`

to`q`

and update`dist[i][j]`

. \n

**Complexity analysis**

- \n
- Time complexity: . \n
- \n
Since, the new cells are added to the queue only if their current distance is greater than the calculated distance, cells are not likely to be added multiple times.

\n \n - \n
Space complexity: . Additional for queue than in Approach #1

\n \n

\n

**Intuition**

The distance of a cell from `0`

can be calculated if we know the nearest distance for all the neighbours, in which case the distance is minimum distance of any neightbour + 1. And, instantly, the word come to mind DP!!

\nFor each `1`

, the minimum path to `0`

can be in any direction. So, we need to check all the 4 direction. In one iteration from top to bottom, we can check left and top directions, and we need another iteration from bottom to top to check for right and bottom direction.

**Algorithm**

- \n
- Iterate the matrix from top to bottom-left to right: \n
- Update\n \n i.e., minimum of the current dist and distance from top or left neighbour +1, that would have been already calculated previously in the current iteration. \n
- Now, we need to do the back iteration in the similar manner: from bottom to top-right to left: \n
- Update\n \n i.e. minimum of current dist and distances calculated from bottom and right neighbours, that would be already available in current iteration. \n

**Complexity analysis**

- \n
- Time complexity: . 2 passes of each \n
- Space complexity: . No additional space required than
`dist vector<vector<int> >`

\n

\n

Analysis written by @abhinavbansal0.

\n