JAVA DP solution, O(N*M) time double traverse matrix; 67ms.


  • 0
    H

    Algo thinking:
    dp[i][j] represents updated matrix value at [i, j];
    double traverse:
    (1) 1st traverse: from upper left conner to bottom right conner
    (2) 2nd traverse: from bottom right conner to upper left conner

    time = O(N*M), space = O(1)

    public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
        
        int n = matrix.size();
        int m = matrix.get(0).size();
        
        List<List<Integer>> updatedMatrix = new ArrayList<List<Integer>>();
        int[][] dir = new int[][]{{0, -1}, {-1, 0}};
        for (int i = 0; i < n; i++) {
            updatedMatrix.add(new ArrayList<>());
            for (int j = 0; j < m; j++) {
                if (matrix.get(i).get(j) == 0) {
                    updatedMatrix.get(i).add(0);
                } else {
                    int dist = Integer.MAX_VALUE;
                    for (int[] d: dir) {
                        int newI = i + d[0];
                        int newJ = j + d[1];
                        if (newI < 0 || newJ < 0 || updatedMatrix.get(newI).get(newJ) == Integer.MAX_VALUE) continue;
                        dist = Math.min(dist, 1 + updatedMatrix.get(newI).get(newJ));
                    }
                    updatedMatrix.get(i).add(dist);
                }
            }
        }
        
        dir = new int[][]{{0, 1}, {1, 0}};
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                if (matrix.get(i).get(j) != 0) {
                    int dist = updatedMatrix.get(i).get(j);
                    for (int[] d: dir) {
                        int newI = i + d[0];
                        int newJ = j + d[1];
                        if (newI >= n || newJ >= m) continue;
                        dist = Math.min(dist, 1 + updatedMatrix.get(newI).get(newJ));
                    }
                    updatedMatrix.get(i).set(j, dist);
                }
            }
        }
        
        return updatedMatrix;
    }

Log in to reply
 

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