Start learning free

LESSON 318 OF 338 · DYNAMIC PROGRAMMING

Unique Paths With Obstacles in Go: Grid Dynamic Programming

Practice O(n * m) Read the full explanation

A robot is located at the top-left corner of a n x m grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any moment of time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider obstacles are placed in some of the grid's cells. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: n and m will be at most 100.

It is guaranteed that the answer can be represented as a 32-bit integer.

Example 1:

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
STEP 1 OF 13
    Ctrl + Enter to check

    GO · DYNAMIC PROGRAMMING

    Unique Paths in Go, explained

    Problem overview

    The function uniquePaths(grid) receives a grid of n rows and m columns. A robot starts in the top-left cell and wants to reach the bottom-right cell, moving only down or right. A cell holding 0 is free and a cell holding 1 is an obstacle the robot can't enter. The function returns the number of different paths.

    In the example the grid is 3 by 3 with a single obstacle in the middle:

    0 0 0
0 1 0
0 0 0

    The robot can go right, right, down, down along the top and right edges, or down, down, right, right along the left and bottom edges. Any path through the center is blocked, so the answer is 2. The notes allow grids up to 100 by 100, and say the answer fits in 32 bits.

    Approach: count the ways to arrive at each cell

    Enumerating every path would take far too long on a 100 by 100 grid, since the number of routes grows explosively. Count them cell by cell instead. Let dp[i][j] be the number of paths from the start (0, 0) to the cell (i, j).

    The robot enters a cell either from the cell above it or from the cell to its left. Those two groups of paths are disjoint, so for a free cell dp[i][j] = dp[i-1][j] + dp[i][j-1]. An obstacle cell has no paths through it, so it stays 0, and the zero flows into its neighbors' sums automatically.

    The recurrence needs a top and a left neighbor, so the first row and the first column are handled separately. A cell in the first column can only be reached by moving straight down, which is possible only if no obstacle lies above it. The same holds for the first row and moving right.

    For the example the finished table is:

    1 1 1
1 0 1
1 1 2

    The bottom-right cell holds the answer, 2. The cell at the bottom right gets 1 from above and 1 from the left.

    Step by step

    1. Read the dimensions: n := len(grid) and m := len(grid[0]). Every row has the same length.
    2. Create dp as an n by m matrix of zeros with the provided makeMatrix.
    3. Fill the first column. Loop i from 0 to n - 1. If grid[i][0] is an obstacle, break: nothing below it can be reached through this column, and those cells keep 0. Otherwise set dp[i][0] = 1, since exactly one path goes straight down.
    4. Fill the first row the same way with j, breaking at the first obstacle and setting dp[0][j] = 1 before it. The corner dp[0][0] is written twice with the same value, which is harmless.
    5. Fill the rest. Loop i from 1 and j from 1. Rows go in increasing order and so do columns, so the top and left neighbors are always done before the cell that needs them.
    6. Skip obstacles. Only when grid[i][j] is 0 apply the recurrence. Otherwise the cell keeps its 0.
    7. Return dp[n-1][m-1].

    The solution in Go

    func uniquePaths(grid [][]int) int {
    n := len(grid)
    m := len(grid[0])
    dp := makeMatrix(n, m)
    for i := 0; i < n; i++ {
        if grid[i][0] == 1 {
            break
        }
        dp[i][0] = 1
    }
    for j := 0; j < m; j++ {
        if grid[0][j] == 1 {
            break
        }
        dp[0][j] = 1
    }
    for i := 1; i < n; i++ {
        for j := 1; j < m; j++ {
            if grid[i][j] == 0 {
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            }
        }
    }
    return dp[n-1][m-1]
}

    Go details worth a closer look:

    • A grid is a slice of slices. [][]int is a slice whose elements are slices, so len(grid) is the number of rows and len(grid[0]) the number of columns of the first row. Rows are allowed to differ in length in Go, which is why the lesson states that they don't.
    • makeMatrix allocates each row with make, which zero-fills it. Allocating only the outer slice would leave nil rows, and indexing into one panics.
    • break inside for ends the loop, not the function. Because the assignment dp[i][0] = 1 comes after the if, a blocked cell never reaches it, so no else is needed.
    • if without parentheses. The condition has no parentheses, and the braces are required even around a single statement.
    • No overflow worries. int is 64 bits here, comfortably above the 32-bit bound the notes give for the answer. A 100 by 100 grid with no obstacles would have about more than 10^58 paths, but the guarantee excludes such inputs.

    Complexity

    Each cell is visited a constant number of times, so the time is O(n * m). The table has n * m cells, so the space is O(n * m). Because a row depends only on the row above, a single row of length m would be enough if memory mattered.

    Edge cases and common mistakes

    • Obstacle on the start. The first loops break at index 0 and write nothing, so all of dp stays 0 and the answer is 0.
    • Obstacle on the finish. The cell is never filled, stays 0, and the function returns 0.
    • Obstacle in the first row or column. Everything past it in that line must stay 0. Setting all of the first row to 1 without the break would count paths that pass through the obstacle.
    • A single cell. A free [[0]] gives 1 and a blocked [[1]] gives 0. The loops over the interior simply don't run.
    • Mixing up n and m. n counts rows and goes with the first index of grid and dp. Swapping them is a common source of index-out-of-range panics on non-square grids.
    • An empty grid. grid[0] would panic when there are no rows. The lesson's inputs always have at least one cell.

    Testing

    For [[0, 1], [0, 0]] the only route is down then right, so the answer is 1. For [[0, 0], [0, 1]] the finish is blocked, so the answer is 0. The 3 by 3 example above gives 2.

    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free