Room 04 · The Grind — 2-D Dynamic Programming

Unique Paths

MEDIUM✓ CHIP-TIMEDLC #62 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: A runner starts in the top-left corner of an m×n grid and can only step right or down. Count how many distinct routes reach the bottom-right corner.

A runner starts in the top-left corner of a grid with m rows and n columns, and every move can only go one step right or one step down. The task is to count how many distinct routes reach the bottom-right corner.

Two routes are different if they take their right/down steps in a different order anywhere along the way, even if they pass through the exact same set of cells overall. There are no obstacles to dodge in this version — every cell can be stepped on.

The output required is simply that total count of distinct routes.

grid dimensions m and n are both at least 1
movement is limited to a single step right or a single step down
grid sizes stay small enough for an O(m·n) table
the answer is a single count of routes, always at least one

EX 01

m = 1 · n = 1

→ 1

single cell, already there

EX 02

m = 1 · n = 6

→ 1

single row, only right moves possible

EX 03

m = 6 · n = 1

→ 1

single column, only down moves possible

The hintstake only what you need

HINT 1 THE NUDGE

Every route is a sequence of right and down steps — a cell reached partway through looks identical no matter which order the earlier steps came in. What does that overlap suggest?

HINT 2 THE STRUCTURE

The number of ways to reach a cell is just the ways to reach the cell above it plus the ways to reach the cell to its left — every route arrives from exactly one of those two neighbours.

HINT 3 ONE STEP FROM THE ANSWER

Fill a table with ways[r][c] = ways[r-1][c] + ways[r][c-1], seeded with 1s along the first row and column. Only the previous row of the table is ever needed again.

Coach's boardthe pattern, step by step

THE TABLE FILLPATTERN · 2-D DPa 3×3 grid, moves: right or down

STEP 1

One way to stand at the start: doing nothing. That seeds the whole table.

STEP 1 / 7 · ← → WORK TOO

The splitstwo paces, two languages

grind/unique-paths.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        row = [1] * n
        for _ in range(m - 1):
            for c in range(1, n):
                row[c] += row[c - 1]
        return row[-1]

TIME O(M·N)SPACE O(N)PYTHON · RACE PACE · 7 LN

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        def paths(r, c):
            if r == m - 1 or c == n - 1:
                return 1
            return paths(r + 1, c) + paths(r, c + 1)

        return paths(0, 0)

TIME O(2^(M+N))SPACE O(M+N)PYTHON · TRAINING PACE · 8 LN

class Solution {
    public int uniquePaths(int m, int n) {
        int[] row = new int[n];
        Arrays.fill(row, 1);
        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                row[c] += row[c - 1];
            }
        }
        return row[n - 1];
    }
}

TIME O(M·N)SPACE O(N)JAVA · RACE PACE · 12 LN

class Solution {
    private int m, n;

    public int uniquePaths(int m, int n) {
        this.m = m;
        this.n = n;
        return paths(0, 0);
    }

    private int paths(int r, int c) {
        if (r == m - 1 || c == n - 1) {
            return 1;
        }
        return paths(r + 1, c) + paths(r, c + 1);
    }
}

TIME O(2^(M+N))SPACE O(M+N)JAVA · TRAINING PACE · 16 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED