LeetCode 62. Unique Paths

A robot sits at the top‑left corner of an m × n grid (cell (0, 0)). It can only move down or right one step at a time. The goal is the bottom‑right corner (m-1, n-1). Compute the total number of distinct paths the robot can take.

Example 1
Input: m = 3, n = 7
Output: 28

Example 2
Input: m = 3, n = 2
Output: 3
Possible paths:

1. Right → Down → Down
2. Down → Down → Right
3. Down → Right → Down

Example 3
Input: m = 7, n = 3
Output: 28

Example 4
Input: m = 3, n = 3
Output: 6

Approach

Define a 2‑dimensional table paths[r][c] that holds the number of ways to reach cell (r, c) from (0, 0).

• State transition
  Since moves are only down or right, the cell (r, c) can be entered either from above or from the left:

  paths[r][c] = paths[r-1][c] + paths[r][c-1]
  

• Initailisation
  The first row and the first column can be reached in exactly one way (by moving only right or only down).
  Set paths[r][0] = 1 for all r and paths[0][c] = 1 for all c.

• Traversal order
  Top to bottom, left to right, which guarantees that the required previous computed values are ready.

• Result
  After filling the table, paths[m-1][n-1] gives the answer.

Python solution

def uniquePaths(m: int, n: int) -> int:
    paths = [[0] * n for _ in range(m)]

    for r in range(m):
        paths[r][0] = 1
    for c in range(n):
        paths[0][c] = 1

    for r in range(1, m):
        for c in range(1, n):
            paths[r][c] = paths[r-1][c] + paths[r][c-1]

    return paths[m-1][n-1]

• Time complexity: O(m · n)
• Space complexity: O(m · n)

LeetCode 63. Unique Paths II

Now some cells contain obstacles. An obstacle is marked by 1, a free cell by 0. Find the number of obstacle‑free paths from top‑left to bottom‑right. The robot can only move down or right.

Example 1
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: The centre cell is blocked. The two valid paths:

1. Right → Right → Down → Down
2. Down → Down → Right → Right

Example 2
Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

Approach

The paths table keeps the same meaning. The transition formula only applies when the current cell is free.

• Initialisation
  Fill the first column with 1 until an obstacle is met; all cells below stay 0. The same logic applies to the first row.

• Transition (obstacle‑aware)
  For r ≥ 1 and c ≥ 1:

  if obstacleGrid[r][c] == 0:
      paths[r][c] = paths[r-1][c] + paths[r][c-1]
  

  (Otherwise it remains 0, effectively ignoring blocked cells.)

• Edge cases
  If the start or the finish cell itself contains an obstacle, return 0 immediately.

Python solution

def uniquePathsWithObstacles(obstacleGrid):
    if not obstacleGrid or obstacleGrid[0][0] == 1:
        return 0
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    if obstacleGrid[m-1][n-1] == 1:
        return 0

    paths = [[0] * n for _ in range(m)]

    # first column: stop at the first obstacle
    for r in range(m):
        if obstacleGrid[r][0] == 1:
            break
        paths[r][0] = 1

    # first row: stop at the first obstacle
    for c in range(n):
        if obstacleGrid[0][c] == 1:
            break
        paths[0][c] = 1

    for r in range(1, m):
        for c in range(1, n):
            if obstacleGrid[r][c] == 0:
                paths[r][c] = paths[r-1][c] + paths[r][c-1]

    return paths[m-1][n-1]

• Time complexity: O(m · n)
• Space complexity: O(m · n)