This problem asks us to find the number of unique paths a robot can take from the top-left corner to the bottom-right corner of an m x n grid, given that the robot can only move down or right. This is a classic dynamic programming problem.

We can solve this efficiently using a space-optimized dynamic programming approach.

Intuition:

Imagine building a table where each cell (i, j) represents the number of unique paths to reach that cell from the top-left corner. The number of paths to reach (i, j) is the sum of the paths to reach (i-1, j) (coming from above) and (i, j-1) (coming from the left). The base cases are the first row and first column, where there is only one path to reach each cell.

Instead of storing the entire table, we can optimize space by using only one row and updating it iteratively. This works because to compute the number of paths for the current row, we only need the values from the previous row and the values from the current row that we have already computed.

Step-by-step thinking:

Initialize a 1D array `row` of size `n` with all elements set to 1. This represents the number of paths to reach each cell in the first row (or initial row).
Iterate `m - 1` times, representing the remaining rows (excluding the initial row).
In each iteration, create a new array `newRow` of size `n` filled with 1s. This will store the number of paths for the current row being calculated.
Iterate through `newRow` from right to left (from index `n - 2` down to 0).
For each cell `newRow[j]`, the number of paths is the sum of the number of paths to the cell to its right (`newRow[j + 1]`) and the number of paths to the cell directly above it (`row[j]`). `newRow[j] = newRow[j + 1] + row[j]`
After calculating all values for `newRow`, update `row` to be `newRow`, so `row` now represents number of paths to each cell in the current row.
After all rows have been processed, the value at `row[0]` represents the number of paths to reach the bottom-right corner. Return `row[0]`.

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

Learn Complexity

35. Matrix Path DP

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Constraints:

Learn

Topics

Hint

Use Cases