We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Unique Paths

Difficulty: Medium

Problem Description

Given a robot located at the top-left corner of an m x n grid, the robot can only move either down or right to reach the bottom-right corner. The task is to determine the number of unique paths the robot can take to reach its destination.

Key Insights

  • The robot can only move in two directions: right and down.
  • The number of unique paths can be determined using either combinatorial mathematics or dynamic programming.
  • The problem can be visualized as a grid, where each cell represents a point in the robot's journey.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(n) (for the dynamic programming approach, if optimized)

Solution

To solve the problem, we can use a dynamic programming approach. We create a 2D array (or a 1D array for optimization) to store the number of unique paths to each cell in the grid. The value at each cell is the sum of the values from the cell directly above it and the cell directly to the left of it. This is because the robot can only come from those two directions.

  1. Initialize a 2D array dp where dp[i][j] represents the number of unique paths to reach cell (i, j).
  2. Set dp[0][0] to 1, as there is one way to be at the starting point.
  3. For each cell (i, j), update dp[i][j] as follows:
    • If i > 0, add dp[i-1][j] (paths from the cell above).
    • If j > 0, add dp[i][j-1] (paths from the cell to the left).
  4. The answer will be found at dp[m-1][n-1], which represents the number of unique paths to the bottom-right corner.

Code Solutions

def uniquePaths(m: int, n: int) -> int:
    # Create a 2D array to store the number of unique paths
    dp = [[1] * n for _ in range(m)]
    
    # Fill the dp array
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    
    # The bottom-right corner will have the total unique paths
    return dp[m - 1][n - 1]
← Back to All Questions