Top down approach 01 Matrix

user_4446662 0
Viewed 34

I new do dynamic programming and I am attempting the following problem on leetcode: 01 Matrix

Problem: Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1.

enter image description here

I have attempted the problem using top-down dynamic programming but cannot seem to get the right answer for all the test cases. In all most all cases, the matrix is almost optimized except for a few values. My algorithm entails finding a '1' and then doing a depth first search in all 4 directions and then taking the minimum of the values + 1 and saving that to the memoization table (ans[][]).

I have tried to search for a top down approach but all most all the solutions are bottom up. Can anyone please help me understand why taking the minimum of the steps in all 4 directions using memoization doesn't not yield an optimal solution or what my solution is missing?

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] ans = new int[m][n];
        for(int i = 0; i <m; i++){
            for(int j = 0; j <n; j++){
                if(mat[i][j] == 0){
                    ans[i][j] = 0;
                }
                else{
                    ans[i][j] = -1;
                }
            }
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(ans[i][j] == - 1){
                    boolean[][] visited = new boolean[m][n];
                    ans[i][j] = dfs(i, j, m, n, mat, ans, visited);
                }
            }
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                    boolean[][] visited = new boolean[m][n];
                    ans[i][j] = Math.min(ans[i][j], dfs(i, j, m, n, mat, ans, visited));
            }
        }
        return ans;
    }
    
    public int dfs(int i, int j, int m, int n, int[][]mat, int[][] ans, boolean[][] visited){
        if(i >= m || i < 0 || j >=n || j < 0|| visited[i][j]){
            return Integer.MAX_VALUE;
        }
        if(mat[i][j] == 0){
            return 0;
        }
        if(ans[i][j] != -1){
            return ans[i][j];
        }
        visited[i][j] = true;
        int up =  dfs(i - 1, j, m, n, mat, ans, visited);
        int down = dfs(i + 1, j, m, n, mat, ans, visited);
        int left = dfs( i, j - 1, m, n, mat, ans, visited);
        int right = dfs(i, j + 1, m, n, mat, ans,visited);
        visited[i][j] = false;
        
        ans[i][j] = Math.min (up, Math.min(down, Math.min(left, right))) + 1;
        return ans[i][j];
    }
}
dynamic-programming graph matrix algorithm
2 Answers

The 3 double-loops at the beginning could be reduced to one double-loop, the 3rd one seems to be completely superfluous. Dfs is not working here. E.g. you will go 4 fields up 1 left and 4 fields down and save 9 but actually that field could be reached in 1 step to the left, you just ignore it because you already have a result. Even if you would fix the problems, this is still O((nm)^2) instead of O(nm). For an O(nm) solution you can initialize the result with 0 where you have a 0, with -1 where there is no 0 next to it and 1 where you have a 1 with a 0 next to it, additionally add the position of this 1 to a list. Initialize c to 2. Go through the list and check the positions up, left, right and down, if it is a -1 in the result replace it by c and add this position to a new list. Replace the list by the new list, increment c and go through the list again and again until it is empty.

user_47851100

There is also a working DFS implementation that is easier to understand:

https://leetcode.com/problems/01-matrix/discuss/732601/DFS-O(1)-Space

class Solution {
public int[][] updateMatrix(int[][] dist) {
        int m = dist.length;
        int n = dist[0].length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][j] != 0) {
                    dist[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][j] == 0) {
                    dfs(dist, i - 1, j, 1);
                    dfs(dist, i + 1, j, 1);
                    dfs(dist, i, j - 1, 1);
                    dfs(dist, i, j + 1, 1); 
                }
            }
        }
        
        return dist;
    }
    
    private void dfs(int[][] dist, int i, int j, int value) {
        if (i >= 0 && i < dist.length && j >= 0 && j < dist[0].length && value < dist[i][j]) {
            dist[i][j] = value;
            dfs(dist, i - 1, j, value + 1);
            dfs(dist, i + 1, j, value + 1);
            dfs(dist, i, j - 1, value + 1);
            dfs(dist, i, j + 1, value + 1); 
        }
    }
}
user_44466620
Related