Unique Paths

Unique Paths is the classic grid problem. The interviewer uses it to check if you can turn a movement puzzle into a clean grid of numbers. The trick is small. Every cell is just the sum of two neighbors. Once you see that, you are done.

🎯 The Problem

You have a grid and a robot moving through it. Here are the rules.

• The grid has some rows and columns.
• The robot starts in the top-left corner.
• The robot wants to reach the bottom-right corner.
• It can only step right or step down. No other move.
• You return the count of different paths that reach the goal.

For a grid of 3 rows by 7 columns, there are many ways to weave right and down. The answer is 28.

Input:  m = 3, n = 7
Output: 28

Explanation: The robot can only move right or down,
and there are 28 distinct routes from top-left to bottom-right.

Here is the movement. The robot starts at the top-left and only goes right or down.

🐢 Approach 1: Plain Recursion (Brute Force)

The idea in one line: let the robot try every route and count the ones that reach the goal.

The idea:

• From any cell, the robot can go right or go down.
• Paths from a cell equal paths from the right cell plus paths from the cell below.

How it works:

• Write a function “how many paths from row r, column c to the end?”
• It calls itself on the right cell and the cell below, then adds the two answers.
• Reaching the goal cell is one finished path, so return one.
• Stepping off the grid is a dead path, so return zero.

Why it is weak:

• It re-walks the same cells again and again from different routes.
• The time grows exponentially.

Here is the plain recursion code:

def unique_paths(m, n):
    def dfs(row, col):
        if row == m - 1 and col == n - 1:
            return 1
        if row == m or col == n:
            return 0
        return dfs(row + 1, col) + dfs(row, col + 1)

    return dfs(0, 0)

⚡ Approach 2: Add Memory With Memoization (Better)

The idea in one line: a cell’s path count never changes, so compute it once and store it.

The idea:

• The number of paths from cell (r, c) to the end is always the same.
• The recursion keeps re-solving the same cell.

How it works:

• Keep a 2D table the same shape as the grid.
• The first time we find a cell’s path count, we save it.
• Next time that cell comes up, we read the saved value.
• This is memoization, caching each cell’s answer so it is computed once.

Why it is faster:

• Each cell is solved once.
• The time drops to O(m times n).

Here is the memoized recursion:

from functools import lru_cache


def unique_paths(m, n):
    @lru_cache(None)
    def dfs(row, col):
        if row == m - 1 and col == n - 1:
            return 1
        if row == m or col == n:
            return 0
        return dfs(row + 1, col) + dfs(row, col + 1)

    return dfs(0, 0)

⚡ Approach 3: Bottom-Up Tabulation (Better)

The idea in one line: flip the direction and fill a grid from the top-left outward.

The idea:

• Instead of recursing toward the goal, build out from the start.
• Make a 2D grid dp where dp[r][c] holds the paths to reach that cell.

How it works:

• The first row has one path each. The robot can only come from the left.
• The first column has one path each. It can only come from above.
• Every other cell is the cell above plus the cell to its left.
• Tabulation fills the grid in order so each cell has its two neighbors ready.

Why it is solid:

• Each of the m times n cells is filled once.
• No recursion stack to worry about.

Here is the 2D grid filling up for a small 3 by 3 case. Each cell is the count of paths to reach it.

🚀 Approach 4: Space-Optimized One Row (Best)

The idea in one line: each cell needs only the cell above and the cell to its left, so keep just one row.

The idea:

• The full grid is not needed in memory.
• We keep a single row and roll it down.

How it works:

• Process the grid row by row.
• The value already sitting in a slot is the cell from the row above.
• The value just to the left in the same row is the left neighbor.
• Add the slot’s old value to the left value, and store it back.

Why it is best:

• Just as fast as the 2D table.
• The memory drops from O(m times n) to O(n).

Steps to Solve

