Unique Paths II

Medium

2 views

Topics:

Dynamic ProgrammingArrays

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 10⁹.

Example 1:

Input: obstacleGrid = [[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

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

Constraints:

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] is 0 or 1.

Unique Paths II

Medium

2 views

Topics:

Dynamic ProgrammingArrays

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 10⁹.

Example 1:

Input: obstacleGrid = [[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

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

Constraints:

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] is 0 or 1.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the dimensions m and n of the grid? What is the maximum size of the grid?
Can the grid be empty (m=0 or n=0)? If so, what should I return?
If the starting cell (top-left) or the ending cell (bottom-right) is an obstacle, what should I return?
Will the obstacleGrid always contain only 0s and 1s, or could there be other values?
If there are no possible paths from the top-left to the bottom-right due to obstacles, what value should I return?

Brute Force Solution

Approach

The brute force method explores every possible route from the starting point to the destination. It's like trying every single path you can think of, one at a time, until you find all the valid routes avoiding obstacles. We will check each route to determine if it is valid.

Here's how the algorithm would work step-by-step:

Start at the top-left corner of the grid.
From your current position, you can only move down or right, so try moving down first.
Then, from that new position, again try moving down or right.
Keep repeating this until you reach the bottom-right corner (the destination).
If, at any point, you hit an obstacle, this path is invalid, so stop and backtrack to the last valid position.
Also backtrack if you go off the grid.
Once you backtrack, try the other possible move (right instead of down, or vice versa) from that last valid position.
Keep track of every single path that successfully reaches the destination without hitting any obstacles or going off the grid.
Count the total number of valid paths found.

Code Implementation

def unique_paths_ii_brute_force(obstacle_grid):
    number_of_rows = len(obstacle_grid)
    number_of_columns = len(obstacle_grid[0])
    path_count = 0

    def traverse_grid(row, column):
        nonlocal path_count

        # If we are out of bounds or on an obstacle, this is an invalid path
        if row < 0 or row >= number_of_rows or column < 0 or column >= number_of_columns or obstacle_grid[row][column] == 1:

            return

        # We found a valid path to the end
        if row == number_of_rows - 1 and column == number_of_columns - 1:
            path_count += 1

            return

        # Explore going down
        traverse_grid(row + 1, column)

        # Explore going right
        traverse_grid(row, column + 1)

    # Start traversal at top-left corner
    traverse_grid(0, 0)

    return path_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^(m+n)) – The brute force approach explores all possible paths, where each path consists of 'm' moves down and 'n' moves right. In the worst case, without any obstacles, the number of paths resembles a binary tree, where each node has two choices (down or right). This leads to an exponential growth in the number of paths explored. Therefore, the time complexity is proportional to the number of possible paths, which is roughly O(2^(m+n)), where 'm' is the number of rows and 'n' is the number of columns. Each path could be of length m+n.

Space Complexity

O(m * n) – The brute force method, as described, implicitly uses a recursion stack to explore each possible path. In the worst-case scenario, the algorithm might explore paths that traverse nearly the entire grid before hitting an obstacle or reaching the destination. The maximum depth of the recursion would then be proportional to the number of rows (m) plus the number of columns (n), representing the maximum steps needed to reach the destination. Each recursive call adds a new frame to the stack, storing function call information. Therefore, the auxiliary space used by the recursion stack is O(m + n), which is equivalent to O(m * n) since we're exploring all paths in the grid.

Optimal Solution

Approach

The problem asks us to find how many different routes exist to reach the end point of a grid, given that some spots are blocked. The clever solution involves building up a table of routes from the start, only considering valid paths. This is a dynamic programming approach, which smartly reuses prior calculations.

Here's how the algorithm would work step-by-step:

Think of each spot in the grid as storing the number of different ways to reach that spot from the beginning.
Start at the top-left corner, which is the beginning: there is one way to reach it (starting there).
Move through the grid. For each spot, the number of ways to reach it is the sum of the ways to reach it from the spot above it and the spot to its left.
If a spot is blocked, there are zero ways to reach it.
Build up this table of 'ways to reach' by going row by row, or column by column. Be careful about the edges of the grid.
The final answer is the number stored in the bottom-right corner, representing the total number of ways to reach the end point.

Code Implementation

def uniquePathsWithObstacles(obstacle_grid):
    grid_height = len(obstacle_grid)
    grid_width = len(obstacle_grid[0])

    # If the start or end has an obstacle, there are no paths.
    if obstacle_grid[0][0] == 1 or obstacle_grid[grid_height - 1][grid_width - 1] == 1:
        return 0

    path_counts = [[0] * grid_width for _ in range(grid_height)]
    path_counts[0][0] = 1

    for row_index in range(grid_height):
        for column_index in range(grid_width):
            if obstacle_grid[row_index][column_index] == 1:
                continue

            # Sum paths from above if not on the top row
            if row_index > 0:
                path_counts[row_index][column_index] += path_counts[row_index - 1][column_index]

            # Sum paths from the left if not on the left most column
            if column_index > 0:
                path_counts[row_index][column_index] += path_counts[row_index][column_index - 1]

    return path_counts[grid_height - 1][grid_width - 1]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each cell of the input grid, where 'm' is the number of rows and 'n' is the number of columns. For each cell, a constant amount of work is performed, such as checking for obstacles and summing values from adjacent cells. Therefore, the time complexity is proportional to the total number of cells in the grid. Thus, the time complexity is O(m*n).

Space Complexity

O(m*n) – The algorithm constructs a table (or grid) to store the number of paths to reach each cell. The size of this table is the same as the input obstacle grid, which has dimensions m rows and n columns, where m is the number of rows and n is the number of columns. Therefore, the auxiliary space used is proportional to m*n. This extra space is used to store the intermediate number of ways to reach each position in the grid. Hence, the space complexity is O(m*n).

Edge Cases

Case	How to Handle
Null or empty obstacleGrid	Return 0 immediately if the input is null or has zero rows/columns because there are no possible paths.
Starting cell is an obstacle	Return 0 immediately since no path can start from an obstacle.
Ending cell is an obstacle	The dynamic programming approach will ensure that the number of paths to the destination cell is 0 if it's an obstacle.
1x1 grid with no obstacle	Return 1 as there is one path which is to stay at the only cell.
All cells are obstacles	Return 0 because there are no valid paths when every cell is blocked.
Obstacle directly blocking the start to end path	The dynamic programming approach will result in 0 paths if the obstacle makes it impossible to reach the destination.
Integer overflow for very large grids	Use a long integer data type instead of int to store the number of paths to prevent overflow.
m x 1 or 1 x n grid with an obstacle	If there's an obstacle in the single path, the number of paths becomes 0; otherwise, it's 1.