What is the brute force approach and complexity for Unique Paths?

Count the paths into a cell by adding the counts of the two cells that can feed it with time complexity O(2^(M + N)) and space complexity O(M + N).

What is the optimal approach and complexity for Unique Paths?

Keep one row of counts; for each cell, row[c] += row[c − 1] with optimal time complexity O(M · N) and space complexity O(N).

How do you identify the pattern for Unique Paths?

Look for key signals in the prompt: "move only down or right" indicates A cell can only be entered from above or from the left. The last move decides which counts to add.; "how many different paths" indicates The goal is a count, not a shortest distance. Add the counts of the cells that feed each cell.; "from the top-left to the bottom-right" indicates The answer for the corner is built from the answers for the cells before it, so fill the table in order..

Unique Paths

Medium·LeetCode #62Basic Anchor

LeetCode

Jump:

30-Second Mental ModelDP — Grid, Paths in a grid (count: dp[r][c] = dp[r−1][c] + dp[r][c−1])

Complexity:O(2^(M + N))→O(M · N)

Key Insight

Only one row of counts is needed. Row r is built from row r − 1 and the cell to its left. Going left to right, row[c] += row[c − 1] turns the old row into the new one. Before that line runs, row[c] still holds the cell above, and row[c − 1] already holds the cell to the left.

Core Validity Invariant

After row r is done, row[c] is the number of paths to cell (r, c), because the update adds exactly the cell above and the cell to the left.

Problem

A robot stands in the top-left corner of a grid with m rows and n columns. It wants to reach the bottom-right corner. Each move takes it one cell down or one cell right. It never moves up or left.

Return how many different paths it can take.

Input

Two whole numbers: m, the number of rows, and n, the number of columns.

Output

The number of different paths from the top-left cell to the bottom-right cell.

Example 1

Input: m = 3, n = 7

Output: 28

A path has 2 downs and 6 rights, in some order. Choose which 2 of the 8 moves are down: C(8, 2) = 28.

Example 2

Input: m = 3, n = 2

Output: 3

The three paths are Right → Down → Down, Down → Down → Right and Down → Right → Down.

Constraints

• 1 ≤ m, n ≤ 100
• The tests are chosen so that the answer is at most 2 × 10^9.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Every path has the same number of moves. How many moves is that, in terms of m and n?
2.
The robot never moves up or left. What does that say about how many downs and rights every path has?
3.
To reach a cell that is not in the top row or the left column, what was the last move?
4.
If I know how many paths reach the cell above and the cell to its left, how do I count the paths to this cell?
5.
Would the length of the shortest route to the corner tell me how many routes there are? Why or why not?

Brute force approach

Idea

Let ways(r, c) be the number of paths from the top-left to cell (r, c). The last move came from above or from the left, so ways(r, c) = ways(r−1, c) + ways(r, c−1). The top row and the left column have exactly one path each, and that stops the recursion. Start from the bottom-right corner.

Thinking process

1
Take a 3 × 3 board. The corner (2, 2) is fed by (1, 2) and by (2, 1).
2
ways(1, 1) = ways(0, 1) + ways(1, 0) = 1 + 1 = 2. Then ways(1, 2) = ways(0, 2) + ways(1, 1) = 1 + 2 = 3, and ways(2, 1) = ways(1, 1) + ways(2, 0) = 2 + 1 = 3.
3
So ways(2, 2) = ways(1, 2) + ways(2, 1) = 3 + 3 = 6. That is the answer for a 3 × 3 board.
4
The recursion remembers nothing. ways(1, 1) is worked out once under (1, 2) and again under (2, 1).
5
Each call above the top row and the left column makes two more calls, so the calls branch again at every step back.

Visual

Each circle is one call ways(r, c), labelled `r,c`. Blue = the current call. Orange = a cell already worked out on another branch, so brute force repeats it. Green = a call that has returned. Purple = the answer. Base calls on the first row and column return 1 straight away.

Brute force on a 3 × 3 boardm = 3, n = 3step 1/17

board

·call

calls

This call

call: ways(2, 2)
calls so far: 1
cells on the board: 9

Repeated calls

none yet

Call ways(2,2): ask the cell above and the cell to the left

To reach (2, 2), the last step came down or right. So ask for (1, 2) and for (2, 1).

Code & Implementation

brute.cpp

class Solution {
    // ways(r, c): how many paths lead from (0, 0) to (r, c).
    // A path reaches (r, c) either from the cell above or from the cell to the left.
    int ways(int r, int c) {
        if (r == 0 || c == 0) return 1;            // first row / first column: only one straight path
        return ways(r - 1, c) + ways(r, c - 1);    // the last step came down or right
    }

public:
    int uniquePaths(int m, int n) {
        return ways(m - 1, n - 1);                 // the bottom-right corner
    }
};

Complexity

Time O(2^(M + N))Space O(M + N)

M is the number of rows and N is the number of columns. A call makes two calls, and the chain of calls back to the top row or the left column is at most M + N − 2 long, so there are at most 2^(M+N) calls. The space is the length of the longest chain. On a 7 × 7 board the recursion makes 1,847 calls for 49 cells.

Better approach

Why brute force is slow

The recursion asks for the same cell many times. On a 7 × 7 board it makes 1,847 calls for 49 cells.

What repeated work are we doing?

A cell's count is needed by every cell below it and to its right. The recursion works it out again for each of them.

What information can we reuse?

A table of counts. A cell only reads two numbers that are already stored, so it costs one addition.

New approach

Idea

Store each cell's count in a table dp[r][c], and fill it row by row. The top row and the left column are 1. Every other cell is the sum of the cell above and the cell to its left. Both are already filled, so each cell is worked out only once.

