There is a robot on an m x n
grid. The robot is initially located at the top-left corner (i.e., grid[0][0]
). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]
). The robot can only move either down or right at any point in time.
Given the two integers m
and n
, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
For example:
Consider a 3x2 grid. How many unique paths are there?
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
Could you write a function to calculate this? What is the Big O runtime?
Given a grid of size m x n
, find the number of unique paths a robot can take from the top-left corner to the bottom-right corner, where the robot can only move down or right.
A straightforward approach is to use recursion. Start from the top-left corner and explore all possible paths. At each step, the robot can either move down or right. When the robot reaches the bottom-right corner, we increment the path count.
def unique_paths_recursive(m, n):
if m == 1 or n == 1:
return 1
return unique_paths_recursive(m - 1, n) + unique_paths_recursive(m, n - 1)
O(2^(m+n)). In the worst case, the function explores all possible paths, leading to exponential time complexity.
O(m+n). Due to the call stack during recursion.
This approach is highly inefficient for larger values of m
and n
due to overlapping subproblems.
A more efficient approach is to use dynamic programming. We can create a 2D array dp
of size m x n
where dp[i][j]
represents the number of unique paths to reach cell (i, j)
. The base cases are the first row and first column, where the number of paths is always 1.
For any other cell (i, j)
, the number of unique paths is the sum of the paths from the cell above (i-1, j)
and the cell to the left (i, j-1)
. This is because the robot can only move down or right.
def unique_paths_dp(m, n):
dp = [[0] * n for _ in range(m)]
for i in range(m):
dp[i][0] = 1
for j in range(n):
dp[0][j] = 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
O(m*n). We iterate through each cell in the m x n
grid once.
O(m*n). We use a 2D array of size m x n
to store the number of unique paths for each cell.
We can further optimize space complexity to O(n) by using only one row to store the current number of paths, since the previous row is no longer needed. This involves updating the array iteratively.
def unique_paths_optimized(m, n):
row = [1] * n
for i in range(1, m):
for j in range(1, n):
row[j] += row[j-1]
return row[n-1]
O(m*n). We iterate through each cell in the m x n
grid once.
O(n). We use a 1D array of size n
to store the number of unique paths for the current row.
m
or n
is 1, there is only one possible path.m
and n
are greater than 0, as per constraints.The dynamic programming approach provides an efficient solution to find the number of unique paths in a grid. The space-optimized version further reduces memory usage, making it an ideal solution for larger grids.