Java solution, time complexity O(n), no auxiliary space.


  • 1
    B

    Algorithm: Dynamic Programming
    Time complexity is O(n), since I traverse the matrix twice.

    public class Solution {
        public int[][] updateMatrix(int[][] matrix) {
            int rowL = matrix.length;
            int colL = matrix[0].length;
            int longer = Math.max(rowL, colL);
            int[][] result = new int[rowL][colL];
            fromUpLeftToRightDown(matrix, result, rowL, colL, longer);
            fromRightDownToUpLeft(matrix, result, rowL, colL, longer);
            return result;
        }
        private void fromUpLeftToRightDown(int[][]matrix, int[][]result, int rowL, int colL, int longer) {
            for (int i = 0; i < rowL; i++) {
                for (int j = 0; j < colL; j++) {
                    if (matrix[i][j] == 0) {
                        result[i][j] = 0;
                    } else if (i == 0 && j == 0) {
                        result[i][j] = longer;
                    } else if (i == 0) {
                        result[i][j] = 1 + result[i][j - 1];
                    } else if (j == 0) {
                        result[i][j] = 1 + result[i - 1][j];
                    } else {
                        result[i][j] = 1 + Math.min(result[i][j - 1], result[i - 1][j]);
                    }
                }
            }
        }
        private void fromRightDownToUpLeft(int[][]matrix, int[][]result, int rowL, int colL, int longer) {
            for (int i = rowL - 1; i >= 0; i--) {
                for (int j = colL - 1; j >= 0; j--) {
                    if (matrix[i][j] == 0 || (i == rowL - 1 && j == colL - 1)) {
                        continue;
                    } else if (i == rowL - 1) {
                        result[i][j] = Math.min(result[i][j], 1 + result[i][j + 1]);
                    } else if (j == colL - 1) {
                        result[i][j] = Math.min(result[i][j], 1 + result[i + 1][j]);
                    } else {
                        result[i][j] = Math.min(result[i][j], Math.min(1 + result[i][j + 1], 1 + result[i + 1][j]));
                    }
                }
            }
        }
    }
    

Log in to reply
 

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