What is the time complexity of Unique Paths II?

The optimal solution has a time complexity of O(m*n).

What data structures are used to solve Unique Paths II?

This problem uses Array, Dynamic Programming, Matrix. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Unique Paths II?

Insight 1: Dynamic Programming: The number of ways to reach a cell is the sum of the number of ways to reach the cell above it and the number of ways to reach the cell to its left. Insight 2: Obstacle Handling: If a cell contains an obstacle, the number of paths to reach that cell is 0.

Which companies ask LeetCode 63. Unique Paths II in interviews?

This problem is frequently asked at Adobe, Agoda, Amazon, Apple, Atlassian and 13 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Unique Paths II - LeetCode 63 Solution

Unique Paths II - Complete Solution Guide

Unique Paths II is LeetCode problem 63, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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-ri

Detailed Explanation

The problem asks us to find the number of unique paths a robot can take from the top-left corner to the bottom-right corner of an m x n grid. The robot can only move down or right. The grid contains obstacles marked as '1', which the robot cannot step on. The goal is to return the count of paths avoiding the obstacles.

Solution Approach

The provided code utilizes dynamic programming with space optimization. It creates a 1D array `dp` of size `n` to store the number of paths to reach each cell in the current row. The algorithm iterates through the grid row by row and column by column. If a cell contains an obstacle, the corresponding `dp` value is set to 0. Otherwise, the `dp` value is updated by adding the `dp` value of the cell to its left (if it exists). The initial `dp[0]` is set to 1, representing the starting point.

Step-by-Step Algorithm

Step 1: Initialize a 1D array `dp` of size `n` with all elements set to 0. Set `dp[0]` to 1, indicating one way to reach the starting cell (top-left). If the starting cell has an obstacle, return 0 immediately.
Step 2: Iterate through each row `i` from 0 to `m-1` of the grid.
Step 3: Inside each row, iterate through each column `j` from 0 to `n-1`.
Step 4: If the current cell `obstacleGrid[i][j]` is an obstacle (value is 1), set `dp[j]` to 0, indicating no path can reach this cell.
Step 5: If the current cell is not an obstacle and `j > 0`, update `dp[j]` by adding `dp[j-1]` to it. This represents adding the number of paths from the left cell to the current cell's path count.
Step 6: After iterating through all rows and columns, `dp[n-1]` will contain the number of unique paths to reach the bottom-right corner. Return this value.

Key Insights

Insight 1: Dynamic Programming: The number of ways to reach a cell is the sum of the number of ways to reach the cell above it and the number of ways to reach the cell to its left.
Insight 2: Obstacle Handling: If a cell contains an obstacle, the number of paths to reach that cell is 0.
Insight 3: Space Optimization: We can solve this problem using O(n) space instead of O(m*n) by only storing the current row's path counts.

Complexity Analysis

Time Complexity: O(m*n)

Space Complexity: O(n)

Topics

This problem involves: Array, Dynamic Programming, Matrix.

Companies

Asked at: Adobe, Agoda, Amazon, Apple, Atlassian, Bloomberg, Cisco, Coupang, Cruise, Flipkart, Meta, Microsoft, Pinterest, Uber, Yahoo, Zepto, Zomato, athenahealth.

Unique Paths II | LeetCode 63

Medium

Array Dynamic Programming Matrix

Time: O(m*n)Space: O(n)

Solution Code

Available in:

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        if (obstacleGrid[0][0] == 1) {
            return 0;
        }

        int[] dp = new int[n];
        dp[0] = 1;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                } else if (j > 0) {
                    dp[j] += dp[j - 1];
                }
            }
        }

        return dp[n - 1];
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 63: Unique Paths II - Detailed explanation and solution approaches.

Topics

Array Dynamic Programming Matrix

Companies

AdobeAgodaAmazonAppleAtlassianBloombergCiscoCoupang

Stats

Difficulty:Medium

Languages:4

Companies:18

