onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

Dynamic Programming (2D) - Complex approach
Dynamic Programming (1D) - Complex approach
In-place Dynamic Programming - Complex approach

Approach 1: Dynamic Programming (2D)

This problem is an extension of the "Unique Paths" problem, with the addition of obstacles. We can still use dynamic programming to solve it, but we need to handle the obstacles differently.

Let's define dp[i][j] as the number of unique paths to reach the cell at position (i, j) from the top-left corner (0, 0).

The key insight is that if a cell contains an obstacle (obstacleGrid[i][j] == 1), then the number of ways to reach that cell is 0. For non-obstacle cells, the recurrence relation is the same as in "Unique Paths":

dp[i][j] = dp[i-1][j] + dp[i][j-1] if obstacleGrid[i][j] == 0

dp[i][j] = 0 if obstacleGrid[i][j] == 1

For the base cases, we need to handle the first row and first column differently:

For the first row (i = 0), dp[0][j] = dp[0][j-1] if obstacleGrid[0][j] == 0, and dp[0][j] = 0 if obstacleGrid[0][j] == 1.
For the first column (j = 0), dp[i][0] = dp[i-1][0] if obstacleGrid[i][0] == 0, and dp[i][0] = 0 if obstacleGrid[i][0] == 1.

Additionally, we need to handle the starting cell (0, 0) specially:

dp[0][0] = 1 if obstacleGrid[0][0] == 0, and dp[0][0] = 0 if obstacleGrid[0][0] == 1.

The final answer is dp[m-1][n-1], which represents the number of unique paths to reach the bottom-right corner.

Algorithm:

Initialize a 2D DP array dp of size m × n, where dp[i][j] represents the number of unique paths to reach the cell at position (i, j).
Set the base case for the starting cell: dp[0][0] = 1 if obstacleGrid[0][0] == 0, and dp[0][0] = 0 if obstacleGrid[0][0] == 1.
For the first row (i = 0), set dp[0][j] = dp[0][j-1] if obstacleGrid[0][j] == 0, and dp[0][j] = 0 if obstacleGrid[0][j] == 1.
For the first column (j = 0), set dp[i][0] = dp[i-1][0] if obstacleGrid[i][0] == 0, and dp[i][0] = 0 if obstacleGrid[i][0] == 1.
For each cell (i, j) where i > 0 and j > 0, set dp[i][j] = dp[i-1][j] + dp[i][j-1] if obstacleGrid[i][j] == 0, and dp[i][j] = 0 if obstacleGrid[i][j] == 1.
Return dp[m-1][n-1], which represents the number of unique paths to reach the bottom-right corner.

Time Complexity:

O(m * n)

We need to fill in the DP table of size m × n, and each cell takes constant time to compute.

Space Complexity:

O(m * n)

We use a 2D DP array of size m × n to store the number of unique paths for each cell.

Approach 2: Dynamic Programming (1D)

We can optimize the space complexity of the dynamic programming approach by using a 1D array instead of a 2D array, similar to the optimization in the "Unique Paths" problem.

The key observation is that when we're calculating dp[i][j], we only need the values from the current row and the row above it. Specifically, we need dp[i-1][j] and dp[i][j-1].

If we use a 1D array dp where dp[j] represents the number of unique paths to reach the cell at position (i, j), then:

Before the update, dp[j] represents the number of unique paths to reach the cell at position (i-1, j).
After updating dp[j-1], dp[j-1] represents the number of unique paths to reach the cell at position (i, j-1).

So, the recurrence relation becomes:

dp[j] = dp[j] + dp[j-1] if obstacleGrid[i][j] == 0

dp[j] = 0 if obstacleGrid[i][j] == 1

We initialize the 1D array based on the first row of the obstacle grid, and then update it row by row.

The final answer is dp[n-1], which represents the number of unique paths to reach the bottom-right corner.

Algorithm:

