Problem Description

You have a robot positioned on a grid with m rows and n columns. The robot starts at the top-left corner of the grid (position [0][0]) and wants to reach the bottom-right corner (position [m-1][n-1]).

The robot has movement restrictions - it can only move in two directions:

• Right (to the next column)
• Down (to the next row)

Your task is to find the total number of unique paths the robot can take to reach from the starting position to the destination.

For example, on a 3×3 grid, the robot needs to make exactly 2 moves right and 2 moves down to reach the destination. The different orderings of these moves create different paths, such as:

• Right → Right → Down → Down
• Right → Down → Right → Down
• Down → Down → Right → Right
• And so on...

Given integers m (number of rows) and n (number of columns), return the count of all possible unique paths from [0][0] to [m-1][n-1].

The answer is guaranteed to be at most 2 × 10^9.

Intuition

Think about how the robot reaches any specific cell in the grid. Since the robot can only move right or down, there are only two ways to arrive at any cell [i][j]:

1. From the cell directly above it [i-1][j] by moving down
2. From the cell directly to its left [i][j-1] by moving right

This observation is key! If we know the number of ways to reach the cell above and the cell to the left, we can calculate the number of ways to reach the current cell by simply adding them together.

Why does addition work here? Because every path to [i-1][j] can be extended by one downward move to reach [i][j], and every path to [i][j-1] can be extended by one rightward move to reach [i][j]. These two sets of paths are completely distinct (they come from different directions), so we add them.

Starting from the top-left corner [0][0], there's exactly 1 way to be there (we start there). For the first row, the robot can only move right, so there's only 1 way to reach each cell. Similarly, for the first column, the robot can only move down, so there's only 1 way to reach each cell.

Building upon this foundation, we can calculate the number of paths to every other cell using our addition rule: f[i][j] = f[i-1][j] + f[i][j-1]. This naturally leads to a dynamic programming solution where we build up our answer cell by cell, row by row, until we reach the bottom-right corner.

The beauty of this approach is that it breaks down a complex counting problem into simple, local decisions - at each cell, we only need to look at its two neighbors to determine the answer.

Learn more about Math, Dynamic Programming and Combinatorics patterns.

Solution Approach

We implement the solution using dynamic programming with a 2D array to store the number of paths to each cell.

Step 1: Initialize the DP table
Create a 2D array f with dimensions m × n, where f[i][j] represents the number of unique paths to reach cell (i, j) from the starting position. Initialize all values to 0, except f[0][0] = 1 since there's exactly one way to be at the starting position.

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

Step 2: Fill the DP table
Iterate through each cell in the grid from top to bottom, left to right. For each cell (i, j), calculate the number of paths using the state transition equation:

f[i][j] = f[i-1][j] + f[i][j-1]

However, we need to handle boundary cases:

• If i > 0, we can arrive from the cell above, so add f[i-1][j]
• If j > 0, we can arrive from the cell to the left, so add f[i][j-1]

for i in range(m):
    for j in range(n):
        if i:  # If not in the first row
            f[i][j] += f[i - 1][j]
        if j:  # If not in the first column
            f[i][j] += f[i][j - 1]

Step 3: Return the result
The answer is stored in f[m-1][n-1], which represents the total number of unique paths to reach the bottom-right corner.

return f[-1][-1]

Time and Space Complexity:

• Time Complexity: O(m × n) - We visit each cell exactly once
• Space Complexity: O(m × n) - We store the number of paths for each cell in the 2D array

The algorithm efficiently builds up the solution by solving smaller subproblems first, ensuring that when we calculate paths to any cell, we already have the answers for the cells we depend on (the cell above and to the left).

Example Walkthrough

Let's walk through a concrete example with a 3×3 grid (m=3, n=3) to see how the dynamic programming solution builds up the answer.

Step 1: Initialize the grid We create a 3×3 DP table and set f[0][0] = 1:

f = [[1, 0, 0],
     [0, 0, 0],
     [0, 0, 0]]

Step 2: Fill the first row and column Starting from position (0,0), we iterate through each cell:

For cell (0,1):

• Can't come from above (i=0)
• Can come from left: f[0][1] = f[0][0] = 1

For cell (0,2):

• Can't come from above (i=0)
• Can come from left: f[0][2] = f[0][1] = 1

After processing the first row:

f = [[1, 1, 1],
     [0, 0, 0],
     [0, 0, 0]]

Similarly for the first column:

• Cell (1,0): Can only come from above: f[1][0] = f[0][0] = 1
• Cell (2,0): Can only come from above: f[2][0] = f[1][0] = 1

f = [[1, 1, 1],
     [1, 0, 0],
     [1, 0, 0]]

