Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Unique Paths
• Main tags: Math, Dynamic Programming, Combinatorics

What the problem is really asking

There is an m x n grid. A robot starts in the top-left corner and wants to reach the bottom-right corner. The robot can only move right or down.

At first glance, it looks like a pathfinding problem. It is not. There are no obstacles, no costs, and no choices about which cells are allowed. Every valid path is simply a sequence of moves:

• exactly m - 1 down moves
• exactly n - 1 right moves

So the real task is to count how many different orders those moves can appear in.

The easiest solution to derive: dynamic programming

Dynamic programming is the most natural interview starting point.

Let dp[row][column] mean the number of ways to reach that cell.

For any interior cell, the robot can only arrive in two ways:

• from the cell above it
• from the cell to its left

That gives the recurrence:

dp[row][column] = dp[row - 1][column] + dp[row][column - 1]

The first row and first column are simple: every cell there has exactly one way to be reached, because the robot can only move in a straight line.

This solution is already good:

• Time: O(m * n)
• Space: O(m * n), or O(n) with a rolling row

It is also a very useful derivation step, because it reveals the structure of the problem clearly.

The stronger observation: this is really a combinations problem

Once the grid is reframed as “arrange the moves,” the problem becomes simpler.

Any valid path must contain:

• m - 1 down moves
• n - 1 right moves

That means every path has exactly m + n - 2 total moves. The only thing that changes from one path to another is which of those positions are down moves, or equivalently which are right moves.

So the answer is:

C(m + n - 2, m - 1)

or equivalently:

C(m + n - 2, n - 1)

This is the optimal solution for the original problem because it counts the paths directly instead of filling the whole grid.

How to derive the optimal solution in an interview

A clean way to derive it is:

1. Start with the recurrence: ways to a cell equals ways from top plus ways from left.
2. Notice that without obstacles, the exact route through the grid does not matter; only the sequence of right and down moves matters.
3. Count how many total moves there are.
4. Choose which of those move positions will be down moves, or right moves.

That turns a grid DP problem into a simple binomial coefficient.

Even if the combinatorics insight does not come immediately, arriving at the DP first is still strong interview performance because it is correct, easy to justify, and often leads naturally to the counting shortcut.

Best approach

For this exact problem, the combinatorics solution is the best default answer.

• Time: O(min(m, n))
• Extra space: O(1)

In practice, it is best to compute the binomial coefficient with a multiplicative loop instead of factorials. That avoids large intermediate values in fixed-width languages and keeps the code straightforward.

The DP solution is still worth remembering because it generalizes more easily when the interviewer adds obstacles or other grid constraints.

Python solution

from typing import Final


def count_unique_paths(row_count: int, column_count: int) -> int:
    """Return the number of valid right/down paths in an empty grid."""
    if row_count <= 0 or column_count <= 0:
        raise ValueError("Grid dimensions must be positive integers.")

    total_moves: Final[int] = row_count + column_count - 2
    downward_moves: Final[int] = row_count - 1

    # Choose the smaller side of the binomial coefficient:
    # C(total_moves, downward_moves) == C(total_moves, rightward_moves)
    chosen_moves = min(downward_moves, total_moves - downward_moves)

    combination_count = 1
    for step_index in range(1, chosen_moves + 1):
        numerator_term = total_moves - chosen_moves + step_index
        combination_count = combination_count * numerator_term // step_index

    return combination_count


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return count_unique_paths(row_count=m, column_count=n)

This implementation uses the combinatorics insight directly. It computes the binomial coefficient incrementally, so it stays precise and avoids the overhead of factorial-based code.

Why this works

Every valid path is a sequence of m + n - 2 moves, and exactly m - 1 of those moves must be down moves. Once the positions of the down moves are chosen, the remaining positions must be right moves, so each valid path corresponds to exactly one choice of positions.

That creates a one-to-one mapping between:

• valid robot paths
• ways to choose m - 1 positions from m + n - 2

Because the mapping is exact, the number of paths is exactly the binomial coefficient the code computes.

Interview follow-ups

What changes if some cells are blocked?

The combinatorics shortcut no longer works, because not every ordering of right and down moves is legal anymore. The right replacement is dynamic programming over the grid. Each open cell still gets its path count from the top and left neighbors, but a blocked cell contributes zero paths. This works because the last move into any open cell must still come from one of those two directions. The time cost is O(m * n), and the space can be reduced to O(n) with a rolling row.

What if the interviewer asks for the DP version first and then asks to optimize space?

Start with the full m x n table because it makes the recurrence obvious and easy to explain. Then observe that each row only depends on the current row and the previous row. That means a single one-dimensional array is enough: update from left to right so the current entry holds “from above” and the previous entry in the same row holds “from the left.” The result stays O(m * n) time but drops from O(m * n) space to O(n) space.

What if the grid is so large that the interviewer cares about overflow in fixed-width languages?

That is exactly why the multiplicative binomial formula is preferable to factorials. Factorials create enormous intermediate values even when the final answer still fits. The incremental product-and-divide approach keeps the numbers much smaller along the way. In Python this is less of a concern because integers grow automatically, but in Java, C++, or Go it is an important implementation detail. If the interviewer adds a modulus, the solution shifts again: use modular arithmetic and, if needed, modular inverses instead of ordinary division.

What if the robot can also move diagonally down-right?

Now the recurrence changes because each cell can be reached from three predecessors instead of two: top, left, and top-left diagonal. The clean solution is dynamic programming, not combinatorics, because the allowed step types create a more complex counting problem. The recurrence becomes dp[row][column] = dp[row - 1][column] + dp[row][column - 1] + dp[row - 1][column - 1], with matching base cases. The tradeoff is straightforward: the idea is still simple, but the elegant closed-form shortcut for the original problem disappears.