Start learning free

LESSON 352 OF 415 · DYNAMIC PROGRAMMING

Unique Paths With Obstacles in Swift: 2D 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

    SWIFT · DYNAMIC PROGRAMMING

    Unique Paths in Swift, explained

    Problem overview

    The method uniquePaths(_ grid: [[Int]]) 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. In the grid, 1 marks an obstacle and 0 a free cell. The method returns how many different paths avoid every obstacle. The notes say n and m are at most 100 and the answer fits in 32 bits.

    For the 3 by 3 grid with a single obstacle in the middle, the answer is 2: right, right, down, down, or down, down, right, right. Any path through the center is blocked.

    Approach: paths into a cell come from two neighbours

    Because the robot moves only down or right, the last step into a cell (i, j) came either from the cell above, (i - 1, j), or from the cell to the left, (i, j - 1). Let dp[i][j] be the number of paths from (0, 0) to (i, j). Then, for a free cell,

    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    An obstacle cell has 0 paths, since nothing can stand on it. The first row and first column are special because they have only one neighbour: each cell there can be reached in exactly one way (straight along the edge), unless an obstacle cuts the edge. After an obstacle in the first column, every cell below it is unreachable; the same applies to the first row and the cells to its right.

    For the example, the table comes out as:

    1 1 1
1 0 1
1 1 2

    The center is 0 because of the obstacle, and the bottom-right cell adds the 1 above and the 1 to the left.

    Step by step

    1. Read the dimensions. Store grid.count in n (rows) and grid[0].count in m (columns), both with let.
    2. Create the table as a var, n rows of m zeros.
    3. Fill the first column. Loop i over 0..<n.
    4. Stop at an obstacle. If grid[i][0] == 1, break. Everything below stays 0.
    5. Otherwise set dp[i][0] = 1: one way to get here, straight down.
    6. Fill the first row the same way, with j over 0..<m.
    7. Stop at an obstacle in the row with break.
    8. Otherwise set dp[0][j] = 1. The start cell is written by both loops when it is free, which is harmless.
    9. Fill the rest. Loop i over 1..<n and, inside it, j over 1..<m.
    10. Skip obstacles. Only when grid[i][j] == 0 do we compute anything. Obstacle cells keep their 0.
    11. Apply the recurrence: add the cell above and the cell to the left.
    12. Return dp[n - 1][m - 1]. If the target itself is an obstacle, it is still 0, which is correct.

    The solution in Swift

    class Solution {
    func uniquePaths(_ grid: [[Int]]) -> Int {
        let n = grid.count
        let m = grid[0].count
        var dp = [[Int]](repeating: [Int](repeating: 0, count: m), count: n)
        for i in 0..<n {
            if grid[i][0] == 1 {
                break
            }
            dp[i][0] = 1
        }
        for j in 0..<m {
            if grid[0][j] == 1 {
                break
            }
            dp[0][j] = 1
        }
        for i in 1..<n {
            for j in 1..<m {
                if grid[i][j] == 0 {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
                }
            }
        }
        return dp[n - 1][m - 1]
    }
}

    Swift details worth knowing:

    • Nested arrays are arrays of values. grid is a [[Int]]: an array whose elements are arrays. grid[i][j] reads row i and then element j of it. The method only reads grid, so it needs no copy of the input.
    • break in a for loop. It leaves the innermost loop right away. Since the assignment dp[i][0] = 1 comes after the if, a blocked cell is never written, and no else is needed.
    • Ranges at the edges. For a one-row or one-column grid, 1..<n or 1..<m is 1..<1, an empty range, so the loops are skipped and the first row or column gives the answer. A range whose lower bound is above its upper bound would crash; none can occur here for a non-empty grid.
    • Empty input. grid[0] crashes on an empty array, because Swift checks every index. The method assumes at least one row.
    • Overflow. Int is 64 bits and an overflowing addition crashes instead of wrapping. With grids of at most 100 by 100 and the notes' promise about the answer, that is not a concern for valid tests.

    Complexity

    Time: O(n * m). Each cell is computed once with a constant amount of work.

    Space: O(n * m). The table has as many cells as the grid. Each row depends only on the row above, so a single row would suffice.

    Edge cases and common mistakes

    • Obstacle at the start. For [[1, 0], [0, 0]] the first loop breaks at i = 0, the second at j = 0, the table stays zero and the answer is 0. Paths can't start on an obstacle.
    • Obstacle at the end. The cell is never filled, so the answer is 0. For [[0, 0], [0, 1]] the result is 0.
    • A single free cell. [[0]] gives 1: the robot is already at the finish.
    • One row. [[0, 0, 0]] gives 1, and an obstacle in it makes the answer 0.
    • Not stopping at an obstacle on the edge. A loop that skips the obstacle but keeps filling would mark cells past it as reachable. For [[0], [1], [0]] the last cell must be 0, because the obstacle blocks the only route.
    • Open grid. A 2 by 2 grid without obstacles gives 2.

    Testing

    • [[0, 0, 0], [0, 1, 0], [0, 0, 0]] gives 2.
    • [[0, 0], [0, 0]] gives 2.
    • [[1, 0], [0, 0]] gives 0.
    • [[0, 0], [0, 1]] gives 0.
    • [[0]] gives 1.
    • [[0], [1], [0]] gives 0.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free