Solution: Unique Paths

Statement#

Imagine a scenario where an adventurous little robot, named Robi, has a mission to traverse a grid with m rows and n columns and reach a treasure box placed at $grid[m-1][n-1]$. Robi starts the journey from its home in the top-left corner of the grid, $grid[0][0]$. However, it faces a constraint that at any given time, it can only move in either of the two directions: downward or to the right.

Given the two integers, m and n, return the total number of unique paths that Robi can take from the grid's top-left corner to reach the bottom-right corner of the grid.

Constraints:

• 1 $\leq$ m, n $\leq$ 100

Solution#

So far, you’ve probably brainstormed some approaches on how to solve this problem. Let’s explore some of these approaches and figure out which one to follow while considering time complexity and any implementation constraints.

Naive approach#

The naive approach uses recursion to consider every possible path that the robot can take from the top-left corner of the grid to the bottom-right corner. The algorithm begins with the top-left corner and explores two branches: moving right and moving down. This process continues recursively, generating further branches for each valid move. Eventually, the recursion reaches the base cases:

• If the robot reaches the bottom-right corner, a single path is counted.

• If it goes out of bounds or reaches an edge, such a path is not counted.

The algorithm sums up the number of paths obtained through these recursive explorations and returns this number as the total number of unique paths.

Since this approach recalculates the overlapping subproblems, it becomes inefficient as the grid size grows, resulting in exponential time complexity. The robot takes a total of $m + n - 2$ steps to go from the top-left corner to the bottom-right corner, which results in $2^{m + n - 2}$ number of nodes in the recursion tree. Overall, the time complexity for this naive approach is $O(2^{m + n})$. The maximum depth of the recursion stack corresponds to the height of the recursion tree, which is $m + n - 2$, so the overall space complexity for this approach is $O(m + n)$.

Optimized approach using dynamic programming #

Let’s look at the bottom-up dynamic programming approach to solve this problem. In this approach, solutions to smaller subproblems are stored in a table as they are computed, and these solutions are then used to solve larger subproblems until the main problem is solved.

For this specific problem, we start with solving the simplest cases along the first row and first column. These are straightforward because there's only one way to reach them. We save these solutions and then use them to find solutions for other cells by adding up the values from the cell above and the cell to the left. This process continues until we calculate the total unique paths to the bottom-right cell. The value in the bottom-right cell will represent the total number of unique paths. This approach avoids unnecessary calculations and is more efficient.

We start by creating a 2D array, grid, to store the results of smaller subproblems and then combine these results to get the final answer. We initialize grid with all $1$s because this will automatically cover the base case of having $1$s in the cells of the first row and column. To iteratively fill the values of each subsequent cell, we then traverse each cell of the grid and use the following recurrence relation:

            grid[row][col] = grid[row-1][col] + grid[row][col-1]

This is because the robot can only move either down or right. Therefore, the total number of ways to reach the current cell is the sum of the ways to reach the cell above it and the ways to reach the cell to its left. This process continues until all cells in the grid have been updated with the correct values. Finally, the function returns the value in the bottom-right cell of the grid, which represents the total number of unique paths to reach the bottom-right corner of the grid.

Now, let’s look at the following illustration to get a better understanding of the solution:

Let’s look at the code for this solution below:

Solution summary#

To recap, the solution to this problem can be divided into the following parts:

• A grid is created with all cells initialized to $1$ to cater the base case.

• Traverse the grid and update the value in the current cell by adding the value from the cell above and the value from the cell to the left. Keep doing this until we reach the bottom-right cell of the grid.

• Return the value present in the bottom-right cell of the grid.

Time complexity#

The time complexity of this solution is $O(m \times n)$ because a 2D array of size $m \times n$ is filled iteratively.

Space complexity#

The space complexity of this solution is proportional to the size of the grid, that is, $O(m \times n)$.

Alternative solutions#

Now, let’s see some other ways to solve this problem.

The space-optimized solution#

If you have noticed from the optimized approach given above, in order to calculate the value of any particular cell, except for the cells in the first row and the first column, we only need the values from its previous row and column. This implies that we can get to our answer without storing the whole grid. Instead, we can use a rolling array and modify it until we get to our final answer.

We iterate over the entire rolling array and update its values for m number of times. For this, we'll use a nested loop. The outer loop will make us iterate the rolling array for m times and the inner loop will allow us to update the value of each element of the rolling array based on the values in the previous iteration. In each inner loop, the value of the first element of the rolling array won't be changed since it comes under the base case. To calculate the values for the rest of the elements, we use the sum of the current element and the previous element in the rolling array. These values represent values from the cell directly above the current cell and the cell to its left, respectively. The following illustration will help to get a better understanding of this solution:

Let's look at the code for this solution:

While the time complexity remains the same as the optimized approach above, i.e., $O(m \times n)$, this approach reduces the space complexity from $O(m \times n)$ to $O(n)$.

Mathematical solution#

Another way to this problem is by using a mathematical approach—specifically, combinations and permutations. If we have a $m \times n$ grid, then we'll need to move down $m - 1$ times and move right $n - 1$ times to reach the bottom-right corner. We can arrange movements in a sequence. The total number of unique paths is then equal to the number of ways you can arrange these movements, which can be calculated using combinations.

The binomial coefficient, denoted as $C(h, k)$ or read as "$h$ choose $k$," represents the number of combinations of selecting $k$ items from a set of $h$ items. The formula to precisely calculate combinations is as follows:

$C(h, k) = \frac{h! }{ k!\:(h - k)!}$

In the context of this problem, $h$ is the total number of moves required to travel from the top-left corner to the bottom-right corner of an $m \times n$ grid, i.e., $(m - 1 + n - 1)$, and $k$ represents the number of steps to the right, i.e., $(n-1)$. Now, the formula becomes:

$C(h, k) = \frac{(m+n-2)! }{ (n-1)!\:(m-1)!}$

Let's have a look at the code:

The loop in the function iterates from 1 to n - 1 (inclusive), which means it takes $O(n)$ time. Inside the loop, there are constant-time operations (multiplication and division), so the dominant factor in the time complexity is the loop itself. Therefore, the overall time complexity of this solution is $O(n)$. However, the space complexity of this solution is $O(1)$.