Unique paths II
AmazonThe 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) {
}
}go
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
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
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question