62. Unique Paths
Model: qwen3.5:9b
Topics: Array,Dynamic Programming
FAANG asked: 1
Acceptance rate: 56.3%
Problem Breakdown
The problem asks us to count the number of unique paths from a top-left starting point (0, 0) to a bottom-right ending point in an m x n grid. The robot is constrained to move only Down or Right.
- Inputs: Two integers
m(rows) andn(columns). - Output: An integer representing the total count of unique paths.
- Constraints & Edge Cases:
- Grid dimensions are at least 1x1 (
1 <= m, n). This means we don’t need to handle empty grids or zero-sized inputs. - The result fits within a standard 32-bit integer limit (guaranteed ), so Python’s arbitrary precision integers won’t overflow unexpectedly even if the constraint wasn’t there.
- Grid dimensions are at least 1x1 (
Intuition
If we tried to solve this using brute-force recursion, every time the robot reaches an intersection, it branches into two paths: Down or Right. This creates a binary tree of depth . The number of nodes in that tree grows exponentially (). For inputs like 100 x 100, this would be computationally impossible (Time Limit Exceeded).
The key insight is Dynamic Programming. Notice that to reach any specific cell (i, j), the robot must have arrived from either directly above (i-1, j) or directly to the left (i, j-1). This means the number of paths to a current cell depends entirely on the cells we’ve already solved. We can build up our solution iteratively:
paths[i][j] = paths[i-1][j] + paths[i][j-1]
This transforms an exponential problem into a polynomial one by reusing subproblem results (memoization).
Approach
We will use a 2D array dp of size m x n.
- Initialization: We know that for any cell in the first row or first column, there is exactly one unique path to reach it (you can only move Right along the top edge or Down along the left edge). So we initialize these boundary cells with 1s.
- Iteration: Iterate through every other cell
(i, j)starting from index[1][1]. For each cell, calculate its value by summing the paths available to reach it from the Top and Left neighbors. - Result: The bottom-right corner
dp[m-1][n-1]will contain our final answer.
Complexity Analysis
- Time Complexity: . We visit each cell in the grid exactly once to compute its value. With constraints up to 100x100, this is roughly 10,000 operations, which is negligible for modern processors (well under a millisecond).
- Space Complexity: due to the DP table storage.
- Note: We could optimize space down to by only storing the current row’s values since we never need more than one previous row, but given
mandn <= 100, a full grid is clearer for communication purposes in an interview setting unless memory constraints are explicitly tight.
- Note: We could optimize space down to by only storing the current row’s values since we never need more than one previous row, but given
Solution
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# Initialize DP table with zeros
dp = [[0] * n for _ in range(m)]
# Base case initialization:
# There is exactly one way to reach any cell on the first row (all Rights)
# and any cell on the first column (all Downs).
for i in range(m):
dp[i][0] = 1
for j in range(n):
dp[0][j] = 1
# Fill the rest of the grid based on recurrence relation:
# Paths to current cell = paths from Top + paths from Left
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]
# Example usage:
# sol = Solution()
# print(sol.uniquePaths(3, 7)) # Output: 28