Today, we have another programming challenge taken from the Unique Paths problem at Leetcode.
Table of Contents
The Unique Paths Challenge
This challenge requires us to write a function called uniquePaths() that accepts two arguments – m and n. Our job is to find the number of paths from the top-left corner, to the bottom-right corner, of a m x n grid.
At any point in time, we are only allowed to move down or right.
For instance, suppose we have the following 2 x 3 grid.
Our job is to find the number of paths from cell A to cell B. For a small grid like the one above, we can easily mark out the paths. As shown in the diagram above, for a 2 x 3 grid, the number of unique paths is 3 (indicated by the orange, blue and grey lines).
Our job is to write a function that returns the number of unique paths to get from A (top-left corner) to B (bottom-right corner) for any m x n grid.
Approach 1: Using a m x n List to Find Unique Paths
The Approach
The first approach to solving the unique paths problem is to use a 2-D list to represent the m x n grid.
To understand how this works, let’s suppose m = 3 and n = 4. This gives us the 3 x 4 grid below (ignore the letters and colors in the grid for now):
We can represent this grid using the list below:
[[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]]
This list consists of three elements, with each element ([1, 1, 1, 1]) representing one row in the grid.
Each element in the nested lists represents a cell in the grid. The value of that element will eventually represent the number of ways to reach that cell in the corresponding grid.
At the beginning, we’ll initialize all the values to 1.
These values will remain for the first row and first column. This is because for each cell in the first row and column of a grid, there is only one way to reach that cell. For instance, to reach the blue cell in the grid above, the only path is to move two steps to the right from point A. Similarly, to reach the red cell, the only path is to move one step down.
Our job now is to determine the number of ways to reach all the other cells in the grids.
Determining Numbers of Ways to Reach Other Cells
Given that we are only allowed to move to the right, or move down, this means that to reach any cell in the grid, we have to pass through the cell above it or the cell on the left of it. For instance, to reach the yellow cell (cell R), we can either move one step down from cell P, or one step to the right from cell Q.
Since there is only one path to reach cell P and cell Q each, we can conclude there are a total of two paths to reach cell R (either A -> P -> R or A -> Q -> R).
In general, we can conclude that the number of ways to reach any cell is given by the sum of the number of ways to reach the cell above it, and the number of ways to reach the cell on the left of it.
Using this formula above, we can update the values of all the cells in the grid to reflect the number of ways to reach that cell. Once we reach the last cell (cell B), our task is complete. We simply need to return the value of cell B.
Based on this description above, try solving the unique paths problem yourself.
Graphical Illustration
Suggested Solution
The suggested solution for approach 1 is as follows:
def uniquePaths(m, n):
# Initialize m x n list with 1
myList = [[1 for x in range(n)] for x in range(m)]
for i in range(1, m):
for j in range(1, n):
# Number of ways for current cell =
# Number of ways for cell on the left +
# Number of ways for cell above
myList[i][j] = myList[i-1][j] + myList[i][j-1]
# Return result for last cell
return myList[-1][-1]Here, we first declare a list called myList and initialize all elements in the list to 1. This is done using list comprehension.
Creating the List
Suppose m = 3 and n = 4.
[1 for x in range(n)] creates a list with n elements, each with a value of 1.
When n equals 4, this creates the list [1, 1, 1, 1].
[[1 for x in range(n)] for x in range(m)]
becomes
[[1, 1, 1, 1] for x in range(3)]
This creates the list
[[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]]
As mentioned in the “The Approach” section above, each element in this list represent a cell in a 3 x 4 grid.
Updating Values in The List to Represent Number of Ways
After creating this list, we use a for loop (lines 7 to 14) to loop through the list, starting from the second element in the second nested list. This represents the cell in the second row, second column of the grid.
For each cell in the grid that we loop through, we update the value of that cell (myList[i][j]) by assigning the sum of the value of the cell above it (myList[i-1][j]) and the value of the cell on the left of it (myList[i][j-1]).
After we finish iterating all the cells in the grid, the value in the last cell (the bottom right cell) gives us the answer that we need.
Therefore, we return the value of myList[-1][-1] on line 17.
With that, the function is complete.
Approach 2: Using Mathematics to Find Unique Paths
The Approach
Now that we know how to solve the unique paths problem using a list, let’s move on to the second approach where we use mathematics to solve the problem.
To do this, we need to understand that for any m x n grid, to get from the top-left corner to the bottom-right corner, regardless of which path we take, we need to make m – 1 moves down and n – 1 moves to the right.
For instance, for the 2 x 3 grid shown above, regardless of whether we take the orange, grey or blue path, we need to make 2 – 1 = 1 move down and 3 – 1 = 2 moves to the right.
The orange path can be represented as RRD, the grey path as RDR, and the blue path as DRR, where R represents a move to the right and D represents a move down.
Applying The Concept of Combination
Once we recognize that each path consists of m – 1 moves down and n – 1 moves to the right, the question can be simplified to a combination question.
For any m x n grid, a total of (m – 1) + (n – 1) moves are required for each path.
For instance, for a 2 x 3 grid, each path requires (2 – 1) + (3 – 1) = 3 moves.
Out of these three moves, 2 of them are moves to the right and 1 of them is a move down.
To determine the number of unique paths from A to B, we simply need to consider how many unique ways can we select 2 moves to the right, out of a total of 3 moves. In this example, there are 3 unique ways. The moves to the right can either be the first 2 moves – RRD, the first and last move – RDR, or the last two moves – DRR.
Mathematically, we can say that the number of unique paths is given by 3C2, also known as 3 choose 2. That is, out of a total of 3 moves, how many ways can we choose 2 right moves.
Alternatively, we can consider the number of ways to select 1 move down, out of a total of 3 moves.
Mathematically, we say that the number of unique paths is given by 3C1. That is, out of a total of 3 moves, how many ways can we choose 1 down move.
If you are familiar with combination, you’ll know that 3C1 and 3C2 give the same answer. In general, nCr and nCn-r always give the same answer.
In addition, nCr can be calculated using the formula below:
For instance, 7C3 can be evaluated as
Based on this description above, try writing a function that calculates the number of unique paths using the combination approach.
Suggested Solution
The code below shows how we can solve the unique paths problem using combination:
def uniquePaths(m, n):
total = m + n -2
choose = min(m, n) - 1
product = 1
for i in range(choose):
product = product * total / (i+1)
total -= 1
return int(product)Here, we first define a function called uniquePaths() with two parameters – m and n.
Determining the Values of total and choose
Inside the function, we declare two variables called total and choose.
total stores the total number of moves we need to make while choose stores the number of moves we need to choose.
Let’s use an example to illustrate what these variables do.
Suppose we have a 4 x 5 grid.
To get from the top-left to the bottom-right corner, we need to make a total of 3 moves down (m-1) and 4 moves to the right (n-1).
Therefore,
total = m + n - 2 = 4 + 5 - 2 = 7
Out of these 7 moves, we need to choose which 4 moves are to the right and which 3 moves are down. For instance, we need to choose whether it is RRRRDDD, RRDDRRD, RDRDRDR or some other combination.
This can be achieved by evaluating either 7C3 or 7C4, both of which give us the same answer.
If we decide to evaluate 7C4, we’ll assign 4 to the choose variable. On the other hand, if we decide to evaluate 7C3, we’ll assign 3. Given that it is faster to evaluate 7C3, we’ll assign 3 to choose. This is achieved on line 3 in our code, where
choose = min(m, n) - 1 = m - 1 (as m is smaller than n in this example) = 4 - 1 = 3
Calculating Number of Ways Using the Combination Formula
After determining the values of total and choose, we declare a variable called product on line 5 and initialize it to 1.
We then proceed to calculate the value of totalCchoose.
We do that using a for loop from lines 7 to 9, based on the formula given in the “The Approach” section above.
Suppose we want to calculate the value of 7C3 .
The first time the loop runs,
product = 1 * 7 / (1) = 7
The second time the loop runs,
product = product * 6 / (2) = 1 * 7 * 6 / (1*2) = 21
The third time the loop runs,
product = product * 5 / (3) = 1 * 7 * 6 * 5 / (1*2*3) = 35
Since range(choose) equals range(3), the for loop will only run 3 times.
After the loop finishes, product stores the value of 7C3. Therefore, we return its value on line 11.
Notice that we cast product to an integer before returning it?
This is necessary in Python 3 as Python 3 returns a float for any division. If we do not do that, we’ll get 35.0 as the output, instead of 35.
Casting product to an integer will not lead to any loss of accuracy in our answer as product will always be an integer.
This is because for every n consecutive numbers, at least one of them must be divisible by n, one of them divisible by n – 1 and so on.
For instance, let’s consider the third step in our example above.
For this step, the numerator consists of 1, 7, 6 and 5. Other than the number 1 (which does not affect the product), the remaining numbers are all consecutive. Out of these 3 consecutive numbers, at least one of them must be divisible by 3 (the number 6 in this example), one by 2 (the number 6) and one by 1 (all three numbers).
Thus, we will never get a non-integer when we divide the numerator by the denominator. This Mathematical property ensures that product will always be an integer.
That’s it. That’s all for today’s programming challenge.