The O(n) Club: Unique Paths II—Help, My Robot Can’t Even (LeetCode 63 Edition)

The O(n) Club: Unique Paths II—Help, My Robot Can’t Even (LeetCode 63 Edition)

⚡ TL;DR

You’re coding a grid-crawling robot, but some squares are off-limits. How many ways can it get from home base (top-left) to the docking bay (bottom-right), moving only down or right, without crashing into obstacles? If you brute-force it, you’ll invent a new kind of burnout. Here’s what Java dreams (and nightmares) look like:

// Brute force: Sure, this'll pass. On a postage stamp.
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    return dfs(obstacleGrid, 0, 0);
}
private int dfs(int[][] grid, int i, int j) {
    if (i >= grid.length || j >= grid[0].length || grid[i][j] == 1) return 0;
    if (i == grid.length - 1 && j == grid[0].length - 1) return 1;
    return dfs(grid, i + 1, j) + dfs(grid, i, j + 1);
} // Friends don’t let friends DFS grids this big.

🧠 How Devs Usually Mess This Up

This problem is basically a trap for your DP fundamentals. Common slip-ups:

• Ignoring obstacles on the starting cell. If start is blocked, it’s over! Bail out instantly or the robot just faceplants forever.
• Messy first row/column initialization. Hit a wall early, and it’s a zero-fest downstream—all the way across that row/column.
• Forgetting the rules of the DP club: It’s not always dp[i][j] = dp[i-1][j] + dp[i][j-1]. If there’s an obstacle, set dp[i][j] to (and pray for better furniture placement).

🔍 What’s Actually Going On

Imagine a robot at a dinner party, only allowed to move right or down—no moonwalks, no teleporting through walls (obstacles). Every cell asks: “Can I be reached without eating glass?” If it’s an obstacle: zero ways, sorry. Otherwise, it checks on left and top neighbors (if not obstacles!), adds up the ways, and proceeds. Hit an obstacle in row or column zero? Everything after is cursed.

🛠️ PseudoCode

• Check if the start is blocked.
  if (obstacleGrid[0][0] == 1) return 0;
  If you trip at the door, you don’t get to dance.
• Make a DP grid the size of your warehouse.
  int[][] dp = new int[m][n];
  Each dp[i][j] stores paths to reach (i,j) alive.
• Set the origin.
  dp[0][0] = 1;
  Assuming it’s obstacle-free.
• Initialize first row.
  For every cell, if it and all cells left are open, copy 1. Otherwise, all (obstacles are contagious here).
• Initialize first column.
  Same as row, just vertically confused.
• For the rest, fill using:
  if obstacle: dp[i][j] = 0;<br>else: dp[i][j] = dp[i-1][j] + dp[i][j-1];
  Because robots don’t walk through walls.
• The answer:
  return dp[m-1][n-1];
  How many ways to glory? Or 0, if the universe hates you.

💻 The Code

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length, n = obstacleGrid[0].length;
    if (obstacleGrid[0][0] == 1) return 0;
    int[][] dp = new int[m][n];
    dp[0][0] = 1;
    // First row
    for (int j = 1; j < n; j++) {
        dp[0][j] = (obstacleGrid[0][j] == 0 && dp[0][j-1] == 1) ? 1 : 0;
    }
    // First col
    for (int i = 1; i < m; i++) {
        dp[i][0] = (obstacleGrid[i][0] == 0 && dp[i-1][0] == 1) ? 1 : 0;
    }
    // The rest
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[i][j] == 0) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }
    return dp[m-1][n-1];
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge case black holes:
  • If start or end is blocked, you get a big, fat zero.
  • First row/column obstacle? Every cell after, in that direction, is doomed too.
  • Null or empty grid? Java will shame you in loud stack traces.
• Complexity check-in: Time and space is O(mn). Sure, you can optimize space, but unless your robot moonlights as a Mars Rover, keep it readable.