62. Unique Paths

Problem¶

Given an m x n grid, start at the top-left and reach the bottom-right by moving only right or down. Return how many different paths exist.

Example:

m = 3, n = 2

grid:
S .
. .
. E

paths = 3

Key trick¶

Use dynamic programming:

• Each cell can only be reached from:
  • the cell above
  • the cell to the left
• So:
  • dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

A shorter equivalent view is combinatorics:

• You must make exactly:
  • m - 1 down moves
  • n - 1 right moves
• Total paths:
  • \(\binom{m+n-2}{m-1}\)

Trap¶

• Forgetting moves are only right and down.
• Writing transitions with 4 directions.
• Mixing up m and n.
• Missing base cases:
  • first row is all 1
  • first column is all 1
• Using plain recursion without memoization, which is too slow.

Why is it interesting?¶

• It tests whether you can turn movement constraints into a DP recurrence.
• It also has a clean math shortcut, so it checks pattern recognition.

Python solution¶

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # dp[j] = number of ways to reach current row, column j
        # First row is all 1s because you can only move right.
        dp = [1] * n

        # For each next row:
        # dp[j] = ways from above + ways from left
        for _ in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j - 1]

        return dp[-1]

    def uniquePaths_2(self, m: int, n: int) -> int:
        # Total moves = (m - 1) downs + (n - 1) rights
        # Choose where the downs go, or equivalently where the rights go.
        return math.comb(m + n - 2, m - 1)

• uniquePaths
• Time: \(O(mn)\)
• Space: \(O(n)\)
• uniquePaths_2
• Time: \(O(\min(m, n))\) for big integer combinatorics in practice
• Space: \(O(1)\) ignoring big integer storage

Comment on my solution¶

• Your main idea is correct:
  • dp[i][j] is the number of ways to reach cell (i, j).
• The final recurrence is also correct:
  • from left plus from above.
• Good recovery after noticing the 4-direction recurrence was wrong.

A few improvements:

• The final loop calling visit(i, j) everywhere is unnecessary if you use bottom-up DP.
• The extra visit(0,0) at the end does nothing.
• A -1 matrix plus recursion is more complex than needed here.
• Recursive DFS is fine with memoization, but iterative DP is simpler and more interview-friendly.

## Solution

# Work
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # m = 3, n = 2 -> 3
        # 1. Right -> Down -> Down
        # 2. Down -> Down -> Right
        # 3. Down -> Right -> Down
        #
        #      start x
        #      x     x
        #      x     end
        #
        # - don't enumerate
        # - BFS seems complicated because we can't mark visited node as
        #   they can be visited by many different valid paths
        # - deduplicating after enumating path is bad idea
        # - (i, j) pairs in a valid path must be unique
        # - maybe DP where dp[i,j] is the number of unique way to reach
        #   (i, j)
        #   - so what would be the recursion formula?
        #     - dp[i,j] = dp[i-1,j] + dp[i+1,j] + dp[i,j-1] + dp[i,j+1]
        #       for valid indices (in mxn matrix)
        #   - maybe we can write recursive function with a dp matrix for memoization
        # - I forgot the constraint that the robot can only move down or right
        #   - so the recursion above is wrong
        #   - but maybe the DP idea is still right
        #   - dp[i,j] = dp[i,j-1] + dp[i+1,j]
        dp = [[-1 for _ in range(n)] for _ in range(m)]
        dp[0][0] = 1

        def visit(i,j):
            if i < 0 or i >= m or j < 0 or j >= n:
                return 0
            if dp[i][j] != -1:
                return dp[i][j]
            # (i,j) can only be reached from the left or from above
            dp[i][j] = visit(i,j-1) + visit(i-1,j)
            return dp[i][j]
        for i in range(m):
            for j in range(n):
                visit(i,j)
        visit(0,0)
        return dp[m-1][n-1]

Solution().uniquePaths(3,2) # 3
Solution().uniquePaths(3,7) # 28

Your solution can be simplified to:

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        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[-1][-1]

• This keeps your DP idea.
• It makes the base cases obvious.
• It is easier to explain in an interview.

Extra¶

Combinatorics (arrangements and combinations)¶

• Give the minimum background in combinatorics to understand the above combinatorics solution.
• Emphasize on the combinatorics intuition and why it makes sense
• Provide the definition (formula) and explain with a small example \(\binom{n}{k}\)

