Problem Statement #

A robot is located at the top-left corner of an m × n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

Question: How many possible unique paths are there?

Solution #

var uniquePaths = function(m, n) {
    // The robot can't go backwards, so movement is always forward (right or down)
    
    let matrix = [];
    
    // Create the edges of the matrix
    // Bottom edge: only one way to reach finish (go right)
    for (let i = 0; i < n; i++) { // for every row
        if (!matrix[i]) {
            matrix[i] = [];
        }
        matrix[i][m - 1] = 1;
    }
    
    // Right edge: only one way to reach finish (go down)
    for (let i = 0; i < m; i++) { // for every column
        matrix[n - 1][i] = 1;
    }
    
    // Build up the matrix from bottom-right to top-left
    // Each cell equals the sum of the cell below it and the cell to its right
    for (let i = n - 2; i >= 0; i--) { // offset by 2 since edges already made
        for (let j = m - 2; j >= 0; j--) {
            // Sum up paths from right and bottom
            matrix[i][j] = matrix[i + 1][j] + matrix[i][j + 1];
        }
    }
    
    // The top-left corner contains the total number of unique paths
    return matrix[0][0];
};

Approach and Intuition #

Understanding the Problem Through Examples #

When approaching this problem, it’s essential to visualize the grid and work through small examples to build intuition. The provided samples give us insight into patterns that emerge as we scale up the grid size.

Matrix Representation #

We represent the grid as a two-dimensional array (matrix). For consistency and clarity:

• Rows are represented by n (first dimension)
• Columns are represented by m (second dimension)
• Array notation: matrix[row][column] or matrix[i][j]

Building Intuition with Examples #

Let’s examine progressively larger grids to understand the pattern.

2×2 Grid: The simplest non-trivial case yields 2 unique paths:

1. Down → Right
2. Right → Down

Scaling Up to 3×3 and 4×4:

To see the pattern clearly, let’s visualize a 4×4 grid with the number of unique paths to reach the finish from each cell:

For a 3×3 grid, examine the bottom-right 3×3 portion of this table.

Key Insight: The Edge Cases #

Notice the pattern along the bottom row and rightmost column—they all contain the value 1. Why?

• Bottom edge: From any cell in the bottom row, there’s only ONE path to the destination: move right until you reach the finish.
• Right edge: From any cell in the rightmost column, there’s only ONE path to the destination: move down until you reach the finish.

These edges form the base case for our dynamic programming solution.

The Recurrence Relation #

For any cell that’s not on the bottom or right edge, the number of unique paths follows a simple rule:

paths[i][j] = paths[i+1][j] + paths[i][j+1]

Why does this work?

From any given cell, the robot has exactly two choices:

1. Move right: The number of unique paths from that point forward equals the value in the cell to the right
2. Move down: The number of unique paths from that point forward equals the value in the cell below

Therefore, the total number of unique paths through any cell is the sum of the paths through the cell below and the cell to the right.

This is the essence of dynamic programming: we solve smaller subproblems (paths from cells closer to the finish) and use those solutions to build up to the answer for larger subproblems.

Code Breakdown #

Let’s examine each section of the solution in detail.

Step 1: Initialize the Edge Cases #

// Create edges
for (let i = 0; i < n; i++) { // for every row
    if (!matrix[i]) {
        matrix[i] = [];
    }
    matrix[i][m - 1] = 1;
}

for (let i = 0; i < m; i++) { // for every column
    matrix[n - 1][i] = 1;
}

This section initializes the bottom and right edges with 1s, as discussed above.

Important detail: In JavaScript, we cannot access the second dimension of a 2D array without first initializing the first dimension. The check if (!matrix[i]) ensures we create an empty array for each row before attempting to set values in that row.

Step 2: Build the Matrix Using Dynamic Programming #

// Build from bottom-left corner moving toward top-left
for (let i = n - 2; i >= 0; i--) { // offset by 2 since edges already made
    for (let j = m - 2; j >= 0; j--) {
        // Each cell is the sum of paths from right and bottom
        matrix[i][j] = matrix[i + 1][j] + matrix[i][j + 1];
    }
}

We iterate from bottom-right toward top-left, filling in each cell using our recurrence relation.

Why start at n-2 and m-2?

• Arrays are zero-indexed, so the last element is at index n-1 (or m-1)
• We’ve already initialized the edges at n-1 and m-1
• Therefore, we start at n-2 and m-2 to avoid redundant work and prevent out-of-bounds array access

The inner calculation matrix[i+1][j] + matrix[i][j+1] references cells that have already been computed (cells below and to the right), which is guaranteed because we’re iterating backward through the matrix.

Step 3: Return the Result #

return matrix[0][0];

After completing the matrix, the top-left corner (matrix[0][0]) contains the total number of unique paths from start to finish. This is our answer.

Complexity Analysis #

Time Complexity: O(m × n)

• We iterate through every cell in the grid exactly once
• Each cell operation (addition) is O(1)

Space Complexity: O(m × n)

• We create a 2D matrix to store the path counts
• This could be optimized to O(min(m, n)) by only keeping track of one row or column at a time

Alternative Approaches #

While this dynamic programming solution is intuitive and efficient, there are other approaches worth mentioning:

1. Mathematical approach: This problem is actually a combination problem: C(m+n-2, m-1) or C(m+n-2, n-1)
2. 1D dynamic programming: Optimize space by using only a single array
3. Recursive with memoization: Top-down dynamic programming approach

Conclusion #

The Unique Paths problem is an excellent introduction to dynamic programming concepts. By recognizing the overlapping subproblems and building solutions from the base cases upward, we can efficiently solve what might initially seem like a complex combinatorial problem.

The key takeaways are:

• Identify base cases (edges with value 1)
• Establish the recurrence relation (sum of paths from adjacent cells)
• Build the solution bottom-up from known values
• Extract the final answer from the starting position

This pattern of thinking applies to countless other dynamic programming problems, making it a valuable skill for any programmer to develop.