parikshan

unique-paths

Difficulty: Medium  ·  Topic: 2-D Dynamic Programming  ·  Practice it on parikshan: /practice/unique-paths/start

The story

A warehouse-automation team at a logistics company, say a Flexport or a Locus Robotics installation, wires up a new aisle layout. A picking robot starts at the top-left bay of an m x n shelf grid and must reach the dispatch dock at the bottom-right. To keep collisions out of the planner, the robot only moves right (down the aisle) or down (across to the next aisle). The simulation engineer needs to know, for a given layout, how many distinct routes the robot could take. The number drives the routing planner's stress test, the audit log's "path coverage" metric, and the QA team's verification harness. They send you m and n. They want the count.

The answer is one of the cleanest 2-D recurrences in computer science. Once you see it, you will recognise the same rectangular state space in every problem that compares two sequences or counts monotone paths through a grid.

What's actually being asked

Given an m x n grid, count the number of distinct paths from cell (0, 0) to cell (m-1, n-1) if each move goes only one cell right or one cell down.

Examples:

  • m=3, n=7 → 28 paths.
  • m=3, n=2 → 3 paths: RDD, DRD, DDR.
  • m=1, n=1 → 1 path (start equals end, do nothing).
  • m=1, n=10 → 1 path (a single straight line of rights).

The naive approach

Recurse: from any cell (i, j), the number of paths to the goal is the sum of paths from (i+1, j) and (i, j+1).

def paths(i, j, m, n):
    if i == m - 1 and j == n - 1: return 1
    total = 0
    if i + 1 < m: total += paths(i + 1, j, m, n)
    if j + 1 < n: total += paths(i, j + 1, m, n)
    return total

Correct, exponential. Every cell off the main diagonal is recomputed many times. For m = n = 20 this already crawls. For m = n = 100 the universe ends before the function returns.

The key insight

There are exactly two ways to arrive at cell (i, j): from the cell directly above (i-1, j), or from the cell directly to the left (i, j-1). The number of paths to (i, j) is therefore the sum of the paths to those two cells. That recurrence is the entire problem.

This is the gateway 2-D DP. The four DP questions:

  1. State: dp[i][j] = number of distinct paths from (0, 0) to (i, j).
  2. Base case: dp[0][j] = 1 for every j (only one way along the top row, all rights). dp[i][0] = 1 for every i (only one way down the left column, all downs).
  3. Transition: dp[i][j] = dp[i-1][j] + dp[i][j-1].
  4. Answer: dp[m-1][n-1].

Notice the geometry. The table is a rectangle. Every cell's answer is built from the cell directly above and the cell directly to the left. The table is filled row by row, left to right, and the answer lives in the bottom-right corner. Every 2-D DP you will see in this cluster has this same shape, just with different transition rules.

Step-by-step approach

Bottom-up, O(m n) time, O(m n) space:

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    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]

Because each row only needs the row above and the cell to its left, you can collapse the table to a single 1-D array:

def unique_paths(m, n):
    row = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            row[j] += row[j-1]
    return row[n-1]

O(m n) time, O(min(m, n)) space.

Worked example

m = 3, n = 3. Fill the table:

      j=0  j=1  j=2
i=0 [  1    1    1  ]
i=1 [  1    2    3  ]
i=2 [  1    3    6  ]
  • dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2.
  • dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3.
  • dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3.
  • dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6.

Return 6. ✓

Complexity

  • Time: O(m n) to fill every cell once.
  • Space: O(m n) for the full table, O(min(m, n)) with the rolling row.

For the constraint m, n ≤ 100 this is 10,000 cells, trivially fast.

There is also a closed form. Every path makes exactly m + n - 2 moves, of which m - 1 are down. The number of paths is therefore the binomial C(m + n - 2, m - 1). With the iterative integer-only product result = result * (a - i) // (i + 1), this runs in O(min(m, n)) with no DP table at all. Worth keeping in your pocket.