Initialize a 1D DP array dp of size n, where dp[j] represents the number of unique paths to reach the cell at position (i, j).
Set the base case for the starting cell: dp[0] = 1 if obstacleGrid[0][0] == 0, and dp[0] = 0 if obstacleGrid[0][0] == 1.
For the first row (i = 0), set dp[j] = dp[j-1] if obstacleGrid[0][j] == 0, and dp[j] = 0 if obstacleGrid[0][j] == 1.
For each row i from 1 to m-1:
a. If obstacleGrid[i][0] == 1, set dp[0] = 0.
b. For each column j from 1 to n-1:
i. If obstacleGrid[i][j] == 1, set dp[j] = 0.
ii. Otherwise, update dp[j] = dp[j] + dp[j-1].
Return dp[n-1], which represents the number of unique paths to reach the bottom-right corner.

Time Complexity:

O(m * n)

We still need to process each cell in the grid, which takes O(m * n) time.

Space Complexity:

O(n)

We only use a 1D array of size n to store the number of unique paths for the current row.

Approach 3: In-place Dynamic Programming

We can further optimize the space complexity by using the input grid itself to store the DP values, thus avoiding the need for an additional array.

The key idea is to reuse the obstacleGrid array to store the number of unique paths to reach each cell. We'll modify the array in-place:

If obstacleGrid[i][j] == 1 (obstacle), we set obstacleGrid[i][j] = 0 (no paths).
If obstacleGrid[i][j] == 0 (no obstacle), we calculate the number of paths using the recurrence relation and store it in obstacleGrid[i][j].

However, there's a complication: we need to distinguish between cells that are obstacles (which should have 0 paths) and cells that have 0 paths because they can't be reached. To handle this, we can first preprocess the grid to mark all obstacles as -1, and then apply the DP algorithm.

Alternatively, we can directly modify the grid without preprocessing, by carefully handling the base cases and the recurrence relation.

Note that this approach modifies the input grid, which might not be desirable in all situations. If preserving the input is important, we should use one of the previous approaches.

Algorithm:

For the starting cell (0, 0), set obstacleGrid[0][0] = 1 - obstacleGrid[0][0] (1 if no obstacle, 0 if obstacle).
For the first row (i = 0), set obstacleGrid[0][j] = obstacleGrid[0][j-1] if obstacleGrid[0][j] == 0, and obstacleGrid[0][j] = 0 if obstacleGrid[0][j] == 1.
For the first column (j = 0), set obstacleGrid[i][0] = obstacleGrid[i-1][0] if obstacleGrid[i][0] == 0, and obstacleGrid[i][0] = 0 if obstacleGrid[i][0] == 1.
For each cell (i, j) where i > 0 and j > 0:
a. If obstacleGrid[i][j] == 1 (obstacle), set obstacleGrid[i][j] = 0 (no paths).
b. Otherwise, set obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1].
Return obstacleGrid[m-1][n-1], which represents the number of unique paths to reach the bottom-right corner.

Time Complexity:

O(m * n)

We still need to process each cell in the grid, which takes O(m * n) time.

Space Complexity:

O(1)

We use the input grid itself to store the DP values, so we don't need any additional space beyond the input.

Pseudocode

solution.pseudo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function uniquePathsWithObstacles(obstacleGrid):
    m = obstacleGrid.length
    n = obstacleGrid[0].length
 
    // Initialize DP array
    dp = new 2D array of size m × n, initialized with 0
 
    // Set base case for starting cell
    if obstacleGrid[0][0] == 0:
        dp[0][0] = 1
    else:
        dp[0][0] = 0
 
    // Set base cases for first row
    for j from 1 to n-1:
        if obstacleGrid[0][j] == 0:
            dp[0][j] = dp[0][j-1]
        else:
            dp[0][j] = 0
 
    // Set base cases for first column
    for i from 1 to m-1:
        if obstacleGrid[i][0] == 0:
            dp[i][0] = dp[i-1][0]
        else:
            dp[i][0] = 0
 
    // Fill DP array
    for i from 1 to m-1:
        for j from 1 to n-1:
            if obstacleGrid[i][j] == 0:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            else:
                dp[i][j] = 0
 
    return dp[m-1][n-1]

Previous Next

String Problems

Palindrome Checker

Determine if a string reads the same forward and backward.

EasyString Manipulation

Message Encryption

Reverse a string to create a simple encryption system.

EasyString Manipulation

Word Puzzle Challenge

Check if two strings are anagrams of each other.

EasyString Manipulation

Learning Objective

Understand different approaches to solve the unique paths ii problem and analyze their efficiency.