62. Unique Paths - Detailed Explanation

Problem statement

You are given two integers, m and n, which represent the dimensions of an m x n grid. A robot is initially located in the top-left corner of this grid (cell (0, 0)). The robot can only move either down or right at any point in time. The goal is for the robot to reach the bottom-right corner of the grid (cell (m - 1, n - 1)). Your task is to determine how many unique paths exist for the robot to get from the top-left corner to the bottom-right corner.

Example 1

• Input:
  m = 3, n = 7
• Output:
  28
• Explanation:
  There are 28 distinct ways for the robot to reach the bottom-right corner by only moving right or down.

Example 2

• Input:
  m = 3, n = 2
• Output:
  3
• Explanation:
  The three unique paths are:
  1. Right → Down → Down
  2. Down → Down → Right
  3. Down → Right → Down

Example 3

• Input:
  m = 7, n = 3
• Output:
  28
• Explanation:
  Similarly, there are 28 distinct ways for the robot to move from (0,0) to (6,2) using only right and down moves.

Hints and intuition

• Hint 1:
  Think about breaking the question into subproblems. The number of ways to reach any given cell is the sum of the ways to reach the cell above it and the ways to reach the cell on its left.

• Hint 2:
  Consider using dynamic programming (DP) to build up a solution for the entire grid. Alternatively, notice that the robot must make exactly (m-1) down moves and (n-1) right moves in some order, which leads to a combinatorial solution.

Hint 1 is the whole pattern in one line. Unique Paths is a multidimensional dynamic programming question, built on a grid table rather than a take-or-skip choice. Every member of that family has the same shape. You fill a table, and each entry combines a fixed set of earlier entries, one per allowed choice. Knapsack offers two choices, take the item or skip it. Here the two choices that reach a cell are arrive from above and arrive from the left. Recognizing that shape is worth more than memorizing this one answer, which is why most short lists of recurring coding interview patterns put table-building DP near the top.

Detailed approaches

Approach A: dynamic programming

Idea

• Create a 2D DP array dp where dp[i][j] represents the number of unique paths to cell (i, j).
• Base cases:
  • The starting cell dp[0][0] is 1 (only one way to be at the start).
  • For the first row (i = 0), there is only one way to move (all rights) so dp[0][j] = 1.
  • For the first column (j = 0), there is only one way to move (all downs) so dp[i][0] = 1.
• Recurrence:
  For any cell (i, j), the number of paths to reach it is:

  dp[i][j] = dp[i-1][j] + dp[i][j-1]

  This holds because the robot can only arrive from the top or from the left.

Walkthrough

1. Initialization:
   Create a grid dp of size m x n. Initialize the first row and first column to 1.
2. Fill the DP table:
   For each cell (i, j) starting from (1, 1), compute dp[i][j] using the recurrence.
3. Final answer:
   The value at dp[m-1][n-1] is the number of unique paths from the start to the finish.

Every cell is computed once and read at most twice, so the table never revisits work. That is the payoff of the DP formulation, and it is the same machinery that drives harder grid questions such as Edit Distance, where each cell combines three neighbors instead of two.

Approach B: combinatorial mathematics

Idea

• To reach the bottom-right corner, the robot must make exactly (m-1) downs and (n-1) rights in any order.
• The total number of moves required is (m-1 + n-1) = (m+n-2).
• Counting paths therefore means counting the distinct arrangements of those moves, which the binomial coefficient gives directly:

  Number of unique paths = C(m+n-2, m-1) = (m+n-2)! / [(m-1)! * (n-1)!]

Walkthrough

1. Total moves:
   Calculate the total number of moves (m+n-2).
2. Choose moves:
   Choose which moves are downs, or equivalently which are rights. The answer is the number of ways to choose (m-1) moves from (m+n-2).
3. Final answer:
   Compute the binomial coefficient to get the answer.

Approach B is faster and shorter, but it only works because movement is unrestricted. Add a single blocked cell, as Unique Paths II does, and the formula collapses while the DP table survives with a one-line change. Learn both, and lead with the DP in an interview unless the interviewer asks for the closed form.

Code implementation

Python implementation (dynamic programming)