101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Dynamic Programming (2D) - Complex approach
  2. Dynamic Programming (1D) - Complex approach
  3. Combinatorial Solution - Complex approach

Approach 1: Dynamic Programming (2D)

The key insight for solving this problem is to use dynamic programming to build up the solution from smaller subproblems.

Let's define dp[i][j] as the number of unique paths to reach the cell at position (i, j) from the top-left corner (0, 0).

Since the robot can only move right or down, to reach the cell (i, j), it must come from either the cell above it (i-1, j) or the cell to its left (i, j-1). Therefore, the recurrence relation is:

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

For the base cases, there is only one way to reach any cell in the first row or first column (by moving only right or only down, respectively). So:

  • dp[0][j] = 1 for all j from 0 to n-1
  • dp[i][0] = 1 for all i from 0 to m-1

The final answer is dp[m-1][n-1], which represents the number of unique paths to reach the bottom-right corner.

Algorithm:

  1. Initialize a 2D DP array dp of size m × n, where dp[i][j] represents the number of unique paths to reach the cell at position (i, j).
  2. Set the base cases: dp[0][j] = 1 for all j from 0 to n-1, and dp[i][0] = 1 for all i from 0 to m-1.
  3. For each cell (i, j) where i > 0 and j > 0, calculate dp[i][j] = dp[i-1][j] + dp[i][j-1].
  4. Return dp[m-1][n-1], which represents the number of unique paths to reach the bottom-right corner.

Time Complexity:

O(m * n)

We need to fill in the DP table of size m × n, and each cell takes constant time to compute.

Space Complexity:

O(m * n)

We use a 2D DP array of size m × n to store the number of unique paths for each cell.

Approach 2: Dynamic Programming (1D)

We can optimize the space complexity of the dynamic programming approach by using a 1D array instead of a 2D array.

The key observation is that when we're calculating dp[i][j], we only need the values from the current row and the row above it. Specifically, we need dp[i-1][j] and dp[i][j-1].

If we use a 1D array dp where dp[j] represents the number of unique paths to reach the cell at position (i, j), then:

  • Before the update, dp[j] represents the number of unique paths to reach the cell at position (i-1, j).
  • After updating dp[j-1], dp[j-1] represents the number of unique paths to reach the cell at position (i, j-1).

So, the recurrence relation becomes:

dp[j] = dp[j] + dp[j-1]

We initialize the 1D array with all 1s, representing the base case for the first row. Then, for each subsequent row, we update the array from left to right.

The final answer is dp[n-1], which represents the number of unique paths to reach the bottom-right corner.

Algorithm:

  1. Initialize a 1D DP array dp of size n, where dp[j] represents the number of unique paths to reach the cell at position (i, j).
  2. Set the base case: dp[j] = 1 for all j from 0 to n-1, representing the first row.
  3. For each row i from 1 to m-1:
  4. a. For each column j from 1 to n-1:
  5. i. Update dp[j] = dp[j] + dp[j-1].
  6. Return dp[n-1], which represents the number of unique paths to reach the bottom-right corner.

Time Complexity:

O(m * n)

We still need to process each cell in the grid, which takes O(m * n) time.

Space Complexity:

O(n)

We only use a 1D array of size n to store the number of unique paths for the current row.

Approach 3: Combinatorial Solution

This problem can also be solved using combinatorics. To reach the bottom-right corner from the top-left corner, the robot needs to make exactly m-1 down moves and n-1 right moves, for a total of m+n-2 moves.

The number of unique paths is equivalent to the number of ways to choose which m-1 of the m+n-2 total moves should be down moves (or equivalently, which n-1 moves should be right moves).

This is a combination problem, and the answer is:

C(m+n-2, m-1) = (m+n-2)! / ((m-1)! * (n-1)!)

However, calculating factorials directly can lead to overflow for large inputs. To avoid this, we can use the formula for combinations and calculate it step by step:

C(n, k) = n! / (k! * (n-k)!) = (n * (n-1) * ... * (n-k+1)) / (k * (k-1) * ... * 1)

In our case, n = m+n-2 and k = m-1, so:

C(m+n-2, m-1) = ((m+n-2) * (m+n-3) * ... * n) / ((m-1) * (m-2) * ... * 1)

We can calculate this efficiently by taking the smaller of m-1 and n-1 as k to minimize the number of multiplications.

Algorithm:

  1. Calculate the total number of moves: total = m + n - 2.
  2. Choose the smaller of m-1 and n-1 as k to minimize the number of multiplications.
  3. Calculate C(total, k) = total! / (k! * (total-k)!) using the formula C(n, k) = (n * (n-1) * ... * (n-k+1)) / (k * (k-1) * ... * 1).
  4. Return the result.

Time Complexity:

O(min(m, n))

We perform min(m-1, n-1) multiplications and divisions to calculate the combination.

Space Complexity:

O(1)

We only use a constant amount of space to store the result and intermediate values.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function uniquePaths(m, n):
    // Initialize DP array
    dp = new 2D array of size m × n, initialized with 0
 
    // Set base cases
    for i from 0 to m-1:
        dp[i][0] = 1
    for j from 0 to n-1:
        dp[0][j] = 1
 
    // Fill DP array
    for i from 1 to m-1:
        for j from 1 to n-1:
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
 
    return dp[m-1][n-1]
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone