Matrix in O(n)

Here is the problem: https://leetcode.com/problems/01-matrix/

542. 01 Matrix

Medium

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,0]]

Output:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Example 2:

Input:
[[0,0,0],
 [0,1,0],
 [1,1,1]]

Output:
[[0,0,0],
 [0,1,0],
 [1,2,1]]

Note:

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

The idea will be to do 2-passes: from top to bottom (O(n)) and then from bottom to top (O(n)), using an extra matrix to keep track of the min distance. The first pass you check the min distance comparing with the previous row and the previous col. The second pass you keep track of the min between the current element and the next row, next col. Doing that guarantees you a (DP-like) solution. Beats 100% of the other C# solutions. Cheers, and happy Thanks Giving!!! :)

public class Solution
{
    public int[][] UpdateMatrix(int[][] matrix)
    {
        int[][] distance = (int[][])matrix.Clone();

        //top left to bottom right
        for (int r = 0; r < distance.GetLength(0); r++)
        {
            for (int c = 0; c < distance[0].GetLength(0); c++)
            {
                if (matrix[r][c] == 0) distance[r][c] = 0;
                else
                {
                    if (c - 1 < 0)
                    {
                        if (r - 1 < 0) distance[r][c] = 20000;
                        else distance[r][c] = 1 + distance[r - 1][c];
                    }
                    else if (r - 1 < 0)
                    {
                        distance[r][c] = 1 + distance[r][c - 1];
                    }
                    else
                    {
                        distance[r][c] = 1 + Math.Min(distance[r - 1][c], distance[r][c - 1]);
                    }
                }
            }
        }

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

        return distance;
    }
}