18-line C++ DP Solution, O(n), Easy to Understand

• Simple DP, just check if the neigbours know how far are they to the nearest 0 when I don't know

``````class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int h=matrix.size(), w=matrix[0].size();
vector<vector<int>> dp(h,vector<int>(w,INT_MAX));
for(int times=0;times<=1;times++) // two passes, first forward then backward
for(int i=times?h-1:0;times?i>=0:i<h;times?i--:i++)
for(int j=times?w-1:0;times?j>=0:j<w;times?j--:j++)
if(matrix[i][j]==0)
dp[i][j]=0;
else {
if(i&&dp[i-1][j]!=INT_MAX&&dp[i][j]>dp[i-1][j]+1) // look up
dp[i][j]=dp[i-1][j]+1;
if(j&&dp[i][j-1]!=INT_MAX&&dp[i][j]>dp[i][j-1]+1) // look left
dp[i][j]=dp[i][j-1]+1;
if(i<h-1&&dp[i+1][j]!=INT_MAX&&dp[i][j]>dp[i+1][j]+1) // look down
dp[i][j]=dp[i+1][j]+1;
if(j<w-1&&dp[i][j+1]!=INT_MAX&&dp[i][j]>dp[i][j+1]+1) // look right
dp[i][j]=dp[i][j+1]+1;
}
return dp;
}
};
``````

• a great idea!
thanks a lot for the different solution!

• This post is deleted!

• Not sure if it is really a DP, but based on the same idea, and directly use `matrix` as dp table. Here is my Python version.

It takes 675 ms to run. It is faster than my BFS version https://discuss.leetcode.com/topic/83571/python-bfs, which takes 986 ms.

``````class Solution(object):
def check(self, matrix, height, width, i, j):
if (i > 0 and matrix[i-1][j] + 1 < matrix[i][j]):
matrix[i][j] = matrix[i-1][j] + 1
if (i + 1 < height and matrix[i+1][j] + 1 < matrix[i][j]):
matrix[i][j] = matrix[i+1][j] + 1
if (j > 0 and matrix[i][j-1] + 1 < matrix[i][j]):
matrix[i][j] = matrix[i][j-1] + 1
if (j + 1 < width and matrix[i][j+1] + 1 < matrix[i][j]):
matrix[i][j] = matrix[i][j+1] + 1

def updateMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
height = len(matrix)
width = len(matrix[0])
for i in xrange(height):
for j in xrange(width):
if matrix[i][j] != 0:
matrix[i][j] = height + width

# traverse forward
for i in xrange(height):
for j in xrange(width):
if matrix[i][j] == 0:
continue
self.check(matrix, height, width, i, j)

# traverse backward
for i in xrange(height - 1, -1, -1):
for j in xrange(width -1, -1, -1):
if matrix[i][j] == 0:
continue
self.check(matrix, height, width, i, j)

return matrix
``````

• Nice solution.
One backward and one forward to make sure the nearest 0.

• Indeed nice.
I had thought only what is below AND right of a zero gets set forwards, and only what is above AND to the left of a zero going backwards. But because we propagate across the whole row, the first pass gets anything below anything to the right of a zero. Then on the way backwards, the bottom row gets completed, and that propagates up.

• code style is a problem.

• @yuanqili This is called Line-Crushing style.

• It still confuses me that why exactly `2 passes` are needed. Could anybody give any theoretical proof about it?

• @jtimberlakers
The first pass makes sure we have distance to nearest zero from top-left direction.
The second pass makes sure we have distance to nearest zero from bottom-right direction.

It is more clear it write this way (Java):

``````public int[][] updateMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] ans = new int[m][n];
for (int[] row : ans)
Arrays.fill(row, m + n);

// top-left to bottom-right
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (matrix[r][c] == 0) ans[r][c] = 0;
else {
if (r > 0) ans[r][c] = Math.min(ans[r][c], 1 + ans[r - 1][c]);
if (c > 0) ans[r][c] = Math.min(ans[r][c], 1 + ans[r][c - 1]);
}
}
}

// bottom-right to top-left
for (int r = m - 1; r >= 0; r--) {
for (int c = n - 1; c >= 0; c--) {
if (matrix[r][c] == 0) ans[r][c] = 0;
else {
if (r < m - 1) ans[r][c] = Math.min(ans[r][c], 1 + ans[r + 1][c]);
if (c < n - 1) ans[r][c] = Math.min(ans[r][c], 1 + ans[r][c + 1]);
}
}
}

return ans;
}
``````

• Thank you for your solution.

Here's a little suggestion. Because `INT_MAX++` will lead to a overflow, the if statement does a judgement.
However, if the dp matrix is initialized with `INT_MAX - 1`(or which is a bit larger than 2 times of matrix's size), there's no need to judge `dp[i-1][j] != INT_MAX` in the if-condition.

• @luming89 Nice idea. Obviously, you don't like using space.

• @yuxiangmusic why filling the array with row+col work not any other.

• Some thoughts on why two passes are enough to find the shortest path. Suppose there is a directed path p from a 0 to an e(i, j) in the matrix and suppose this path is shortest, so that dp[i, j] = length(p) after the code terminates. The top-down & left-right pass will optimize any subpath of p that has directions down or right, the bottom-up & right-left pass will optimize any subpath of p that has direction up or left.

• @badalgupta9911103602 The maximum of distance between tow cells is row+col

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.