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:

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

JavaScript Solution
Python Solution

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.

Python Solution - Dynamic Programming

def unique_paths(M: int, N: int) -> int:
  """
  Find number of unique paths from top-left to bottom-right
  
  Args:
      M: Number of rows
      N: Number of columns
      
  Returns:
      int: Number of unique paths
  """
  # dp[i][j] = number of ways to reach cell (i, j)
  dp = [[0] * N for _ in range(M)]
  
  # Base case: starting position
  dp[0][0] = 1
  
  # Fill first row: can only come from left
  for j in range(1, N):
      dp[0][j] = 1
  
  # Fill first column: can only come from top
  for i in range(1, M):
      dp[i][0] = 1
  
  # Fill rest of the table
  for i in range(1, M):
      for j in range(1, N):
          # 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
print('Example 1:', unique_paths(2, 2))  
# 2

print('Example 2:', unique_paths(4, 3))  
# 10

print('Example 3:', unique_paths(3, 7))  
# 28

print('Example 4:', unique_paths(1, 1))  
# 1

Loading Python runtime...

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:

JavaScript Optimized
Python Optimized

/**
 * 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];
}

def unique_paths_optimized(M: int, N: int) -> int:
    """
    Space-optimized: O(N) space instead of O(M × N)
    """
    # dp[j] = number of ways to reach current row, column j
    dp = [1] * N
    
    # For each row (starting from row 1)
    for i in range(1, M):
        for j in range(1, N):
            # 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:

JavaScript Combinatorics
Python 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);
}

import math

def unique_paths_combinatorics(M: int, N: int) -> int:
    """
    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)!)
    """
    # Total moves needed: (M-1) downs + (N-1) rights = M+N-2 moves
    # Choose (M-1) positions for downs (or (N-1) for rights)
    
    total_moves = M + N - 2
    downs = M - 1
    
    # Calculate C(total_moves, downs)
    return math.comb(total_moves, downs)

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:

DP state:
- dp[i][j] = number of ways to reach cell (i, j) from top-left
- We build up from the starting position
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
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]
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

Example(s)​

Solution​

JavaScript Solution - Dynamic Programming

Output:

Python Solution - Dynamic Programming

Output:

Alternative Solution (Space-Optimized)​

Alternative Solution (Combinatorics)​

Complexity​

Approach​

Key Insights​

Step-by-Step Example​

Visual Representation​

Mathematical Insight​

Edge Cases​

Important Notes​

Why Dynamic Programming Works​

Related Problems​

Takeaways​

Example(s)

Solution

Alternative Solution (Space-Optimized)

Alternative Solution (Combinatorics)

Complexity

Approach

Key Insights

Step-by-Step Example

Visual Representation

Mathematical Insight

Edge Cases

Important Notes

Why Dynamic Programming Works

Related Problems

Takeaways