Step 3: Fill the interior cells For cell (1,1):

• From above: f[0][1] = 1
• From left: f[1][0] = 1
• Total: f[1][1] = 1 + 1 = 2

For cell (1,2):

• From above: f[0][2] = 1
• From left: f[1][1] = 2
• Total: f[1][2] = 1 + 2 = 3

For cell (2,1):

• From above: f[1][1] = 2
• From left: f[2][0] = 1
• Total: f[2][1] = 2 + 1 = 3

For cell (2,2) (our destination):

• From above: f[1][2] = 3
• From left: f[2][1] = 3
• Total: f[2][2] = 3 + 3 = 6

Final DP table:

f = [[1, 1, 1],
     [1, 2, 3],
     [1, 3, 6]]

The answer is f[2][2] = 6, meaning there are 6 unique paths from the top-left to bottom-right corner.

These 6 paths correspond to the different orderings of 2 Right moves (R) and 2 Down moves (D):

1. RRDD
2. RDRD
3. RDDR
4. DRRD
5. DRDR
6. DDRR

Solution Implementation

Time and Space Complexity

The current code uses a 2D array f of size m × n to store the number of unique paths to each cell.

Time Complexity: O(m × n)

• The algorithm uses two nested loops that iterate through all m rows and n columns
• For each cell (i, j), it performs constant time operations (checking conditions and adding values)
• Therefore, the total time complexity is O(m × n)

Space Complexity: O(m × n)

• The code creates a 2D array f with m rows and n columns to store intermediate results
• This requires O(m × n) space to store all the values

Optimization Opportunity: As noted in the reference, since f[i][j] only depends on f[i-1][j] (cell directly above) and f[i][j-1] (cell directly to the left), we can optimize space complexity. Instead of maintaining the entire 2D array, we could use a 1D array of size n and update it row by row, reducing space complexity to O(n) while maintaining the same time complexity of O(m × n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Initialization of the DP Table

The Pitfall: A common mistake is initializing the starting cell dp[0][0] = 1 but then incorrectly handling it during the iteration. The current code sets dp[0][0] = 1 initially, but when the loops reach (0, 0), the cell value gets recalculated. Since both conditions row > 0 and col > 0 are false at (0, 0), the value remains 1, which happens to be correct. However, this relies on implicit behavior and can lead to confusion or errors if the code is modified.

Why It's Problematic:

• The logic becomes unclear - are we initializing or calculating?
• If someone modifies the initialization or loop logic, it could break
• It's not immediately obvious why the code works correctly

Better Solution: Either skip the starting cell in the iteration or initialize the entire first row and column properly:

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * n for _ in range(m)]
      
        # Initialize first row - only one way to reach any cell in first row
        for col in range(n):
            dp[0][col] = 1
      
        # Initialize first column - only one way to reach any cell in first column  
        for row in range(m):
            dp[row][0] = 1
      
        # Fill the rest of the table starting from (1, 1)
        for row in range(1, m):
            for col in range(1, n):
                dp[row][col] = dp[row - 1][col] + dp[row][col - 1]
      
        return dp[m - 1][n - 1]

2. Space Optimization Opportunity Missed

The Pitfall: Using a full 2D array when only the previous row is needed for computation wastes memory, especially for large grids.

Why It's Problematic:

• Uses O(m × n) space when O(n) is sufficient
• Can cause memory issues for very large grids
• Inefficient cache usage

Optimized Solution: Use a 1D array that gets updated row by row:

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # Only need to store one row at a time
        dp = [1] * n  # Initialize first row with all 1s
      
        # Process each subsequent row
        for row in range(1, m):
            for col in range(1, n):
                dp[col] = dp[col] + dp[col - 1]
      
        return dp[n - 1]

3. Mathematical Solution Alternative

The Pitfall: Not recognizing that this is a combinatorial problem that can be solved with a mathematical formula.

Why It's Problematic:

• The DP solution has O(m × n) time complexity
• The mathematical solution is O(min(m, n)) time and O(1) space

Mathematical Solution: The robot needs to make exactly (m-1) down moves and (n-1) right moves. The number of unique paths is the number of ways to arrange these moves: C(m+n-2, m-1) or C(m+n-2, n-1).

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        from math import factorial
      
        # Total moves needed: (m-1) down + (n-1) right = m+n-2
        # Choose positions for either m-1 down moves or n-1 right moves
        return factorial(m + n - 2) // (factorial(m - 1) * factorial(n - 1))

Or more efficiently to avoid large factorial calculations:

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # Calculate C(m+n-2, m-1) iteratively
        result = 1
        for i in range(1, min(m, n)):
            result = result * (m + n - 1 - i) // i
        return result