Count paths on a board

You're sitting in a Microsoft interview when the interviewer pulls out a whiteboard and draws a simple 2×2 grid. "Imagine you're designing a robot that needs to navigate from the top-left corner to the bottom-right corner of a warehouse floor grid," they begin. "The robot can only move right or down due to the conveyor belt system. How many unique paths can it take?" This classic problem appears at companies like Amazon, Twitter, and Microsoft because it tests your ability to recognize overlapping subproblems and apply dynamic programming effectively.

TL;DR

Count unique paths in an m-by-n grid using dynamic programming: set all first-row and first-column cells to 1, then fill each remaining cell with the sum of the cell above and the cell to the left. The answer sits in the bottom-right cell. This runs in O(mn) time and O(mn) space, reducible to O(min(m,n)) with a rolling 1D array. A closed-form combinatorial solution C(m+n-2, m-1) also exists but does not extend to grids with obstacles.

Why This Problem Matters

The grid path counting problem is a gateway to understanding dynamic programming. It's deceptively simple yet reveals whether you can identify when recursion becomes inefficient and how to optimize it with memoization. Master this pattern, and you'll be ready for more complex DP problems like edit distance, longest common subsequence, and the knapsack problem.

Understanding the Problem

Let's break down what we're being asked to do:

Given: Dimensions m (rows) and n (columns) of a grid Task: Count all unique paths from top-left (0,0) to bottom-right (m-1, n-1) Constraints: Can only move right or down Return: The total number of unique paths

Here's a simple 2×2 grid to visualize the problem:

In this 2×2 grid, there are exactly 2 paths:

1. Start → Right → Down (A → B → D)
2. Start → Down → Right (A → C → D)

Edge Cases to Consider

