542. 01 Matrix

// LeetCode URL: https://leetcode.com/problems/01-matrix/

/**
 * Dynamic Programming
 *
 * Refer: 1)
 * https://leetcode.com/problems/01-matrix/discuss/101051/Simple-Java-solution-beat-99-(use-DP)
 * 2)
 * https://leetcode.com/problems/01-matrix/discuss/101051/Simple-Java-solution-beat-99-(use-DP)/113437
 *
 * The first iteration is from upper left corner to lower right. It's trying to
 * update dis[i][j] to be the distance to the nearest 0 that is in the top left
 * region relative to (i,j). If there's a nearer 0 to the right or to the bottom
 * of (i,j), it won't catch that. And because of the direction of the double
 * loop, it's already in correct iterative order, meaning, you must have dealt
 * with dis[i-1][j] and dis[i][j-1] before you deal with dis[i][j]
 *
 * Then in the second loop, it goes the opposite direction from the lower right
 * corner. So it'll find the distance to the nearest 0 in the bottom right
 * region. Now combine that with the result from the first loop, it'll cover
 * nearest 0 in all directions. That is where dis[i][j] takes the min of its
 * previous value from the first loop, and the new value (distance to the
 * nearest 0 in the lower right region)
 *
 * Time Complexity: O(2 * M * N)
 *
 * Space Complexity: O(M * N) - Including the result space. O(1) - Excluding the
 * result space.
 *
 * M = Number of rows. N = Number of columns.
 */
class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new int[0][0];
        }

        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] result = new int[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] != 0) {
                    // If the cell in original matrix is not 0, then set this result cell to
                    // Integer.MAX_VALUE. This will help to find the minimum in the following
                    // conditions.
                    result[i][j] = Integer.MAX_VALUE;
                    if (i > 0 && result[i - 1][j] != Integer.MAX_VALUE) {
                        result[i][j] = result[i - 1][j] + 1;
                    }
                    if (j > 0 && result[i][j - 1] != Integer.MAX_VALUE) {
                        result[i][j] = Math.min(result[i][j], result[i][j - 1] + 1);
                    }
                }
            }
        }

        for (int i = rows - 1; i >= 0; i--) {
            for (int j = cols - 1; j >= 0; j--) {
                // Integer.MAX_VALUE check can be removed from below conditions if there is at
                // least one 0 in the given matrix
                if (i < rows - 1 && result[i + 1][j] != Integer.MAX_VALUE) {
                    result[i][j] = Math.min(result[i][j], result[i + 1][j] + 1);
                }
                if (j < cols - 1 && result[i][j + 1] != Integer.MAX_VALUE) {
                    result[i][j] = Math.min(result[i][j], result[i][j + 1] + 1);
                }
            }
        }

        return result;
    }
}