⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#62) before relying on it.

🗺️ Unique Paths

An interactive visualization of how dynamic programming counts unique paths in a grid. Watch the algorithm build up the solution from base cases to the final answer.

Dynamic Programming LeetCode 62 ↗ Medium

The Problem

A robot is located on an m × n grid, starting at the top-left corner.

The robot is trying to reach the bottom-right corner. The robot can only move right or down at any point in time.

Given the two integers m and n, return the number of unique paths the robot can take to reach the bottom-right corner.

Interactive Visualization

Rows (m)

Columns (n)

Preset

Speed:

Grid

Equation will appear here

Status

Press Step or Play to begin.

Code

fun uniquePaths(m: Int, n: Int): Int {    val dp = Array(m) { IntArray(n) }        for (i in 0 until m) {        dp[i][0] = 1  // first column    }    for (j in 0 until n) {        dp[0][j] = 1  // first row    }    for (i in 1 until m) {        for (j in 1 until n) {            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]        }    }    return dp[m - 1][n - 1]}

def uniquePaths(m, n):    dp = [[0] * n for _ in range(m)]        for i in range(m):        dp[i][0] = 1  # first column        for j in range(n):        dp[0][j] = 1  # first row        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]

How It Works

Key Insight

The number of unique paths to reach any cell (i, j) is the sum of paths from the cell above it (i-1, j) and the cell to its left (i, j-1). This is because the robot can only arrive at (i, j) from these two directions.

Base Cases

First row: All cells have exactly 1 path (can only move right).
First column: All cells have exactly 1 path (can only move down).

Recurrence Relation

For any cell (i, j) where i > 0 and j > 0:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

The Algorithm

Initialize: Create an m × n grid filled with zeros.
Fill first column: Set dp[i][0] = 1 for all rows (base case).
Fill first row: Set dp[0][j] = 1 for all columns (base case).
Fill remaining cells: For each cell (i, j), compute dp[i][j] = dp[i-1][j] + dp[i][j-1].
Return: The answer is dp[m-1][n-1] (bottom-right corner).

Complexity

Time O(m × n)

Space O(m × n)

We visit each cell exactly once to compute its value, giving us O(m × n) time complexity. The DP table requires O(m × n) space to store all intermediate results. Space optimization: Since each row only depends on the previous row, we can reduce space to O(n) by keeping only two rows in memory.