The whole combinatorics idea is just this:

• Every valid path is a sequence of moves.
• The robot must make:
  • exactly m - 1 down moves
  • exactly n - 1 right moves
• So every path has exactly:
  • m + n - 2 total moves

For example, if m = 3 and n = 2:

• You need:
  • 2 downs
  • 1 right
• So every path is a length-3 sequence made from:
  • D, D, R

The possible paths are:

DDR
DRD
RDD

That is why the answer is 3.

Why combinatorics fits perfectly¶

You are not really exploring a grid.

You are really arranging moves in order.

A path is completely determined by:

• which positions in the move sequence are D
• or equivalently, which positions are R

So the problem becomes:

• In a sequence of length m + n - 2,
• choose m - 1 positions for the down moves.

That count is:

or equivalently:

Both are the same count.

What does \(\binom{n}{k}\) mean?¶

\(\binom{n}{k}\) means:

• the number of ways to choose k items from n items
• when order does not matter

Example:

• Choose 2 people from {A, B, C}

Possible choices:

AB
AC
BC

So:

Formula¶

Where factorial means:

Example:

Why that formula makes sense¶

If order mattered, the number of ways to fill k chosen positions from n would be:

But in combinations, order does not matter.

So each group of k chosen items gets counted k! times, one for each ordering.

That is why we divide by k!:

Back to Unique Paths¶

Suppose m = 3, n = 7.

You must make:

• 2 downs
• 6 rights

So you have 8 total move slots.

Now ask:

• In those 8 slots, which 2 are the down moves?

That is:

Same as:

• choose where the 6 right moves go:

The key intuition to remember¶

A path is not a geometric object here.

It is just a string of moves like:

RRDRRDDR

So counting paths becomes counting distinct arrangements of repeated letters:

• D repeated m - 1 times
• R repeated n - 1 times

That is exactly what combinations count.

Combinatorics follow-up #1¶

Be precise with the word you're using here.

• What is an arrangement?
• What is a combination?

• Arrangement
  • A placement of items in an order.
  • Order matters.

Example:

A, B, C

Arrangements of 2 items:
AB
BA
AC
CA
BC
CB

• AB and BA are different arrangements.

• Combination

  • A selection of items without caring about order.
  • Order does not matter.

Example:

A, B, C

Combinations of 2 items:
AB
AC
BC

• AB and BA are the same combination.

For this problem:

• A path itself is an ordered sequence of moves:
  • so it is an arrangement of moves
• But to count such paths, we can instead choose:
  • which positions are D
• That counting step is a combination:
  • choose m - 1 positions among m + n - 2 positions

So:

• path representation:
  • arrangement
• counting method:
  • combination

Combinatorics follow-up #2¶

The confusion comes here when the set we are arranging/combining is not a set but a multiset like with 2 downs and 1 right like in the example above.

Yes - that is exactly the subtle point.

With D, D, R, the items are not all distinct, so we must be careful with words.

What changes with a multiset¶

If you had 3 distinct symbols:

D1, D2, R

then the arrangements would be:

D1D2R
D1RD2
D2D1R
D2RD1
RD1D2
RD2D1

That is 3! = 6.

But in the real problem, D1 and D2 are identical:

D, D, R

So some of those are the same path:

DDR
DRD
RDD

Now there are only 3.

Precise wording¶

• Arrangement
  • Usually means ordering items.
  • If items are distinct, each permutation counts separately.
• Arrangement of a multiset
  • Ordering items when some are identical.
  • Swapping identical items does not create a new arrangement.

In this problem, paths are:

• arrangements of the multiset containing:
  • m - 1 copies of D
  • n - 1 copies of R

Why combinations still work¶

Instead of arranging repeated symbols directly, say:

• there are m + n - 2 move positions
• choose which m - 1 positions hold D
• all remaining positions must be R

That is a combination because:

• you are choosing positions
• the order in which you choose those positions does not matter

Example with D, D, R:

• positions are:

1 2 3

Choose 2 positions for D:

{1, 2} -> DDR
{1, 3} -> DRD
{2, 3} -> RDD

So the count is:

Clean mental model¶

• The path is an ordered sequence.
• But because moves repeat, it is best viewed as:
  • an arrangement of a multiset
• The easiest way to count those arrangements is:
  • choose the positions of one move type
• That is why combinations appear.