Category: Medium
Problem
A robot is located at the top-left corner of a m x 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).
How many possible unique paths are there?
Examples
First Example:
1 2 | Input: m = 3, n = 7 Output: 28 |
Second Example:
1 2 3 4 5 6 7 | Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Down -> Down 2. Down -> Down -> Right 3. Down -> Right -> Down |
Third Example:
1 2 | Input: m = 7, n = 3 Output: 28 |
Fourth Example:
1 2 | Input: m = 3, n = 3 Output: 6 |
Constraints
1 <=1 <= m, n <= 100It's guaranteed that the answer will be less than or equal to2 * 109.
Solution Approach
In this problem of Unique paths, we have to find the paths from the top left corner to the bottom right corner. We are only concerned with the number of unique paths and not the actual paths themselves. The number of unique paths should be returned as the answer.
We can solve this problem in different ways and with different complexities. It’s necessary to know all the ways. This question can be altered where one solution will outperform the rest in complexity.
We will be using the following approaches to solve the problem
- Dynamic Programming
- Dynamic Programming with Optimised space
- Mathematical formula
Let’s look at the solutions one by one:-
Dynamic Programming
The idea of the dynamic programming approach is simple. If it’s a one dimension array there is only one way to reach the required destination – straight down or straight right. We have to decompose our 2D array to a 1D array to simplify and use dynamic programming. For that, we will create one dummy array to store the value of the number of ways to reach a cell from starting cell. The starting rows and columns will have values set to one (1) as there is only one way to reach them. For the rest of the cells, we will calculate the no of the ways will be equal to the sum of no ways to reach the cell in the previous cell horizontally and vertically. In the end, the M*Nth cell’s value will be unique paths.
The time complexity of this approach is O(m*n) as we are iterating the whole 2D array once. The space complexity is also O(m*n) as we need an array of the same dimension to store the number of paths.
Dynamic Programming with Optimised space
Here we are using the same dynamic programming method but instead of creating a 2D array, we can save the space by creating a 1D array of only columns. We still have to loop through rows and columns like in the above approach but we will just add the previous element of the array and current element and store it in the current element. This will enable us to not use the extra space. The value of the last element will be the number of unique paths.
The time complexity is the same as the last approach i.e O(m*n). The space complexity is reduced to O(n).
Mathematical Formula
We can use the mathematical formula of combination to get the number of unique paths. From the starting position we have to move m-1 steps down and n-1 steps to the right. Hence the total number of steps is m+n-2 from (m-1 + n -1). To formulate this problem for a combination we can ask how many ways we can get by performing m – 1 down steps out of total m + n – 2 moves. The answer of which comes out to be C(n,k) = n! / (n – k)! k!. The same formula can be used for finding the number of unique paths.
The time complexity of this approach is O(n). This is in order to find the factorial we need to loop through 1 to n once. We won’t be needing extra space hence the space complexity is O(1).
Solution code
Dynamic Programming
We create a 2D array of size m*n. Then we initialize the first row and first columns with 1. After that, we loop through the length and update the cells in the array with the sum of the previous row and previous columns value. In the end, we return the last cell’s value as the number of unique paths.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | class Solution { public int uniquePaths(int m, int n) { int[][] dynamicArray = new int[m][n]; for (int row = 0; row < m; row++) dynamicArray[row][0] = 1; for (int column = 0; column < n; column++) dynamicArray[0][column] = 1; for (int row = 1; row < m; row++) { for (int column = 1; column < n; column++) { dynamicArray[row][column] = dynamicArray[row - 1][column] + dynamicArray[row][column - 1]; } } return dynamicArray[m - 1][n - 1]; } } |
Dynamic Programming with Optimised space
In this approach, we will declare an array of size n. We then initialize all elements of the array to 1. Secondly, we loop through the array and update each element with the sum of the previous element and that element itself. In the end, we return the last element as the number of unique paths.
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public int uniquePaths(int m, int n) { int[] dynamicArray = new int[n]; dynamicArray[0] = 1; for (int row = 0; row < m; row++) { for (int column = 1; column < n; column++) { dynamicArray[column] += dynamicArray[column- 1]; } } return dynamicArray[n - 1]; } } |
Mathematical Formula
We need to set up few things before the implementation which are basically numerator and denominator in combinations formula. The numerator will be m-1 + n-1 = m+n-2. The denominator will be a minimum of m and n, -1. Another variable to store the result is required which can be initialized with 1. Then we loop through the denominator and keep finding the intermediate combination result. In the end, we return the same result as the answer.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution { public int uniquePaths(int m, int n) { int numerator = m + n - 2; int denominator = Math.min(m, n) - 1; long result = 1; for (int i = 0; i < denominator; i++) { result = result * (numerator - i) / (i + 1); } return (int) result; } } |
For more Leetcode explained solutions visit Leetcode Solutions.
If you like capture the flag challenges visit here.
Check out my socials below in the footer. Feel free to ask any doubts in the comment section. You can also contact me via the Contact page I will surely respond. Happy Leetcoding 🙂