1. Make a single array dp of length n. Fill it all with 1, since the first row has one path per cell.
2. Loop over each remaining row, from the second row to the last.
3. Inside each row, loop over the columns from the second column to the last.
4. Set dp[c] to dp[c] plus dp[c - 1]. The old dp[c] is the cell above, and dp[c - 1] is the cell to the left.
5. The first column stays 1 the whole time, since there is only one way down the edge.
6. After the last row, dp[n - 1] holds the total number of paths.

#include <stdio.h>

int uniquePaths(int m, int n) {
    int dp[100];
    for (int c = 0; c < n; c++) dp[c] = 1;   // first row: one path each

    for (int r = 1; r < m; r++) {
        for (int c = 1; c < n; c++) {
            dp[c] = dp[c] + dp[c - 1];        // above + left
        }
    }
    return dp[n - 1];
}

int main(void) {
    int m = 3, n = 7;
    printf("%d\n", uniquePaths(m, n));
    return 0;
}

28

#include <iostream>
#include <vector>
using namespace std;

int uniquePaths(int m, int n) {
    vector<int> dp(n, 1);                 // first row: one path each

    for (int r = 1; r < m; r++) {
        for (int c = 1; c < n; c++) {
            dp[c] = dp[c] + dp[c - 1];     // above + left
        }
    }
    return dp[n - 1];
}

int main() {
    int m = 3, n = 7;
    cout << uniquePaths(m, n) << endl;
    return 0;
}

28

public class UniquePaths {
    public static int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        for (int c = 0; c < n; c++) dp[c] = 1;   // first row: one path each

        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                dp[c] = dp[c] + dp[c - 1];        // above + left
            }
        }
        return dp[n - 1];
    }

    public static void main(String[] args) {
        int m = 3, n = 7;
        System.out.println(uniquePaths(m, n));
    }
}

28

def unique_paths(m, n):
    dp = [1] * n                  # first row: one path each

    for r in range(1, m):
        for c in range(1, n):
            dp[c] = dp[c] + dp[c - 1]   # above + left
    return dp[n - 1]


m, n = 3, 7
print(unique_paths(m, n))

28

function uniquePaths(m, n) {
  const dp = new Array(n).fill(1);   // first row: one path each

  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      dp[c] = dp[c] + dp[c - 1];      // above + left
    }
  }
  return dp[n - 1];
}

const m = 3, n = 7;
console.log(uniquePaths(m, n));

28

Let us walk through the Python version line by line. The why behind each line is what makes the grid click.

dp = [1] * n makes one row of counts, all set to one. This stands for the very first grid row. The robot can only slide right along the top, so every top cell has exactly one path.

for r in range(1, m): moves down the grid one row at a time. We start at row one, not row zero, because row zero is already filled with ones.

for c in range(1, n): walks across the columns, starting at column one. Column zero stays one the whole time, since the only way down the left edge is straight down.

dp[c] = dp[c] + dp[c - 1] is the transition, and it carries the whole idea. The old dp[c] still holds the value from the row above, because we have not overwritten it yet. The dp[c - 1] is the cell just to the left in this same row. Adding them gives the paths into this cell.

return dp[n - 1] gives the answer. After the last row, the final slot holds the count of all paths to the bottom-right corner.

⏱️ Time and Space Complexity

Plain recursion is exponential, since it re-walks the same cells over and over. Memoization and 2D tabulation both visit each of the m times n cells once, so they run in O(m times n) time. The space-optimized version keeps a single row, so it uses the least memory while staying just as fast.

🧩 Key Takeaways

• ✅ The robot can only move right or down, which keeps the choices simple.
• ✅ Each cell holds the number of paths to reach it from the start.
• ✅ The transition is just cell above plus cell to the left.
• ✅ The first row and first column are all ones, since there is one way along each edge.
• ✅ One rolling row replaces the full grid and saves memory.

🚀 What’s Next?

• Longest Common Subsequence
• Partition Equal Subset Sum