Coding

Unique paths II

Asked at

Amazon

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an m x n 2d array named matrix, where each cell is either 0 or 1. Return the number of unique ways to go from the top-left cell (matrix[0][0]) to the bottom-right cell (matrix[m-1][n-1]). A cell is blocked if its value is 1, and no path is possible through that cell.

Movement is allowed in only two directions from a cell - right and bottom.

Input: matrix = [[0, 0, 0], [0, 1, 0], [0, 0, 0]] Output: 2 Explanation: The two possible paths are:

down -> down-> right -> right
right -> right -> down -> down

Input: matrix = [[0, 0, 0], [0, 0, 1], [0, 1, 0]] Output: 0 Explanation: There is no way to reach the bottom-right cell.

Input: matrix = [[0, 0, 0, 0], [0, 0, 1, 0]]

m == number of rows in matrix
n == number of columns in matrix
1 <= n, m <= 100
Value of each cell in matrix is either 0 or 1
The answer will not exceed 109

cpp

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& matrix) {

    }
};

java

class Solution {
    public int uniquePathsWithObstacles(int[][] matrix) {

    }
}

python

class Solution:
    def uniquePathsWithObstacles(self, matrix):

javascript

class Solution {
    uniquePathsWithObstacles(matrix) {

    }
}

csharp

public class Solution {
    public int UniquePathsWithObstacles(int[][] matrix) {
        
    }
}

func uniquePathsWithObstacles(matrix [][]int) int {

}

Stuck? Show a way to structure it+

01Let dp[j] represent paths to column j in the current row.
02Set dp[j] to zero at blocked cells.
03Otherwise add paths from above and left, with dp[0] initialized from the start cell.
04Zero blocked cells immediately so no path count flows through an obstacle.

Reference answer

Use a one-dimensional array dp of length n, where before processing a cell dp[j] contains paths from above and dp[j - 1] contains paths from the left. Initialize dp[0] = 1 only if the starting cell is open. Scan rows and columns. If matrix[i][j] is blocked, set dp[j] = 0 because no path may end there. Otherwise, for j > 0, update dp[j] += dp[j - 1]. The existing dp[j] is the count from above, so the addition implements the two allowed incoming directions. The answer is the final dp[n - 1]. Time is O(mn) and extra space is O(n). This handles a blocked start or destination naturally. If counts may exceed the numeric range, use the required modulo or a wider integer type according to the specification.

Then expect these follow-ups

How would you reconstruct one valid path?
Tests: reconstruction
What changes if movement in four directions is allowed?
Tests: algorithm selection

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question