Problem #:63

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize a 1D array `dp` of size `n` with all elements set to 0. Set `dp[0]` to 1, indicating one way to reach the starting cell (top-left). If the starting cell has an obstacle, return 0 immediately.
2
Step 2: Iterate through each row `i` from 0 to `m-1` of the grid.
3
Step 3: Inside each row, iterate through each column `j` from 0 to `n-1`.
4
Step 4: If the current cell `obstacleGrid[i][j]` is an obstacle (value is 1), set `dp[j]` to 0, indicating no path can reach this cell.
5
Step 5: If the current cell is not an obstacle and `j > 0`, update `dp[j]` by adding `dp[j-1]` to it. This represents adding the number of paths from the left cell to the current cell's path count.
6
Step 6: After iterating through all rows and columns, `dp[n-1]` will contain the number of unique paths to reach the bottom-right corner. Return this value.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(m*n)

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The algorithm iterates through each cell of the `m x n` grid once, resulting in O(m*n) time complexity. It uses a 1D array `dp` of size `n` to store the path counts, resulting in O(n) space complexity.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

2D Dynamic Programming

Use a 2D array dp[m][n] to store the number of paths to reach each cell. dp[i][j] = dp[i-1][j] + dp[i][j-1] if obstacleGrid[i][j] == 0 else 0. Initialize the first row and first column accordingly.

Time: O(m*n)Space: O(m*n)

Trade-offs: Easier to understand and implement, but uses more space than the optimized 1D DP approach. Use it when memory is not a constraint and clarity is preferred.

Recursion with Memoization

A recursive approach combined with memoization to avoid redundant calculations. Define a recursive function that calculates the number of paths to reach a cell (i, j) based on the paths to reach (i-1, j) and (i, j-1). Use a memoization table to store the results of the recursive calls.

Time: O(m*n)Space: O(m*n) due to the memoization table and recursion stack.

Trade-offs: Can be less intuitive than DP, and the overhead of recursion might be slower in practice. Useful for understanding the problem conceptually but not recommended for optimized solutions.

✨

Key Insights

1Insight 1: Dynamic Programming: The number of ways to reach a cell is the sum of the number of ways to reach the cell above it and the number of ways to reach the cell to its left.
2Insight 2: Obstacle Handling: If a cell contains an obstacle, the number of paths to reach that cell is 0.
3Insight 3: Space Optimization: We can solve this problem using O(n) space instead of O(m*n) by only storing the current row's path counts.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Edge Cases

Edge case 1: Starting cell has obstacle: If `obstacleGrid[0][0] == 1`, there are no paths possible, so the code returns 0 immediately.
Edge case 2: Obstacle in last cell: The algorithm correctly handles cases where the bottom-right cell has an obstacle by setting the corresponding value in `dp` to 0, effectively eliminating paths that end at that cell.
Edge case 3: All cells have obstacles. The algorithm correctly returns 0 because dp[0] is initially set to 1, but will be subsequently set to 0 for the remaining cells due to the obstacle checks.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the obstacle in the starting cell: Forgetting to check if the starting cell has an obstacle, which immediately makes the number of paths 0.

✗Common mistake 2: Incorrectly updating the `dp` array: Failing to set `dp[j]` to 0 when an obstacle is encountered in the current cell, which leads to incorrect path counts.

✗Common mistake 3: Not handling edge cases when grid has only one row/column. This might cause array index out of bounds errors.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Pathfinding in Robotics: Determining the number of possible routes a robot can take in a warehouse or factory environment, avoiding obstacles.

🏦Real-world scenario 2: Game Development: Calculating the number of possible paths a character can take in a game level to reach a destination, avoiding walls or enemy locations.

🎮Real-world scenario 3: Network Routing: Finding the number of possible paths for data packets to travel through a network, avoiding congested or failed nodes.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 3, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 14

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 7

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jun 30

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

Should I use top-down (memoization) or bottom-up (tabulation)?

Start with top-down (recursion + memoization) as it directly maps to the recursive thinking and handles only needed subproblems. Convert to bottom-up for better space efficiency and to avoid stack overflow. Bottom-up is often faster due to no recursion overhead.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Unique Paths II"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?