Pular para o conteúdo principal

Unique Paths

This question is asked by Google. A ball is dropped into a special Galton board where at each level in the board the ball can only move right or down. Given that the Galton board has M rows and N columns, return the total number of unique ways the ball can arrive at the bottom right cell of the Galton board.

Example(s)​

Example 1:

Input: M = 2, N = 2
Output: 2
Explanation:
The possible paths are:
  - DOWN -> RIGHT
  - RIGHT -> DOWN
Total: 2 unique paths

Example 2:

Input: M = 4, N = 3
Output: 10
Explanation:
There are 10 unique paths from top-left to bottom-right.

Example 3:

Input: M = 3, N = 7
Output: 28
Explanation:
There are 28 unique paths from top-left to bottom-right.

Example 4:

Input: M = 1, N = 1
Output: 1
Explanation:
Only one cell, so only one path (already at destination).

Solution​

The solution uses Dynamic Programming:

  1. DP state: dp[i][j] = number of ways to reach cell (i, j)
  2. Base case: dp[0][0] = 1 (starting position)
  3. Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1] (can come from top or left)
  4. Result: dp[M-1][N-1] where M and N are number of rows and columns

JavaScript Solution - Dynamic Programming

/**
* Find number of unique paths from top-left to bottom-right
* @param {number} M - Number of rows
* @param {number} N - Number of columns
* @return {number} - Number of unique paths
*/
function uniquePaths(M, N) {
// dp[i][j] = number of ways to reach cell (i, j)
const dp = Array(M).fill().map(() => Array(N).fill(0));

// Base case: starting position
dp[0][0] = 1;

// Fill first row: can only come from left
for (let j = 1; j < N; j++) {
  dp[0][j] = 1;
}

// Fill first column: can only come from top
for (let i = 1; i < M; i++) {
  dp[i][0] = 1;
}

// Fill rest of the table
for (let i = 1; i < M; i++) {
  for (let j = 1; j < N; j++) {
    // Can come from top (i-1, j) or left (i, j-1)
    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  }
}

return dp[M - 1][N - 1];
}

// Test cases
console.log('Example 1:', uniquePaths(2, 2)); 
// 2

console.log('Example 2:', uniquePaths(4, 3)); 
// 10

console.log('Example 3:', uniquePaths(3, 7)); 
// 28

console.log('Example 4:', uniquePaths(1, 1)); 
// 1
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (Space-Optimized)​

Here's a space-optimized version using only O(N) space:

/**
 * Space-optimized: O(N) space instead of O(M × N)
 */
function uniquePathsOptimized(M, N) {
  // dp[j] = number of ways to reach current row, column j
  const dp = Array(N).fill(1);
  
  // For each row (starting from row 1)
  for (let i = 1; i < M; i++) {
    for (let j = 1; j < N; j++) {
      // dp[j] = dp[j] (from top) + dp[j-1] (from left)
      dp[j] = dp[j] + dp[j - 1];
    }
  }
  
  return dp[N - 1];
}

Alternative Solution (Combinatorics)​

Here's a mathematical solution using combinatorics:

/**
 * Mathematical solution: C(M+N-2, M-1) or C(M+N-2, N-1)
 * Number of ways = (M+N-2)! / ((M-1)! × (N-1)!)
 */
function uniquePathsCombinatorics(M, N) {
  // Total moves needed: (M-1) downs + (N-1) rights = M+N-2 moves
  // Choose (M-1) positions for downs (or (N-1) for rights)
  
  const totalMoves = M + N - 2;
  const downs = M - 1;
  
  // Calculate C(totalMoves, downs)
  let result = 1;
  for (let i = 1; i <= downs; i++) {
    result = result * (totalMoves - downs + i) / i;
  }
  
  return Math.round(result);
}

Complexity​

  • Time Complexity: O(M × N) - Where M and N are the number of rows and columns. We fill a DP table of size M × N.
  • Space Complexity:
    • Standard DP: O(M × N) - For the DP table
    • Optimized: O(N) - Using only one row
    • Combinatorics: O(1) - Constant space

Approach​

