Problem Description

A robot is located at the top - left corner of an m x n grid (marked 'Start'). The robot can only move either down or right at any point. The goal is to reach the bottom - right corner (marked 'Finish'). We need to determine the number of unique paths possible.

Examples

• Example 1: Input: rows = 3, cols = 7 Output: 28
• Example 2: Input: rows = 3, cols = 2 Output: 3 Explanation: There are 3 unique paths:
  1. Right → Down → Down
  2. Down → Down → Right
  3. Down → Right → Down
• Example 3: Input: rows = 7, cols = 3 Output: 28
• Example 4: Input: rows = 3, cols = 3 Output: 6

Constraints

1 ≤ m, n ≤ 100 The answer is guaranteed to be ≤ 2 × 10⁹

Approach 1: Dynamic Programming (2D DP Array)

1. Define DP Array: path_counts[i][j] represents the number of unique paths to reach cell (i, j) from (0, 0).
2. Recurrence Relation: To reach (i, j), the robot can come from the top (path_counts[i - 1][j]) or the left (path_counts[i][j - 1]). Thus, path_counts[i][j] = path_counts[i - 1][j] + path_counts[i][j - 1].
3. Initialization: All cells in the first row (path_counts[0][j]) and first column (path_counts[i][0]) have exactly 1 path (since there's only one way to move right or down along these edges).
4. Traversal Order: Iterate row - wise (or column - wise) to ensure that the cells (top and left) on which the current cell's path count depends are computed first.
5. DP Array Calculation: Fill the DP table using the recurrence relation.

class Solution:
    def uniquePaths(self, rows: int, cols: int) -> int:
        # Initialize DP table with all zeros
        path_counts = [[0 for _ in range(cols)] for _ in range(rows)]
        
        # Set base cases: first column and first row
        for i in range(rows):
            path_counts[i][0] = 1
        for j in range(cols):
            path_counts[0][j] = 1
        
        # Compute paths for other cells
        for i in range(1, rows):
            for j in range(1, cols):
                path_counts[i][j] = path_counts[i - 1][j] + path_counts[i][j - 1]
        
        return path_counts[rows - 1][cols - 1]

Time Complexity: O(rows × cols) (each cell is processed exactly once). Space Complexity: O(rows × cols) (we use a two - dimensional array to store the number of paths for each cell).

Approach 2: Dynamic Programming (1D DP Array)

This approach optimizes space by using a 1D array and updating it in place.

class Solution:
    def uniquePaths(self, rows: int, cols: int) -> int:
        # Initialize a 1D array where each element represents the number of paths to a column
        col_paths = [1] * cols  # The first row has only one path to each column
        
        # Update the number of paths for subsequent rows
        for _ in range(1, rows):
            for j in range(1, cols):
                col_paths[j] += col_paths[j - 1]  # Accumulate the number of paths from the left
        
        return col_paths[cols - 1]

Time Complexity: O(rows × cols) (the time complexity remains the same as the 2D approach, but with reduced space usage). Space Complexity: O(cols) (we only store the number of paths for one row at a time).

Approach 3: Combinatorics

The robot needs to make a total of (rows - 1)+(cols - 1) moves (the total number of steps is rows + cols - 2), among which there are (rows - 1) down - moves (or (cols - 1) right - moves). The problem can be reduced to choosing (rows - 1) positions out of (rows + cols - 2) steps (this is a combination problem, denoted as C(rows + cols - 2, rows - 1)).

To avoid overflow, we calculate the combination iteratively with division:

class Solution:
    def uniquePaths(self, rows: int, cols: int) -> int:
        # Total number of steps: (rows + cols - 2), and we need to choose (rows - 1) steps for down - moves
        total_steps = rows + cols - 2
        choose = rows - 1  # We can also choose cols - 1, whichever is smaller
        
        numerator = 1
        denominator = choose
        count = choose
        
        while count > 0:
            numerator *= total_steps
            total_steps -= 1
            # Reduce the fraction early to prevent overflow
            while denominator > 0 and numerator % denominator == 0:
                numerator //= denominator
                denominator -= 1
            count -= 1
        
        return numerator

Time Complexity: O(choose) (the time complexity is dominated by the smaller value between rows - 1 and cols - 1). Space Copmlexity: O(1) (we only use a few variables).