Solution

Approach #1 Brute force [Time Limit Exceeded]

Intuition

Do what the question says.

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
\n

Complexity Analysis

\n
• \n

  Time complexity: $$O((r \\cdot c)^2)$$ .\nIterating over the entire matrix for each 1 in the matrix.

  \n
\n
• \n

  Space complexity: $$O(r \\cdot c)$$ .\nNo extra space required than the vector<vector<int> > dist

  \n
\n

Approach #2 Using BFS [Accepted]

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 0s and thereby, updating the distances of all the 1s 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 0s 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: $$O(r \\cdot c)$$ .
\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: $$O(r \\cdot c)$$ . Additional $$O(r \\cdot c)$$ for queue than in Approach #1

  \n
\n

Approach #3 DP Approach [Accepted]

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 $$\\text{dist}[i][j]=\\min(\\text{dist}[i][j],\\min(\\text{dist}[i][j-1],\\text{dist}[i-1][j])+1)$$ \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 $$\\text{dist}[i][j]=\\min(\\text{dist}[i][j],\\min(\\text{dist}[i][j+1],\\text{dist}[i+1][j])+1)$$ \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: $$O(r \\cdot c)$$ . 2 passes of $$r \\cdot c$$ each
\n
• Space complexity: $$O(r \\cdot c)$$ . No additional space required than dist vector<vector<int> >
\n

Analysis written by @abhinavbansal0.