Why Memoization is not working??? Please help!
Anonymous User
55
JavaInterview

Question: Unique Paths ii

Without Memoization answer is correct, but getting TLE

class Solution {
    int count = 0;
    
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null) {
            return 0;
        }
        
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        if (obstacleGrid[m - 1][n - 1] != 0) {
            return 0;
        }
        
        dfs(obstacleGrid, 0, 0);
        return count;
    }
    
    private void dfs(int[][] grid, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 1) {
            return;
        }
        
        if (r == grid.length - 1 && c == grid[0].length - 1) {
            count++;
            return;
        }
        
        grid[r][c] = 1;
        
        dfs(grid, r + 1, c);
        dfs(grid, r, c + 1);
        
        grid[r][c] = 0;
    }
}

With Memoization, answer is incorrect

class Solution {
    int count = 0;
    Integer[][] dp;
    
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null) {
            return 0;
        }
        
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
    
        dp = new Integer[m][n];
        
        if (obstacleGrid[m - 1][n - 1] != 0) {
            return 0;
        }
        
        dfs(obstacleGrid, 0, 0);
        return count;
    }
    
    private void dfs(int[][] grid, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 1) {
            return;
        }
        
        if (dp[r][c] != null) {
            return;
        }
        
        if (r == grid.length - 1 && c == grid[0].length - 1) {
            count++;
            dp[r][c] = count;
            return;
        }
        
        grid[r][c] = 1;
        
        dfs(grid, r + 1, c);
        dfs(grid, r, c + 1);
        
        grid[r][c] = 0;
    }
}

Can someone please help why memoization is giving wrong output and what is the correct way to use memoization in these type of questions!?

Comments (0)