Common pitfalls

  • Forgetting the base case row and column: leaving them at 0 zeros out the entire table because the recurrence multiplies through zeros. Always initialise the first row and first column to 1.
  • Off-by-one between "m x n grid" and "indices": the goal cell is (m-1, n-1), not (m, n). Read the spec carefully.
  • Overflow in bounded-integer languages: C(198, 99) is around 4.5 x 10^58. Python handles it natively; Java needs BigInteger; C/C++ either takes a modulus or uses __int128 / big-int libraries.
  • Recursing without memoization: the brute-force recursion is exponential. If you want the recursive style, add @lru_cache or pass a memo dict.

Where this shows up in the enterprise

  • Warehouse robot path planning at Amazon Robotics, Locus, GreyOrange: counting monotone routes is a smoke test for the planner.
  • Maze-and-grid game design at Unity, Roblox, Riot: level designers use path-counting to balance difficulty.
  • Lattice models in quantitative finance: binomial option pricing trees count paths through a recombining lattice the same way.
  • Bioinformatics sequence alignment at Illumina, 23andMe: the DP table for global alignment uses the same rectangular shape, just with different transition rules.
  • Compiler diff tools (git diff, IDE merge views): the longest-common-subsequence DP is the same table shape, summing-with-max instead of summing-with-add.
  • AB-test bucket walks at Booking.com or Netflix: counting valid sequences of user states across a grid of event types.
  • Compliance-event ordering: counting valid orderings of two parallel event streams under "monotone in both" constraints.

The pattern is universal: any time the problem describes a rectangular state with two indices and a transition that looks at "the cell up" and "the cell left", you are in 2-D DP territory.

Variants you'll see elsewhere

  • unique-paths-ii: same grid but with obstacles. Set dp[i][j] = 0 for obstacle cells; everything else unchanged.
  • minimum-path-sum: replace + with min on per-cell costs; same shape.
  • longest-common-subsequence: two strings instead of dimensions; transition reads "diagonal +1 on match, else max of up/left".
  • edit-distance: three transitions instead of two on a mismatch: insert, delete, replace.
  • dungeon-game: fill the table from bottom-right to top-left when the constraint is "minimum starting health to survive".

Once the rectangular state space clicks, this whole family clicks at once.

How parikshan turns this into a learning loop

This is the entry point to the 2-D DP cluster, and the integrated loop is built to make the recurrence stick.

  1. Read this article. The recurrence is the entire idea.
  2. Solve in practice mode with the AI chat off. Before writing code, draw the 3 by 3 table on paper and fill it in by hand. The muscle that transfers is the table, not the code.
  3. Submit, take the verdict. If you missed the base-row initialisation, the small public tests catch it instantly. The bank's dynamic private tests include m = 1, n = 1 and m = 1, n = 10 to catch off-by-one errors.
  4. AI training: Optimise your solution. Ask the assistant to collapse it to O(min(m, n)) space, or to derive the binomial closed form. Each request costs a small slice of your integrity score, so spend it deliberately.
  5. Move to longest-common-subsequence in exam mode. The recurrence shape carries over almost verbatim, with one transition rule swapped. Solving it cold confirms you have generalised, not memorised.

The dispute flow rarely fires on counting problems (verdicts are unambiguous), but if a stress test seems to TLE on what you believe is an O(m n) solution, dispute it. A human reviewer can re-examine the time limit on the bank's reference.

In the AI-integrated workspace

2-D DP is where AI agents are simultaneously the most productive and the most dangerous on small inputs. The agent will happily generate a recursive solution that passes the 3 by 7 sample and silently times out on 50 by 50.

The 2027 engineer's discipline for 2-D DP:

  1. State the recurrence in English before the agent codes. "dp[i][j] is the count of paths to cell (i, j). Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Base: first row and first column all 1."
  2. Tell the agent to implement that recurrence iteratively. Not "solve unique-paths"; spell out the table fill order. Memoised recursion is acceptable but iterative is preferable for cache-friendliness.
  3. Verify on a 3 by 3 example by hand. Always. Fill the table, compare to the agent's output, only then trust the rest.
  4. Ask the agent to collapse memory. "Reduce to a single rolling row of length n." Read its diff; ensure it didn't break the base case.

That discipline turns a probabilistic answer into a deterministic, verified one. parikshan's loop is designed to train exactly that habit so when you walk into the workspace at Google Maps or Amazon Robotics, you direct the agent rather than approve its first guess.

unique-paths