Start learning free

LESSON 327 OF 348 · DYNAMIC PROGRAMMING

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

    KOTLIN · DYNAMIC PROGRAMMING

    Unique Paths in Kotlin, explained

    Problem overview

    The function uniquePaths(grid) receives a grid as an Array<IntArray> with n rows and m columns. A 0 is an empty cell and a 1 is an obstacle. A robot starts at the top-left cell and wants to reach the bottom-right cell, moving only down or right. The function returns how many different paths avoid every obstacle. The statement promises that the answer fits in a 32-bit integer and that n and m are at most 100.

    In the example, the 3x3 grid has a single obstacle in the middle, at row 1, column 1. Two paths exist: right, right, down, down along the top and right edges, and down, down, right, right along the left and bottom edges. The answer is 2.

    Approach: count the ways into each cell

    Every path to a cell arrives from the cell above or from the cell to the left. So the number of paths to a cell is the sum of the number of paths to those two neighbours. Let dp[i][j] be the number of paths from (0, 0) to (i, j). Then dp[i][j] = dp[i - 1][j] + dp[i][j - 1] for a free cell, and 0 for an obstacle, since no path may stand on it.

    The first row and the first column have only one neighbour each, so they are filled separately. A cell in the first column is reachable only by going straight down, so it has one path, unless an obstacle sits between it and the start. Once an obstacle blocks the column, every cell below it has no path. The first row works the same way going right.

    Trying every path with recursion would explore a number of paths that grows exponentially. The table touches each cell once.

    Step by step

    1. Read the dimensions. n is grid.size, the number of rows, and m is grid[0].size, the number of columns.
    2. Create dp, an n by m table of zeros.
    3. Fill the first column. Loop i from 0 until n. If grid[i][0] is an obstacle, break: nothing below it can be reached, and those cells keep their 0.
    4. Mark the cell reachable. Otherwise set dp[i][0] = 1, one straight path down from the start. The break already skips this line for a blocked cell, so no else is needed.
    5. Fill the first row the same way with j from 0 until m. Both loops set dp[0][0] when the start is free, which is harmless.
    6. Fill the rest. Loop i from 1 until n and j from 1 until m. The neighbours above and to the left are already computed when a cell is reached.
    7. Skip obstacles. Only when grid[i][j] == 0, set dp[i][j] to the sum of the cell above and the cell to the left. An obstacle cell stays 0.
    8. Return the bottom-right cell, dp[n - 1][m - 1]. If that cell is itself an obstacle, it is still 0, which is the right answer.

    The solution in Kotlin

    class Solution {
    fun uniquePaths(grid: Array<IntArray>): Int {
        val n = grid.size
        val m = grid[0].size
        val dp = Array(n) { IntArray(m) }
        for (i in 0 until n) {
            if (grid[i][0] == 1) {
                break
            }
            dp[i][0] = 1
        }
        for (j in 0 until m) {
            if (grid[0][j] == 1) {
                break
            }
            dp[0][j] = 1
        }
        for (i in 1 until n) {
            for (j in 1 until m) {
                if (grid[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
                }
            }
        }
        return dp[n - 1][m - 1]
    }
}

    The Kotlin details worth a closer look:

    • Array<IntArray>. The grid is an array whose elements are IntArrays, so grid[i][j] reads row i, column j. grid.size counts rows and grid[0].size counts columns. This shape is what Array(n) { IntArray(m) } builds, with the lambda creating a separate row each time.
    • break inside a for. It leaves only the innermost loop it sits in. In the first two loops that is the whole loop, which is what we want. Writing an extra else would be redundant, because the code after the if only runs when the if didn't fire.
    • until versus ... 0 until n stops at n - 1, the last valid index. 0..n would include n and throw ArrayIndexOutOfBoundsException.
    • val table, mutable cells. val dp fixes which array dp names, but its cells can still be assigned.

    Complexity

    Time: O(n * m). Every cell is filled once, and each fill is a constant-time addition.

    Space: O(n * m). The dp table has the same size as the grid. A row-by-row version could keep just one row, but the full table is easier to read.

    Edge cases and common mistakes

    • Obstacle at the start. [[1]] returns 0: the first loop breaks at once, and the bottom-right cell is the start cell.
    • Single free cell. [[0]] returns 1, because the robot is already at the finish.
    • Obstacle at the finish. [[0, 0], [0, 1]] returns 0.
    • A single row or column. [[0, 0, 0, 0]] returns 1, and [[0, 1, 0, 0]] returns 0, since the obstacle cuts the only route. The nested loops never run when there is only one row or column.
    • An open grid. A 3x3 grid of zeros returns 6.
    • Forgetting the break. Without it, cells below a blocked first-column cell would be marked reachable and the counts would be too high. A continue would also be wrong, for the same reason.
    • Overwriting obstacles. If the recurrence runs for a cell with a 1, the table would count paths through the obstacle. The check on grid[i][j] == 0 prevents that.

    Testing

    • The 3x3 grid [[0, 0, 0], [0, 1, 0], [0, 0, 0]] gives 2.
    • [[0, 0, 0], [0, 0, 0], [0, 0, 0]] gives 6.
    • [[0, 1], [0, 0]] gives 1.
    • [[0, 0], [0, 1]] gives 0.
    • [[1]] gives 0, and [[0]] gives 1.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free