[Leetcode] Unique Paths II

[Problem Link]

  • Total paths ending at [i, j] are 
      Total paths ending at [i+1, j]  +  Total paths ending at [i, j+1]
  • Typically we would keep track of the path we’re on (so as to not go around in circles). However, in this case since we can only move down or right, there is no way we can circle back to a visited cell.
  • Make sure you check for obstacle (and return 0) before checking for end of grid. That way you’ll correctly return 0 for test-case [[1]].
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        return uniquePathsWithObstacles(obstacleGrid, 0, 0, new HashMap<String,Integer>());
    }
 
    public int uniquePathsWithObstacles(int[][] obstacleGrid, int i, int j, Map<String,Integer> memoized) {
 
        if ( i >= obstacleGrid.length || j >= obstacleGrid[0].length )
            return 0;
 
        if ( obstacleGrid[i][j] == 1 )
            return 0;
 
        if ( i == obstacleGrid.length-1 && j == obstacleGrid[0].length-1 )
            return 1;
 
        String key = String.valueOf(i) + "," + String.valueOf(j);
        if (memoized.containsKey(key))
            return memoized.get(key);
 
        int totalPaths = uniquePathsWithObstacles(obstacleGrid, i+1, j, memoized) + 
                    uniquePathsWithObstacles(obstacleGrid, i, j+1, memoized);
        memoized.put(key, totalPaths);
 
        return totalPaths;
    }
}