LeetCode Unique Paths Problem Getting The Wrong Answer

Question

I'm doing this problem called "Unique Paths" on a site called leetcode. The problem is: given a 2D matrix with 1s and 0s, a robot starts at the top-left and wants to reach the bottom-right. The robot has only 2 moves: right and down. Also, there are obstacles (represented by a '1'). The robot cannot walk over the obstacles. My program is giving me a wrong answer when I give the input:

Which should output 7, because there are 7 paths from the top left square to the bottom right square. My program outputs 2. My guess is that it only goes all the way down and all the way right, and all the way right and all the way down. However, I don't know the cause of this behaviour, as it looks fine to me. Can anyone tell me why it's doing this? Here is the code:

class Solution {

    int[][] check;

    public int uniquePathsWithObstacles(int[][] grid) {
        if(grid == null || grid.length == 0)
            return 0;

        check = new int[grid.length][grid[0].length];
        return uniquePaths(grid, 0, 0);
    }

    private int uniquePaths(int[][] grid, int x, int y){
        if(x >= grid[0].length || y >= grid.length || grid[y][x] == 1)
            return 0;

        else if(x == grid[0].length - 1 && y == grid.length - 1)
            return 1;

        else if(check[y][x] > 0)
            return check[y][x];

        return grid[y][x] = uniquePaths(grid, x + 1, y) + uniquePaths(grid, x, y + 1);
    }
}

[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173) — Andy Turner, Jul 31 '19 at 22:01
You never assign elements of `check`, do you? What is that for? — Andy Turner, Jul 31 '19 at 22:02
Sorry I just created my account, can you recommend me a better title? — nishantc1527, Jul 31 '19 at 22:05
I use check for memoization. I don't need it, it just makes it much faster. — nishantc1527, Jul 31 '19 at 22:06
You wrote "grid[y][x] = uniquePaths(grid, x + 1, y) + uniquePaths(grid, x, y + 1);" instead of "check[y][x] = blah" and you are returning the number of paths from the last tile you checked instead of from (0,0). — Tassle, Jul 31 '19 at 22:08

score 1 · Accepted Answer · answered Jul 31 '19 at 23:14

For a "better" implementation that doesn't require recursion, start at the lower right.

If you do that, you only need to remember one row (or column), so it's both faster and requires less memory.

Example

Lets use a grid like this. To not confuse with the path-counting arrays below, using symbols instead of numbers to define the grid.

. . . . .
. * * . .
. . . . .
. . . . .

Now build an array for the last row, with how many ways to get the exit from there.

. . . . .   last row from grid
=========
1 1 1 1 1   pathCount from each cell to the end

Repeat that for the row above it. Calculate from the right, and pathCount is the pathCount when going right + pathCount when going down.

. . . . .   3rd row from grid
1 1 1 1 1   result from last row
=========
5 4 3 2 1   result for 3rd row

Since we won't need the last-row values any more when done, we can reuse the array and replace the values inline.

Repeat again. This time we have blocked cells, so setting pathCount of those cells to 0.

. * * . .   2nd row from grid
5 4 3 2 1   result from 3rd row
=========
5 0 0 3 1   result for 2nd row

And finally:

. . . . .   1st row from grid
5 0 0 3 1   result from 2nd row
=========
9 4 4 4 1   result for 1st row

Final result: 9 unique paths from upper-left to lower-right.

Compact implementation using alternate format for the grid for easier testing:

static int countPaths(String... grid) {
    int[] paths = new int[grid[0].length() + 1];
    paths[grid[0].length() - 1] = 1;
    for (int y = grid.length - 1; y >= 0; y--)
        for (int x = grid[0].length() - 1; x >= 0; x--)
            paths[x] = (grid[y].charAt(x) != '0' ? 0 : paths[x] + paths[x + 1]);
    return paths[0];
}

Tests

System.out.println(countPaths("00000",
                              "01100",
                              "00000",
                              "00000")); // prints: 9

System.out.println(countPaths("000",
                              "000",
                              "000")); // prints: 6

LeetCode Unique Paths Problem Getting The Wrong Answer

1 Answers1

Linked