Domain 2MediumCORE

Unique Paths

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.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Dynamic Programming

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) and n (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 ≤2⋅109\le 2 \cdot 10^9), so Python’s arbitrary precision integers won’t overflow unexpectedly even if the constraint wasn’t there.

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 m+n−2m + n - 2. The number of nodes in that tree grows exponentially (O(2m+n)O(2^{m+n})). 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.

  1. 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.
  2. 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.
  3. Result: The bottom-right corner dp[m-1][n-1] will contain our final answer.

Complexity Analysis

  • Time Complexity: O(m×n)O(m \times n). 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: O(m×n)O(m \times n) due to the DP table storage.
    • Note: We could optimize space down to O(n)O(n) by only storing the current row’s values since we never need more than one previous row, but given m and n <= 100, a full grid is clearer for communication purposes in an interview setting unless memory constraints are explicitly tight.

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

Edge Cases Handled