View on NeetCode
View on LeetCode

Problem

There is a robot on an m x n grid. The robot is 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.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Example 1:

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

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Constraints:

  • 1 <= m, n <= 100

Solution

Approach 1: 2D Dynamic Programming

The key insight is that the number of ways to reach cell (i, j) is the sum of ways to reach (i-1, j) and (i, j-1).

Implementation

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

        # First row - only one way (all right)
        for j in range(n):
            dp[0][j] = 1

        # First column - only one way (all down)
        for i in range(m):
            dp[i][0] = 1

        # Fill the rest of the grid
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]

        return dp[m-1][n-1]

Approach 2: Space-Optimized 1D DP

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] * n

        for i in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j-1]

        return dp[n-1]

Approach 3: Mathematical (Combinatorics)

from math import comb

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # Total moves needed: (m-1) down + (n-1) right = (m+n-2) total
        # Choose (m-1) positions for down moves out of (m+n-2) total
        return comb(m + n - 2, m - 1)

Complexity Analysis

2D DP:

  • Time Complexity: O(m * n), filling m×n grid.
  • Space Complexity: O(m * n) for the dp array.

1D DP:

  • Time Complexity: O(m * n).
  • Space Complexity: O(n), only storing one row at a time.

Mathematical:

  • Time Complexity: O(m) or O(n) for computing combination.
  • Space Complexity: O(1).

Key Insights

  1. Only Two Directions: Can only move right or down, so paths have clear structure.

  2. DP Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1] (ways from above + ways from left).

  3. Base Cases: First row and column all have value 1 (only one path - straight line).

  4. Space Optimization: Only need previous row to compute current row, so can use 1D array.

  5. Combinatorial Interpretation: Need exactly (m-1) down moves and (n-1) right moves. This is choosing positions, which is C(m+n-2, m-1).

  6. Pascal’s Triangle: The DP values follow Pascal’s triangle pattern.