1. Single cell (1×1): Only 1 path (you're already there!)
2. Single row (1×n): Only 1 path (keep moving right)
3. Single column (m×1): Only 1 path (keep moving down)
4. Large grids: Can have millions of paths (e.g., 18×17 has over 1 billion paths)

Solution Intuition

The Naive Recursive Approach

Your first instinct might be to use recursion. At each cell, you have two choices (if available): go right or go down. This gives us:

if (m == 1 || n == 1) return 1;
return countPaths(m - 1, n) + countPaths(m, n - 1);

But here's the problem: this creates an exponential time complexity of O(2^{m+n}). For an 18×17 grid, you'd be computing billions of redundant calculations!

The Key Insight: Overlapping Subproblems

The magic happens when you realize that multiple recursive branches calculate the same subproblems. For example, reaching cell (1,1) can happen via:

• Start → Right → Down
• Start → Down → Right

Both paths need to know "how many ways to reach the destination from (1,1)?" Why calculate this twice?

Dynamic Programming to the Rescue

Instead of recalculating, we'll build up our solution from the ground up. The brilliance lies in this observation:

The number of paths to any cell = paths from above + paths from left

Why? Because those are the only two ways to reach any cell (you can only move right or down).

Watch how the DP table builds up for a 3×3 grid:

Each cell shows the cumulative number of paths to reach it from the start. The pattern is elegant:

• First row: all 1s (only one way - keep going right)
• First column: all 1s (only one way - keep going down)
• Interior cells: sum of the cell above and the cell to the left

Implementation

Prefer a different language? Jump to solutions in Python, JavaScript, C++, Go, and Scala.

Here's our dynamic programming solution with detailed explanations:

public long countPaths(int m, int n) {
    // Create a DP table to store path counts for each cell
    int[][] memo = new int[m][n];

    // Initialize first column: only one way to go down
    for (int r = 0; r < m; r++) {
        memo[r][0] = 1;
    }

    // Initialize first row: only one way to go right
    for (int c = 0; c < n; c++) {
        memo[0][c] = 1;
    }

    // Fill the DP table using the recurrence relation
    for (int r = 1; r < m; r++) {
        for (int c = 1; c < n; c++) {
            // Paths to current cell = paths from above + paths from left
            memo[r][c] = memo[r - 1][c] + memo[r][c - 1];
        }
    }

    // The bottom-right cell contains our answer
    return memo[m - 1][n - 1];
}

The beauty of this solution is its simplicity. We're essentially filling out a multiplication table, but instead of multiplying, we're adding the values from above and to the left.

Complexity Analysis

Time Complexity: O(m \times n)

We visit each cell exactly once and perform constant-time operations (addition and array access) at each cell. This gives us linear time in the size of the grid.

Space Complexity: O(m \times n)

We use a 2D array to store the path counts for each cell. However, this can be optimized to O(\min(m, n)) by using a single-row rolling array, since we only need the previous row to compute the current row.

Mathematical Insight

There's actually a closed-form solution using combinatorics! The problem is equivalent to choosing (m-1) down moves from a total of (m+n-2) moves:

For a 3×3 grid: C(4, 2) = \frac{4!}{2! \times 2!} = 6

Here's the final state of our 3×3 grid showing all path counts:

Common Pitfalls and Interview Tips

Pitfalls to Avoid

1. Integer Overflow: For large grids, the path count exceeds int range. Use long in Java or appropriate types in other languages.

2. Off-by-One Errors: Remember that an m×n grid has indices from (0,0) to (m-1, n-1).

3. Forgetting Base Cases: Don't forget to handle single row/column cases if using recursion.

4. Not Recognizing the Pattern: Some candidates try complex DFS/BFS when simple DP suffices.

Interview Tips

1. Start with Examples: Draw a small 2×2 or 3×3 grid and manually count paths to build intuition.

2. Mention Both Approaches: Show you know recursive and DP solutions, explain why DP is better.

3. Discuss Optimizations: Mention the space optimization using a 1D array and the combinatorial formula.

4. Think Aloud: Explain why paths[i][j] = paths[i-1][j] + paths[i][j-1]. This shows you understand the recurrence relation.

5. Test Your Solution: Walk through your code with a simple 2×2 example to catch errors.

Key Takeaways

• The DP recurrence paths[i][j] = paths[i-1][j] + paths[i][j-1] captures the fact that each cell can only be reached from above or from the left.
• Initialize all first-row and first-column cells to 1 because there is exactly one way to reach any cell along the edges (straight right or straight down).
• Space can be optimized from O(m*n) to O(min(m,n)) using a rolling 1D array, since each row depends only on the current and previous row.
• The combinatorial formula C(m+n-2, m-1) provides an O(m+n) closed-form solution for grids without obstacles.
• This problem is the gateway to 2D dynamic programming; the same table-filling pattern appears in edit distance, longest common subsequence, and minimum path sum.

Practice Makes Perfect

Understanding this problem opens doors to countless DP variations. Try these related problems on Firecode:

• Edit Distance (similar 2D DP table)
• Longest Common Subsequence (another grid-based DP)
• Minimum Path Sum (same grid traversal with costs)

The grid path problem might seem simple, but it's a fundamental building block of dynamic programming. Once you internalize the pattern of building solutions from smaller subproblems, you'll find yourself recognizing it everywhere. Ready to practice more DP problems? Fire up Firecode and solidify these concepts with hands-on coding!

Solutions in Other Languages

The dynamic programming approach works identically across all languages. Below are clean implementations in Python, JavaScript, C++, Go, and Scala.

Python

class Solution:
    def count_paths(self, m: int, n: int) -> int:
        # Create a DP table initialized with zeros
        memo = [[0 for _ in range(n)] for _ in range(m)]

        # Fill first column with 1s (only one way down)
        for r in range(0, m):
            memo[r][0] = 1

        # Fill first row with 1s (only one way right)
        for c in range(0, n):
            memo[0][c] = 1

        # Fill the rest using DP recurrence
        for r in range(1, m):
            for c in range(1, n):
                memo[r][c] = memo[r - 1][c] + memo[r][c - 1]

        # Return the bottom-right cell value
        return memo[m - 1][n - 1]

JavaScript

class Solution {
  countPaths(m, n) {
    // Create a 2D array for DP
    const memo = [...Array(m)].map(_ => Array(n));

    // Initialize first column
    for (let r = 0; r < m; r++) {
      memo[r][0] = 1;
    }

    // Initialize first row
    for (let c = 0; c < n; c++) {
      memo[0][c] = 1;
    }

    // Fill using DP relation
    for (let r = 1; r < m; r++) {
      for (let c = 1; c < n; c++) {
        memo[r][c] = memo[r - 1][c] + memo[r][c - 1];
      }
    }

    return memo[m - 1][n - 1];
  }
}

C++

#include <vector>

class Solution {
public:
  long countPaths(int m, int n) {
    // Create 2D vector for memoization
    std::vector<std::vector<long>> memo(m, std::vector<long>(n, 0));

    // Initialize first column
    for (int r = 0; r < m; r++) {
      memo[r][0] = 1;
    }

    // Initialize first row
    for (int c = 0; c < n; c++) {
      memo[0][c] = 1;
    }

    // Build DP table
    for (int r = 1; r < m; r++) {
      for (int c = 1; c < n; c++) {
        memo[r][c] = memo[r - 1][c] + memo[r][c - 1];
      }
    }

    return memo[m - 1][n - 1];
  }
};

Go

package solution

func (s *Solution) CountPaths(m int, n int) int64 {
    // Create 2D slice for memoization
    memo := make([][]int64, m)
    for i := range memo {
        memo[i] = make([]int64, n)
    }

    // Initialize first column
    for r := 0; r < m; r++ {
        memo[r][0] = 1
    }

    // Initialize first row
    for c := 0; c < n; c++ {
        memo[0][c] = 1
    }

    // Fill DP table
    for r := 1; r < m; r++ {
        for c := 1; c < n; c++ {
            memo[r][c] = memo[r-1][c] + memo[r][c-1]
        }
    }

    return memo[m-1][n-1]
}

Scala

class Solution {
  def countPaths(m: Int, n: Int): Long = {
    // Create 2D array for DP
    val memo = Array.ofDim[Int](m, n)

    // Initialize first column
    for (r <- 0 until m) {
      memo(r)(0) = 1
    }

    // Initialize first row
    for (c <- 0 until n) {
      memo(0)(c) = 1
    }

    // Build the DP table
    for (r <- 1 until m) {
      for (c <- 1 until n) {
        memo(r)(c) = memo(r - 1)(c) + memo(r)(c - 1)
      }
    }

    memo(m - 1)(n - 1)
  }
}