LeetCode 63: Unique Paths II Solution
Master LeetCode problem 63 (Unique Paths II), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
63. Unique Paths II
Problem Explanation
Explanation:
To solve this problem, we can use dynamic programming. We will create a 2D array to store the number of unique paths to reach each cell. We will initialize the top-left cell with 1 since there is only one way to reach it. Then, we will iterate over the grid, updating the number of paths for each cell based on the cells to the left and above it, considering the obstacle conditions.
Algorithmic Steps:
- Initialize a 2D dp array of size m x n to store the number of unique paths to reach each cell.
- Initialize the top-left cell of dp to 1.
- Iterate over the grid:
- If the current cell is an obstacle, set the number of paths in dp to 0.
- Otherwise, update the number of paths in dp based on the cells to the left and above it.
- Return the number of unique paths to the bottom-right corner.
Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the grid. Space Complexity: O(m * n) for the dp array.
:
Solution Code
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
} else if (i == 0 && j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = (i > 0 ? dp[i - 1][j] : 0) + (j > 0 ? dp[i][j - 1] : 0);
}
}
}
return dp[m - 1][n - 1];
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 63 (Unique Paths II)?
This page provides optimized solutions for LeetCode problem 63 (Unique Paths II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 63 (Unique Paths II)?
The time complexity for LeetCode 63 (Unique Paths II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 63 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 63 in Java, C++, or Python.