Start learning free

LESSON 351 OF 414 · DYNAMIC PROGRAMMING

Unique Paths With Obstacles in Scala: 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

    SCALA · DYNAMIC PROGRAMMING

    Unique Paths in Scala, explained

    Problem overview

    The method uniquePaths(grid) receives an n by m grid as an Array[Array[Int]]. A 0 is an empty cell and a 1 is an obstacle. A robot starts in the top-left corner and wants to reach the bottom-right corner, moving only down or right, and never entering an obstacle. The method returns how many different paths exist. The size is at most 100 by 100, and the answer is guaranteed to fit in an Int.

    In the example, a 3 by 3 grid has a single obstacle in the middle. The robot can go right, right, down, down, or down, down, right, right, so the answer is 2.

    Approach: count the ways into every cell

    Let dp(i)(j) be the number of paths from the start to cell (i, j). A robot that moves only down or right enters a cell either from the cell above or from the cell to the left, and no path is counted in both. 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 keeps 0. The first row and first column are special because they have only one neighbour: a cell in the first column can only be reached by going straight down, and a cell in the first row only by going straight right. Such a cell has exactly one path, unless an obstacle sits between it and the start. A single obstacle in the first column cuts off every cell below it.

    For the example grid the table is:

    1  1  1
1  0  1
1  1  2

    The middle cell is an obstacle and stays 0. The bottom-right cell is 1 + 1, the paths coming from the cell above and from the cell on the left.

    Step by step

    1. Read the dimensions: n is grid.length (rows) and m is grid(0).length (columns).
    2. Create dp with Array.ofDim[Int](n, m), an n by m table of zeros.
    3. Fill the first column. Scala has no break keyword, so the loop sits inside a breakable block and calls break() when it reaches an obstacle. The cells below keep their zeros. Otherwise it sets dp(i)(0) = 1.
    4. Fill the first row in the same way, going over j in 0 until m. The cell at the start is set to 1 by both loops when it is free, which is harmless.
    5. Fill the rest. Loop over 1 until n and 1 until m. Row 0 and column 0 are done, so the recurrence starts at 1.
    6. Skip obstacles. Only a cell with grid(i)(j) == 0 gets a value.
    7. Apply the recurrence from the cell above and the cell to the left.
    8. Return the bottom-right cell, dp(n - 1)(m - 1). If that cell is an obstacle it was never assigned, so it is 0, which is the correct answer.

    The solution in Scala

    class Solution {
    def uniquePaths(grid: Array[Array[Int]]): Int = {
        val n = grid.length
        val m = grid(0).length
        val dp = Array.ofDim[Int](n, m)
        breakable {
            for (i <- 0 until n) {
                if (grid(i)(0) == 1) {
                    break()
                }
                dp(i)(0) = 1
            }
        }
        breakable {
            for (j <- 0 until m) {
                if (grid(0)(j) == 1) {
                    break()
                }
                dp(0)(j) = 1
            }
        }
        for (i <- 1 until n) {
            for (j <- 1 until m) {
                if (grid(i)(j) == 0) {
                    dp(i)(j) = dp(i - 1)(j) + dp(i)(j - 1)
                }
            }
        }
        dp(n - 1)(m - 1)
    }
}

    Some Scala details in this code:

    • breakable and break() come from scala.util.control.Breaks. In a standalone file you add import scala.util.control.Breaks.* at the top (Scala 3 syntax). break() works by throwing a control exception that the enclosing breakable catches, so the loop must be inside the block.
    • A for loop is a method call. for (i <- 0 until n) { ... } turns into foreach with a function, which is why leaving the loop early takes an exception. A while loop with a flag is an alternative that avoids it.
    • Two-dimensional arrays. Array.ofDim[Int](n, m) builds n separate rows of m zeros. You read a cell with dp(i)(j): the first call gets a row, the second gets a cell of it.
    • grid(0).length is the length of the first row. It assumes all the rows have the same length, which a rectangular grid guarantees.
    • The result is the last expression. dp(n - 1)(m - 1) needs no return.

    Complexity

    Let the grid have n rows and m columns.

    Time: O(n * m). Each cell is handled a constant number of times.

    Space: O(n * m). The dp table is the size of the grid. Each row depends only on the row above, so a single row would be enough.

    Edge cases and common mistakes

    • Obstacle at the start or the end. If the start cell is an obstacle, both edge loops break at once and the whole table stays 0. If the end cell is an obstacle, it is never assigned. Either way the answer is 0.
    • Obstacle in the first row or column. For [[0, 0], [1, 0], [0, 0]] the first column is blocked at row 1, so only the path along the top row and down the right side exists, and the answer is 1. Without the break(), the bottom-left cell would wrongly get a 1 and the answer would be 2.
    • A single cell. [[0]] gives 1 and [[1]] gives 0.
    • One row or one column. [[0, 0, 0, 0]] gives 1, and [[0, 1, 0, 0]] gives 0. The nested loop for the rest of the grid doesn't run at all.
    • Mixing up rows and columns. The grid is indexed grid(row)(column). Using grid(0).length for n would swap the sizes and fail on a non-square grid.
    • Overflow. The guarantee in the statement keeps the answer inside an Int. An obstacle-free 17 by 17 grid has 601,080,390 paths, which still fits, and larger grids need a Long.
    • Empty grid. grid(0) throws an ArrayIndexOutOfBoundsException when there are no rows. The lesson's input always has at least one cell.
    • Forgetting the obstacle test in the main loop. The recurrence would give an obstacle cell a positive count, and paths would pass through it.

    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, 0], [1, 0], [0, 0]] gives 1.
    • [[0]] gives 1.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free