Thinking process

1
On the 3 × 3 board, set row 0 and column 0 to 1.
2
dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2. Then dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3.
3
dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3. Then dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6.
4
It is the same rule as the brute force. The table only remembers each value, so no value is worked out twice.

Code & Implementation

better.cpp

class Solution {
public:
    int uniquePaths(int m, int n) {
        // dp[r][c] = number of paths from (0, 0) to (r, c). Start with all 1s:
        // the first row and first column stay 1, and the rest is filled in below.
        vector<vector<long long>> dp(m, vector<long long>(n, 1));
        for (int r = 1; r < m; r++)
            for (int c = 1; c < n; c++)
                dp[r][c] = dp[r - 1][c] + dp[r][c - 1];   // a path ends by coming from above or from the left
        return (int)dp[m - 1][n - 1];
    }
};

Complexity

Time O(M · N)Space O(M · N)

M is the number of rows and N is the number of columns. There is one table cell per board cell, and each cell does one addition. The table keeps all M · N counts, which is why the space is O(M · N).

Optimized approach

Idea

Start from brute force

The brute force counts back from the corner. Each cell's count is built from the counts of the cells above and to the left, and the recursion works those counts out again every time it needs them.

Find the repeated work

Row r only reads row r − 1 and the cell to its left. Rows further up are never read again, so keeping every row is wasted memory.

Define the state — what variables do I need?

row[c]: The number of paths to column c. Before row r is processed it holds row r − 1, and after it holds row r.
r: The row being filled, from 1 to M − 1.
c: The column being filled, from 1 to N − 1. Column 0 is always 1.

Define validity

After row r is done, row[c] is the number of paths to cell (r, c), because the update adds exactly the cell above and the cell to the left.

Define the transitions — when does each pointer move, and why is it safe?

Before the loops

row[c] = 1 for every column

Row 0 has one path to each cell: all of its moves go right.

Each row r from 1, each column c from 1, left to right

row[c] += row[c − 1]

row[c] is still the cell above, and row[c − 1] is already the cell to the left in this row.

Column 0 in rows 1 and below

Do nothing, so row[0] stays 1

The first column has one path to each cell, and nothing adds to it.

What does the current window add to the answer?

After the last row, row[N − 1] is the number of paths to the bottom-right corner, so we return it.

Code & Implementation

optimal.cpp

class Solution {
public:
    int uniquePaths(int m, int n) {
        // One row: row[c] holds dp[r][c] for the row being filled.
        vector<long long> row(n, 1);                // row 0: every cell has exactly one path
        for (int r = 1; r < m; r++)
            for (int c = 1; c < n; c++)
                // Before this line, row[c] is still dp[r-1][c] (from above) and row[c-1] is already dp[r][c-1] (from the left).
                row[c] += row[c - 1];
        return (int)row[n - 1];
    }
};

Complexity

Time O(M · N)Space O(N)

M rows and N columns give one update per cell, so the time is O(M · N). Only one row of N counts is kept, so the space is O(N).

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Count the paths into a cell by adding the counts of the two cells that can feed it	O(2^(M + N))	O(M + N)
Better	dp[r][c] = dp[r−1][c] + dp[r][c−1], with every cell worked out once and stored	O(M · N)	O(M · N)
Optimal	Keep one row of counts; for each cell, row[c] += row[c − 1]	O(M · N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“move only down or right”A cell can only be entered from above or from the left. The last move decides which counts to add.
“how many different paths”The goal is a count, not a shortest distance. Add the counts of the cells that feed each cell.
“from the top-left to the bottom-right”The answer for the corner is built from the answers for the cells before it, so fill the table in order.

cell (r, c)+two feeders: (r−1, c) and (r, c−1)+count the ways into the cell+dp = above + left→DP — Grid, Paths in a grid (count: dp[r][c] = dp[r−1][c] + dp[r][c−1])

This is the anchor of the Paths sub-pattern. Every cell's count is the sum of the two cells that can feed it, and the top row and the left column start at 1. No cell is blocked here, so there is no validity rule at all. The next questions change one rule each: an obstacle forces a count to 0, a cost turns the sum into a minimum, and more feeding cells change the list of neighbours.

Don't make this mistake

Pattern confusion: shortest-path search (BFS)

✗ return dist[m - 1][n - 1]; // BFS: the number of moves to the corner

✓ return dp[m - 1][n - 1]; // the number of paths to the corner

Every path to the bottom-right corner has the same length, m + n − 2 moves, so a BFS only finds that length. On a 3 × 3 board the BFS reaches the corner after 4 moves, but there are 6 paths. A length does not tell you how many routes there are.

Pattern confusion: listing every path without a table

Walking every path (DFS or plain recursion) counts the paths one by one. On a 10 × 10 board the plain recursion makes 97,239 calls for 100 cells. The number of paths grows much faster than the number of cells, so the table, which does M · N steps, is the only version that scales.

Setting the first row or column to 0

✗ dp[0][c] = 0; // and dp[r][0] = 0

✓ dp[0][c] = 1; // and dp[r][0] = 1

A 0 on the edge stops the sums: every cell is built from edge cells, so every cell becomes 0. For 3 × 7 the table is all 0s, and the answer is 0 instead of 28.

Off-by-one: reading row m or column n

✗ return dp[m][n];

✓ return dp[m - 1][n - 1];

Rows are numbered 0 to m − 1 and columns 0 to n − 1, so index m (or n) is one past the end of the table. The answer is the bottom-right cell.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Grid translate into production architectures and low-level memory mechanics.

LLD Architecture