Java 33ms solution with two sweeps in O(n)


  • 16
    Q

    In the first sweep, we visit each entry in natural order and answer[i][j] = min(Integer.MAX_VALUE, min(answer[i - 1][j], answer[i][j - 1]) + 1).
    in the second sweep, we visit each entry in reverse order and answer[i][j] = min(answer[i][j], min(answer[i + 1][j], answer[i][j + 1]) + 1).

    public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
            List<List<Integer>> answer = new LinkedList();
    		if(matrix.size() == 0) return answer;
    		int[][] array = new int[matrix.size()][matrix.get(0).size()];
    		int i = 0, j = 0;
    		for(List<Integer> list : matrix) {
    			for(Integer x : list) {
    				if(x == 0) {
    					array[i][j] = 0;
    				}
    				else {
    					int left = Integer.MAX_VALUE - 1, top = Integer.MAX_VALUE - 1;
    					if(i - 1 >= 0) top = array[i - 1][j];
    					if(j - 1 >= 0) left = array[i][j - 1];
    					array[i][j] = Math.min(Integer.MAX_VALUE - 1, Math.min(top, left) + 1);
    				}
    				j++;
    			}
    			j = 0;
    			i++;
    		}
    		for(int k = array.length - 1; k >= 0; k--) {
    			for(int m = array[0].length - 1; m >= 0; m--) {
    				if(array[k][m] != 0 && array[k][m] != 1) {
    					int down = Integer.MAX_VALUE - 1, right = Integer.MAX_VALUE - 1;
    					if(k + 1 < array.length) down = array[k + 1][m];
    					if(m + 1 < array[0].length) right = array[k][m + 1];
    					array[k][m] = Math.min(array[k][m], Math.min(down, right) + 1);
    				}
    			}
    		}
    		for(int[] l : array) {
    			List<Integer> tmp = new LinkedList();
    			for(int n : l) {
    				tmp.add(n);
    			}
    			answer.add(tmp);
    		}
    		return answer;
        }
    

  • 1
    Y

    @qswawrq
    thanks for your great idea. based on your solution optimize some var.

        public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
               List<List<Integer>> ans = new ArrayList<>();
               int m = matrix.size(), n = matrix.get(0).size();
               int[][] res = new int[m][n];
               for(int i = 0; i < m; i++)
                  for(int j = 0; j < n; j++)
                      res[i][j] = (matrix.get(i).get(j) == 0) ? 0 : m+n;
               for(int i = 0; i < m; i++)
                   for(int j = 0; j < n; j++){
                       int left =(j-1 >= 0) ? res[i][j - 1]: res[i][j]; 
                       int top = (i-1 >= 0) ? res[i - 1][j]: res[i][j]; 
    		res[i][j] = Math.min(res[i][j], Math.min(top, left) + 1);
              }
              for(int i = m-1; i >=0 ; i--)
                for(int j = n-1; j >= 0; j--){
                     int right = (j+1 < n) ? res[i][j+1]: res[i][j]; 
                     int down = (i+1 < m) ? res[i+1][j]: res[i][j]; 
    	     res[i][j] = Math.min(res[i][j], Math.min(down, right) + 1);
              }
             for(int i = 0; i < m; i++){
                List<Integer> cur = new ArrayList<>();
                for(int j = 0; j < n; j++)
                    cur.add(res[i][j]);
                ans.add(cur);
             }
        
        return ans;
    }

  • 0

    @yin10
    We can do it in-place without extra space.

    public class Solution {
        public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
            if (matrix ==null || matrix.size() <= 0 || matrix.get(0).size() <= 0) return matrix;
            for (int i=0; i<matrix.size(); i++) {
                for (int j=0; j<matrix.get(i).size(); j++) {
                    if (matrix.get(i).get(j) > 0) {
                        matrix.get(i).set(j, 10000);
                    }
                }
            }
            for (int i=0; i<matrix.size(); i++) {
                for (int j=0; j<matrix.get(i).size(); j++) {
                    int cur = matrix.get(i).get(j);
                    int min = i-1 >=0 ? Math.min( cur, matrix.get(i-1).get(j)) : cur;
                    min = j-1 >=0 ? Math.min( min, matrix.get(i).get(j-1)) : min;
                    matrix.get(i).set(j, Math.min(cur,min+1));
                }
            }
            for (int i=matrix.size()-1; i>=0; i--) {
                for (int j=matrix.get(i).size()-1; j>=0; j--) {
                    int cur = matrix.get(i).get(j);
                    int min = i+1 < matrix.size() ? Math.min( cur, matrix.get(i+1).get(j)) : cur;
                    min = j+1 < matrix.get(i).size() ? Math.min( min, matrix.get(i).get(j+1)) : min;
                    matrix.get(i).set(j, Math.min(cur,min+1));
                }
            }
            return matrix;
        }
    }
    

  • 1

    Just another variation, first doing rows and then doing columns. This way I don't need the "if valid neighbor" checks, I can just start the loops from 1 instead of 0.

    public class Solution {
        public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
            int m = matrix.size(), n = matrix.get(0).size();
            this.matrix = matrix;
            for (List<Integer> row : matrix)
                for (int j = 0; j < n; j++)
                    row.set(j, row.get(j) * 10000);
            for (int i = 0; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    relax(i, j, i, j-1);
                    relax(i, n-1-j, i, n-j);
                }
            }
            for (int j = 0; j < n; j++) {
                for (int i = 1; i < m; i++) {
                    relax(i, j, i-1, j);
                    relax(m-1-i, j, m-i, j);
                }
            }
            return matrix;
        }
        void relax(int i, int j, int i0, int j0) {
            matrix.get(i).set(j, Math.min(matrix.get(i).get(j), matrix.get(i0).get(j0) + 1));
        }
        List<List<Integer>> matrix;
    }
    

    Oh well, since I'm using that helper function already, I can put range checks in there. Doing all four directions together:

    public class Solution {
        public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
            this.matrix = matrix;
            m = matrix.size();
            n = matrix.get(0).size();
            for (List<Integer> row : matrix)
                for (int j = 0; j < n; j++)
                    row.set(j, row.get(j) * 10000);
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    relax(i, j, i, j-1);
                    relax(i, n-1-j, i, n-j);
                    relax(i, j, i-1, j);
                    relax(m-1-i, j, m-i, j);
                }
            }
            return matrix;
        }
        void relax(int i, int j, int i0, int j0) {
            if (i0 >= 0 && i0 < m && j0 >= 0 && j0 < n)
                matrix.get(i).set(j, Math.min(matrix.get(i).get(j), matrix.get(i0).get(j0) + 1));
        }
        List<List<Integer>> matrix;
        int m, n;
    }
    

  • 1
    B

    Same idea.

        public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
            if (matrix.size() == 0 || matrix.get(0).size() == 0)
                return matrix;
            int M = matrix.size(), N = matrix.get(0).size();
            for (int i = 0; i < M; i++)
                for (int j = 0; j < N; j++) {
                    if (matrix.get(i).get(j) == 0)
                        continue;
                    int val = Integer.MAX_VALUE - 1;
                    if (i > 0)
                        val = Math.min(val, matrix.get(i - 1).get(j) + 1);
                    if (j > 0)
                        val = Math.min(val, matrix.get(i).get(j - 1) + 1);
                    matrix.get(i).set(j, val);
                }
    
            for (int i = M - 1; i >= 0; i--)
                for (int j = N - 1; j >= 0; j--) {
                    if (matrix.get(i).get(j) == 0)
                        continue;
                    int val = matrix.get(i).get(j);
                    if (i < M - 1)
                        val = Math.min(val, matrix.get(i + 1).get(j) + 1);
                    if (j < N - 1)
                        val = Math.min(val, matrix.get(i).get(j + 1) + 1);
                    matrix.get(i).set(j, val);
                }
            return matrix;
        }
    

  • 1
    M

    @qswawrq I do not understand why two sweeps are correct. Is it possible the optimal solution comes from top right or bottom left, but not top left or bottom right?


  • 0
    Q

    @meng3 You are right. We can start sweeps from top right and bottom left as well.
    The idea is: I want to know the answer for min(up, left, down, right), but I do not want the recursion relation goes forever. So I compute min(up, left) first, then this part of recursion relation ends at bottom right. After that I do min(right, down) in the second sweep to end the recursion relation at top left. Hope it helps.


  • 7

    I love this one best. Thanks @qswawrq

    public int[][] updateMatrix(int[][] matrix) {
            int row = matrix.length, col = matrix[0].length;
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (matrix[i][j] == 1) {
                        matrix[i][j] = Integer.MAX_VALUE;
                        if (i - 1 >= 0 && matrix[i - 1][j] != Integer.MAX_VALUE) 
                           matrix[i][j] = Math.min(matrix[i][j], 1 + matrix[i - 1][j]);
                        if (j - 1 >= 0 && matrix[i][j - 1] != Integer.MAX_VALUE) 
                          matrix[i][j] = Math.min(matrix[i][j], 1 + matrix[i][j - 1]);
                    }
                }
            }
            for (int i = row - 1; i >= 0; i--) {
                for (int j = col - 1; j >= 0; j--) {
                        if (i + 1 < row && matrix[i + 1][j] != Integer.MAX_VALUE) 
                          matrix[i][j] = Math.min(matrix[i][j], 1 + matrix[i + 1][j]);
                        if (j + 1 < col && matrix[i][j + 1] != Integer.MAX_VALUE) 
                          matrix[i][j] = Math.min(matrix[i][j], 1 + matrix[i][j + 1]);
                }
            }
            return matrix;
        }
    

  • 0
    C

    @meng3 I did it with 4 sweeps too.. but you can experiment it with [[1,1,0],[1,1,1][1,1,1]], and you will find 2 sweeps will give right answer. If 0 lies at top right, the correct value will be able to be brought to each element along the "edges" of two sweeps. This aligns with the property that each path can take at most one turn as stated in another answer.


Log in to reply
 

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