The solution uses Dynamic Programming:

  1. DP state:

    • dp[i][j] = number of ways to reach cell (i, j) from top-left
    • We build up from the starting position

  2. Base cases:

    • dp[0][0] = 1 - Starting position, one way to be there
    • dp[0][j] = 1 - First row, can only come from left
    • dp[i][0] = 1 - First column, can only come from top

  3. Recurrence:

    • To reach cell (i, j), can come from:
      • Top: cell (i-1, j) - move down
      • Left: cell (i, j-1) - move right
    • dp[i][j] = dp[i-1][j] + dp[i][j-1]

  4. Result:

    • dp[M-1][N-1] = number of ways to reach bottom-right

Key Insights​

  • Dynamic Programming: Optimal substructure - paths to (i, j) use paths to (i-1, j) and (i, j-1)
  • Two directions: Can only move right or down
  • Combinatorics: This is C(M+N-2, M-1) - choose positions for downs
  • O(M×N) time: Must fill entire DP table
  • Space optimization: Can reduce to O(N) space

Step-by-Step Example​

Let's trace through Example 1: M = 2, N = 2

Grid: 2×2
  (0,0) → (0,1)
    ↓       ↓
  (1,0) → (1,1)

DP table (dp[i][j]):
        j:  0  1
  i=0:      1  1
  i=1:      1  2

Fill table:
  Base cases:
    dp[0][0] = 1 (starting position)
    dp[0][1] = 1 (first row, can only come from left)
    dp[1][0] = 1 (first column, can only come from top)
  
  dp[1][1]:
    Can come from top: dp[0][1] = 1
    Can come from left: dp[1][0] = 1
    dp[1][1] = 1 + 1 = 2

Result: dp[1][1] = 2

Paths:
  1. (0,0) → (0,1) → (1,1)  (RIGHT → DOWN)
  2. (0,0) → (1,0) → (1,1)  (DOWN → RIGHT)

Visual Representation​

Example 1: M = 2, N = 2

Grid:
  (0,0) ──→ (0,1)
    │        │
    ↓        ↓
  (1,0) ──→ (1,1)

DP table:
        j:  0  1
  i=0:      1  1
  i=1:      1  2

Paths:
  Path 1: RIGHT → DOWN
    (0,0) → (0,1) → (1,1)
  
  Path 2: DOWN → RIGHT
    (0,0) → (1,0) → (1,1)

Result: 2 unique paths

Example 2: M = 4, N = 3

DP table (simplified):
        j:  0  1  2
  i=0:      1  1  1
  i=1:      1  2  3
  i=2:      1  3  6
  i=3:      1  4 10

Result: dp[3][2] = 10

Mathematical Insight​

This problem can be solved using combinatorics:

  • To reach bottom-right from top-left:

    • Need (M-1) down moves
    • Need (N-1) right moves
    • Total moves: (M+N-2)

  • Number of unique paths = C(M+N-2, M-1) = C(M+N-2, N-1)

    • Choose (M-1) positions for downs out of (M+N-2) total moves
    • Or choose (N-1) positions for rights

Example: M = 4, N = 3

  • Total moves: 4+3-2 = 5
  • Downs needed: 4-1 = 3
  • Rights needed: 3-1 = 2
  • Number of ways: C(5, 3) = C(5, 2) = 10

Edge Cases​

  • M = 1, N = 1: Return 1 (already at destination)
  • M = 1, N = k: Return 1 (can only move right)
  • M = k, N = 1: Return 1 (can only move down)
  • M = 2, N = 2: Return 2 (two paths)
  • Large values: Use DP or combinatorics with care for overflow

Important Notes​

  • Two directions: Can only move right or down
  • No obstacles: All cells are accessible
  • Combinatorics: Can use mathematical formula
  • O(M×N) time: Must fill DP table
  • Space optimization: Can reduce to O(N) space

Why Dynamic Programming Works​

Optimal Substructure:

  • To reach cell (i, j), we must first reach either (i-1, j) or (i, j-1)
  • The number of ways to reach (i, j) is the sum of ways to reach these two cells
  • This creates the recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1]

Overlapping Subproblems:

  • Multiple paths may pass through the same intermediate cells
  • DP stores and reuses these values
  • Unique Paths II: With obstacles in the grid
  • Minimum Path Sum: Similar DP structure with costs
  • Minimum Path Sum: Find minimum cost path
  • Triangle: Different DP problem

Takeaways​

  • Dynamic Programming solves this efficiently
  • Two directions per cell: right or down
  • Combinatorics provides mathematical solution
  • O(M×N) time to fill DP table
  • Space can be optimized to O(N)
  • Classic DP problem with many variations