#111 Medium Time O(m·n) Space O(m·n) Animated

Unique Paths

Count unique paths from top-left to bottom-right in m×n grid.

LeetCode ↗

Approach: Dynamic Programming (2D)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Description

Count unique paths from top-left to bottom-right in m×n grid.

Constraints

Time Complexity: O(m·n)
Space Complexity: O(m·n)

Solution — Dynamic Programming (2D)

O(m·n) O(m·n)

def uniquePaths(m, n):
    row = [1] * n
    for i in range(m - 1):
        newRow = [1] * n
        for j in range(n - 2, -1, -1):
            newRow[j] = newRow[j + 1] + row[j]
        row = newRow
    return row[0]

Longest Common Subsequence

Unique Paths

Steps

Description

Constraints

Tags

Solution — Dynamic Programming (2D)