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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Unique Paths

Number: 62

Difficulty: Medium

Paid? No

Companies: Amazon, Meta, Google, Microsoft, Bloomberg, tcs, Adobe, Oracle, Coupang, DE Shaw, Accenture, Apple, Uber, Intuit

Problem Description

There is a robot on an m x n grid that starts at the top-left corner and can only move either down or right. The task is to determine the number of unique paths the robot can take to reach the bottom-right corner of the grid.

Key Insights

  • The robot is constrained to only move right or down.
  • Any valid path consists of exactly (m-1) down moves and (n-1) right moves.
  • The problem can be solved using Dynamic Programming where each cell is the sum of the ways to reach the cell from the top and left.
  • Alternatively, a combinatorial solution is possible by calculating the number of unique sequences of moves, equivalent to choosing (m-1) moves from (m+n-2) moves.

Space and Time Complexity

Time Complexity: O(mn)
Space Complexity: O(mn) – can be optimized to O(n) using a 1D DP array.

Solution

We can solve the problem using a dynamic programming approach. The idea is to create a 2D DP table where each cell (i, j) represents the number of ways to reach that cell. Since the robot can only come from above or from the left, we update the DP table as follows:

  • Initialize dp[0][j] = 1 for all j (only one way to move right in the first row).
  • Initialize dp[i][0] = 1 for all i (only one way to move down in the first column).
  • For each other cell, compute dp[i][j] = dp[i-1][j] + dp[i][j-1]. The final answer will be at dp[m-1][n-1].

The combinatorial alternative computes C(m+n-2, m-1) or C(m+n-2, n-1) using basic factorial arithmetic, which is efficient for the given constraints.

Code Solutions

# Python solution using Dynamic Programming

def uniquePaths(m, n):
    # Initialize a 2D list with 1's for the first row and first column
    dp = [[1] * n for _ in range(m)]
    
    # Fill in the DP table
    for i in range(1, m):
        for j in range(1, n):
            # The number of ways to reach this cell is the sum of the ways from the cell above and the cell on the left
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    # Return the value in the bottom-right cell
    return dp[m-1][n-1]

# Example usage:
print(uniquePaths(3, 7))
← Back to All Questions