In this article, we will solve the most asked coding interview problem: Grid Unique Paths
Given two values M and N, which represent a matrix[M][N]. We need to find the total unique paths from the top-left cell (matrix[0][0]) to the rightmost cell (matrix[M-1][N-1]).
At any cell we are allowed to move in only two directions:- bottom and right.
Examples
Example:
Practice:
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Memorization Approach
Algorithm / Intuition
As we have to count all possible ways to go from matrix[0,0] to matrix[m-1,n-1], we can try recursion to generate all possible paths.
Steps to form the recursive solution:
We will first form the recursive solution by the three points mentioned in Dynamic Programming Introduction.
Step 1: Express the problem in terms of indexes.
We are given two variables M and N, representing the dimensions of a 2D matrix. For every different problem, this M and N will change.
We can define the function with two parameters i and j, where i and j represent the row and column of the matrix.
f(i,j) will give us a sub-answer for the region (marked in blue) below:
We will be doing a top-down recursion, i.e we will move from the cell[M-1][N-1] and try to find our way to the cell[0][0]. Therefore at every index, we will try to move up and towards the left.
Base Case:
As discussed in Patterns in Recursion, there will be two base cases:
- When i=0 and j=0, that is we have reached the destination so we can count the current path that is going on, hence we return 1.
- When i<0 and j<0, it means that we have crossed the boundary of the matrix and we couldn’t find a right path, hence we return 0.
The pseudocode till this step will be:
Step 2: Try out all possible choices at a given index.
As we are writing a top-down recursion, at every index we have two choices, one to go up(↑) and the other to go left(←). To go upwards, we will reduce i by 1, and move towards left we will reduce j by 1.
Step 3: Take the maximum of all choices
As we have to count all the possible unique paths, we will return the sum of the choices(up and left)
The final pseudocode after steps 1, 2, and 3:
Steps to memoize a recursive solution:
If we draw the recursion tree, we will see that there are overlapping subproblems. In order to convert a recursive solution the following steps will be taken:
- Create a dp array of size [m][n]
- Whenever we want to find the answer of a particular row and column (say f(i,j)), we first check whether the answer is already calculated using the dp array(i.e dp[i][j]!= -1 ). If yes, simply return the value from the dp array.
- If not, then we are finding the answer for the given values for the first time, we will use the recursive relation as usual but before returning from the function, we will set dp[i][j] to the solution we get.
Code
#include <bits/stdc++.h>
using namespace std;
// Recursive function to count the number of ways to reach (i, j) from (0, 0)
// in a grid of size m x n
int countWaysUtil(int i, int j, vector<vector<int>>& dp) {
// Base case: If we reach the top-left corner (0, 0), there is one way.
if (i == 0 && j == 0)
return 1;
// If we go out of bounds or reach a blocked cell, there are no ways.
if (i < 0 || j < 0)
return 0;
// If we have already computed the number of ways for this cell, return it.
if (dp[i][j] != -1)
return dp[i][j];
// Calculate the number of ways by moving up and left recursively.
int up = countWaysUtil(i - 1, j, dp);
int left = countWaysUtil(i, j - 1, dp);
// Store the result in the dp table and return it.
return dp[i][j] = up + left;
}
// Function to count the number of ways to reach the bottom-right cell (m-1, n-1)
// from the top-left cell (0, 0) in a grid of size m x n
int countWays(int m, int n) {
// Create a memoization table (dp) to store the results of subproblems.
vector<vector<int>> dp(m, vector<int>(n, -1));
// Call the utility function with the bottom-right cell as the starting point.
return countWaysUtil(m - 1, n - 1, dp);
}
int main() {
int m = 3;
int n = 2;
// Call the countWays function and print the result.
cout << "Number of ways to reach (" << m - 1 << ", " << n - 1 << "): " << countWays(m, n) << endl;
return 0;
}
import java.util.*;
class TUF {
// Function to count the number of ways to reach cell (i, j)
static int countWaysUtil(int i, int j, int[][] dp) {
// If we reach the starting cell (0, 0), there's one way to reach it.
if (i == 0 && j == 0)
return 1;
// If we go out of bounds, there's no way to reach the cell.
if (i < 0 || j < 0)
return 0;
// If the value for this cell is already computed, return it.
if (dp[i][j] != -1)
return dp[i][j];
// Calculate the number of ways by moving up and moving left.
int up = countWaysUtil(i - 1, j, dp);
int left = countWaysUtil(i, j - 1, dp);
// Store the result in the DP array and return it.
return dp[i][j] = up + left;
}
// Function to count the number of ways to reach cell (m-1, n-1)
static int countWays(int m, int n) {
// Create a 2D DP array to store the results
int dp[][] = new int[m][n];
// Initialize the DP array with -1 to indicate uncomputed values
for (int[] row : dp)
Arrays.fill(row, -1);
// Start the recursive calculation from the bottom-right cell (m-1, n-1)
return countWaysUtil(m - 1, n - 1, dp);
}
public static void main(String args[]) {
int m = 3;
int n = 2;
// Call the countWays function and print the result
System.out.println(countWays(m, n));
}
}
def countWaysUtil(i, j, dp):
# Base case: If we reach the top-left corner (i=0, j=0), there is one way to reach there.
if i == 0 and j == 0:
return 1
# If either i or j goes out of bounds (negative), there is no way to reach that cell.
if i < 0 or j < 0:
return 0
# If we have already calculated the number of ways for this cell, return it from the dp array.
if dp[i][j] != -1:
return dp[i][j]
# Recursive calls to count the number of ways to reach the current cell.
up = countWaysUtil(i - 1, j, dp) # Moving up one row.
left = countWaysUtil(i, j - 1, dp) # Moving left one column.
# Store the result in the dp array and return it.
dp[i][j] = up + left
return dp[i][j]
def countWays(m, n):
# Initialize a memoization (dp) array to store intermediate results.
dp = [[-1 for j in range(n)] for i in range(m)]
# Call the utility function to compute the number of ways to reach the bottom-right cell (m-1, n-1).
return countWaysUtil(m - 1, n - 1, dp)
def main():
m = 3
n = 2
# Call the countWays function to calculate and print the number of ways to reach the destination.
print(countWays(m, n))
if __name__ == '__main__':
main()
// Define a function to count the number of ways to reach cell (i, j) from the top-left corner (0, 0) in a grid of size m x n.
function countWaysUtil(i, j, dp) {
// If we have reached the top-left corner, there is one way to reach it.
if (i === 0 && j === 0) {
return 1;
}
// If i or j is negative, we are out of bounds, so there are no ways to reach this cell.
if (i < 0 || j < 0) {
return 0;
}
// If we have already computed the number of ways to reach this cell, return it.
if (dp[i][j] !== -1) {
return dp[i][j];
}
// Calculate the number of ways to reach this cell by moving up and left.
const up = countWaysUtil(i - 1, j, dp);
const left = countWaysUtil(i, j - 1, dp);
// Store the result in the dp array and return it.
dp[i][j] = up + left;
return dp[i][j];
}
// Define a function to count the number of ways to reach the bottom-right corner (m-1, n-1) of a grid of size m x n.
function countWays(m, n) {
// Create a 2D array to store the results of subproblems. Initialize it with -1.
const dp = Array.from(Array(m), () => Array(n).fill(-1));
// Call the utility function to compute the result.
return countWaysUtil(m - 1, n - 1, dp);
}
// Main function
function main() {
const m = 3;
const n = 2;
// Call the countWays function and print the result.
console.log(countWays(m, n));
}
// Call the main function to start the program.
main();
Output: 3
Complexity Analysis
Time Complexity: O(M*N)
Reason: At max, there will be M*N calls of recursion.
Space Complexity: O((N-1)+(M-1)) + O(M*N)
Reason: We are using a recursion stack space: O((N-1)+(M-1)), here (N-1)+(M-1) is the path length and an external DP Array of size ‘M*N’.
Tabulation Approach
Algorithm / Intuition
Tabulation is the bottom-up approach, which means we will go from the base case to the main problem.
The steps to convert to the tabular solution are given below:
- Declare a dp[] array of size [m][n].
- First initialize the base condition values, i.e dp[0][0] = 1
- Our answer should get stored in dp[m-1][n-1]. We want to move from (0,0) to (m-1,n-1). But we can’t move arbitrarily, we should move such that at a particular i and j, we have all the values required to compute dp[i][j].
- If we see the memoized code, the values required for dp[i][j] are dp[i-1][j] and dp[i][j-1]. So we only use the previous row and column value.
- We have already filled the top-left corner (i=0 and j=0), if we move in any of the two following ways(given below), at every cell we do have all the previous values required to compute its value.
- We can use two nested loops to have this traversal
- At every cell we calculate up and left as we had done in the recursive solution and then assign the cell’s value as (up+left)
Note: For the first row and first column (except for the top-left cell), then up and left values will be zero respectively.
Code
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of ways to reach the bottom-right cell (m-1, n-1)
// from the top-left cell (0, 0) in a grid of size m x n
int countWaysUtil(int m, int n, vector<vector<int>>& dp) {
// Loop through the grid using two nested loops
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// Base condition: If we are at the top-left cell (0, 0), there is one way.
if (i == 0 && j == 0) {
dp[i][j] = 1;
continue; // Skip the rest of the loop and continue with the next iteration.
}
// Initialize variables to store the number of ways from the cell above (up) and left (left).
int up = 0;
int left = 0;
// If we are not at the first row (i > 0), update 'up' with the value from the cell above.
if (i > 0)
up = dp[i - 1][j];
// If we are not at the first column (j > 0), update 'left' with the value from the cell to the left.
if (j > 0)
left = dp[i][j - 1];
// Calculate the number of ways to reach the current cell by adding 'up' and 'left'.
dp[i][j] = up + left;
}
}
// The result is stored in the bottom-right cell (m-1, n-1).
return dp[m - 1][n - 1];
}
// Function to count the number of ways to reach the bottom-right cell (m-1, n-1)
// from the top-left cell (0, 0) in a grid of size m x n
int countWays(int m, int n) {
// Create a memoization table (dp) to store the results of subproblems.
vector<vector<int>> dp(m, vector<int>(n, -1));
// Call the utility function with the grid size and the memoization table.
return countWaysUtil(m, n, dp);
}
int main() {
int m = 3;
int n = 2;
// Call the countWays function and print the result.
cout << "Number of ways to reach (" << m - 1 << ", " << n - 1 << "): " << countWays(m, n) << endl;
return 0;
}
import java.util.*;
class TUF {
// Function to count the number of ways to reach cell (m, n)
static int countWaysUtil(int m, int n, int[][] dp) {
// Loop through each cell in the grid
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// Base condition: If we are at the top-left cell (0, 0), there's one way to reach it.
if (i == 0 && j == 0) {
dp[i][j] = 1;
continue;
}
int up = 0;
int left = 0;
// Calculate the number of ways by moving up (if possible) and left (if possible)
if (i > 0)
up = dp[i - 1][j];
if (j > 0)
left = dp[i][j - 1];
// Store the total number of ways to reach the current cell in the DP array
dp[i][j] = up + left;
}
}
// Return the number of ways to reach the bottom-right cell (m-1, n-1)
return dp[m - 1][n - 1];
}
// Function to count the number of ways to reach cell (m, n)
static int countWays(int m, int n) {
// Create a 2D DP array to store the results
int dp[][] = new int[m][n];
// Initialize the DP array with -1 to indicate uncomputed values
for (int[] row : dp)
Arrays.fill(row, -1);
// Call the countWaysUtil function to calculate and return the result
return countWaysUtil(m, n, dp);
}
public static void main(String args[]) {
int m = 3;
int n = 2;
// Call the countWays function and print the result
System.out.println(countWays(m, n));
}
}
def countWaysUtil(m, n, dp):
# Loop through each cell in the grid
for i in range(m):
for j in range(n):
# Base condition: If we are at the top-left corner, there is one way to reach it.
if i == 0 and j == 0:
dp[i][j] = 1
continue
# Initialize variables to store the number of ways from above and from the left.
up = 0
left = 0
# Check if moving up is a valid option (not out of bounds).
if i > 0:
up = dp[i - 1][j]
# Check if moving left is a valid option (not out of bounds).
if j > 0:
left = dp[i][j - 1]
# Calculate and store the number of ways to reach the current cell.
dp[i][j] = up + left
# The bottom-right cell (m-1, n-1) now contains the total number of ways to reach there.
return dp[m - 1][n - 1]
def countWays(m, n):
# Initialize a memoization (dp) array to store intermediate results.
dp = [[-1 for j in range(n)] for i in range(m)]
# Call the utility function to compute the number of ways to reach the destination.
return countWaysUtil(m, n, dp)
def main():
m = 3
n = 2
# Call the countWays function to calculate and print the number of ways to reach the destination.
print(countWays(m, n))
if __name__ == '__main__':
main()
// Define a function to count the number of ways to reach cell (m, n) in a grid.
function countWaysUtil(m, n, dp) {
// Iterate through each cell in the grid.
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
// Base condition: If we are at the top-left cell (0, 0), there is only one way to reach it.
if (i === 0 && j === 0) {
dp[i][j] = 1;
continue;
}
// Initialize variables to store the number of ways to reach the current cell by moving up and left.
let up = 0;
let left = 0;
// Check if we can move up (i > 0).
if (i > 0) {
up = dp[i - 1][j];
}
// Check if we can move left (j > 0).
if (j > 0) {
left = dp[i][j - 1];
}
// The total number of ways to reach the current cell is the sum of ways from above (up) and from the left (left).
dp[i][j] = up + left;
}
}
// The result is stored in the bottom-right cell of the grid (m-1, n-1).
return dp[m - 1][n - 1];
}
// Define a function to count the number of ways to reach cell (m, n) in an m x n grid.
function countWays(m, n) {
// Create a 2D array to store the results of subproblems. Initialize it with -1.
const dp = Array.from(Array(m), () => Array(n).fill(-1));
// Call the utility function to compute the result.
return countWaysUtil(m, n, dp);
}
// Main function
function main() {
const m = 3;
const n = 2;
// Call the countWays function and print the result.
console.log(countWays(m, n));
}
// Call the main function to start the program.
main();
Output: 3
Complexity Analysis
Time Complexity: O(M*N)
Reason: There are two nested loops
Space Complexity: O(M*N)
Reason: We are using an external array of size ‘M*N’’.
Space Optimization Approach
Algorithm / Intuition
Part 3: Space Optimization
If we closely look at the relationship,
dp[i][j] = dp[i-1][j] + dp[i][j-1])
We see that we only need the previous row and column, in order to calculate dp[i][j]. Therefore we can space optimize it.
Initially, we can take a dummy row ( say prev) and initialize it as 0.
Now the current row(say temp) only needs the previous row value and the current row’s value in order to calculate dp[i][j].
At the next step, the temp array becomes the prev of the next step and using its values we can still calculate the next row’s values.
At last prev[n-1] will give us the required answer.
Code
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of ways to reach the bottom-right cell (m-1, n-1)
// from the top-left cell (0, 0) in a grid of size m x n
int countWays(int m, int n) {
// Create a vector to represent the previous row of the grid.
vector<int> prev(n, 0);
// Iterate through the rows of the grid.
for (int i = 0; i < m; i++) {
// Create a temporary vector to represent the current row.
vector<int> temp(n, 0);
// Iterate through the columns of the grid.
for (int j = 0; j < n; j++) {
// Base case: If we are at the top-left cell (0, 0), there is one way.
if (i == 0 && j == 0) {
temp[j] = 1;
continue;
}
// Initialize variables to store the number of ways from the cell above (up) and left (left).
int up = 0;
int left = 0;
// If we are not at the first row (i > 0), update 'up' with the value from the previous row.
if (i > 0)
up = prev[j];
// If we are not at the first column (j > 0), update 'left' with the value from the current row.
if (j > 0)
left = temp[j - 1];
// Calculate the number of ways to reach the current cell by adding 'up' and 'left'.
temp[j] = up + left;
}
// Update the previous row with the values calculated for the current row.
prev = temp;
}
// The result is stored in the last cell of the previous row (n-1).
return prev[n - 1];
}
int main() {
int m = 3;
int n = 2;
// Call the countWays function and print the result.
cout << "Number of ways to reach (" << m - 1 << ", " << n - 1 << "): " << countWays(m, n) << endl;
return 0;
}
import java.util.*;
class TUF {
// Function to count the number of ways to reach cell (m, n)
static int countWays(int m, int n) {
// Create an array to store the results for the previous row
int prev[] = new int[n];
for (int i = 0; i < m; i++) {
// Create a temporary array to store the results for the current row
int temp[] = new int[n];
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) {
// Base condition: There's one way to reach the top-left cell (0, 0)
temp[j] = 1;
continue;
}
int up = 0;
int left = 0;
// Calculate the number of ways by moving up (if possible) and left (if possible)
if (i > 0)
up = prev[j];
if (j > 0)
left = temp[j - 1];
// Store the total number of ways to reach the current cell in the temporary array
temp[j] = up + left;
}
// Set the temporary array as the previous array for the next row
prev = temp;
}
// Return the number of ways to reach the bottom-right cell (m-1, n-1)
return prev[n - 1];
}
public static void main(String args[]) {
int m = 3;
int n = 2;
// Call the countWays function and print the result
System.out.println(countWays(m, n));
}
}
def countWays(m, n):
# Initialize a previous row to store intermediate results.
prev = [0] * n
# Loop through each row of the grid.
for i in range(m):
# Initialize a temporary row to store current row results.
temp = [0] * n
# Loop through each column of the grid.
for j in range(n):
# Base case: If we are at the top-left corner, there is one way to reach it.
if i == 0 and j == 0:
temp[j] = 1
continue
# Initialize variables to store the number of ways from above and from the left.
up = 0
left = 0
# Check if moving up is a valid option (not out of bounds).
if i > 0:
up = prev[j]
# Check if moving left is a valid option (not out of bounds).
if j > 0:
left = temp[j - 1]
# Calculate and store the number of ways to reach the current cell.
temp[j] = up + left
# Update the previous row with the current row results.
prev = temp
# The last element in the previous row (prev) now contains the total number of ways to reach the destination.
return prev[n - 1]
def main():
m = 3
n = 2
# Call the countWays function to calculate and print the number of ways to reach the destination.
print(countWays(m, n))
if __name__ == '__main__':
main()
// Define a function to count the number of ways to reach a specific cell (m, n) in a grid.
function countWays(m, n) {
// Create an array 'prev' to store the previous row's values.
const prev = Array(n).fill(0);
// Iterate through each row of the grid.
for (let i = 0; i < m; i++) {
// Create an array 'temp' to store the current row's values.
const temp = Array(n).fill(0);
// Iterate through each column of the grid.
for (let j = 0; j < n; j++) {
// Base condition: If we are at the top-left cell (0, 0), there is only one way to reach it.
if (i === 0 && j === 0) {
temp[j] = 1;
continue;
}
// Initialize variables to store the number of ways to reach the current cell by moving up and left.
let up = 0;
let left = 0;
// Check if we can move up (i > 0).
if (i > 0) {
up = prev[j];
}
// Check if we can move left (j > 0).
if (j > 0) {
left = temp[j - 1];
}
// The total number of ways to reach the current cell is the sum of ways from above (up) and from the left (left).
temp[j] = up + left;
}
// Update the 'prev' array with the values from the current row ('temp') for the next iteration.
prev.splice(0, n, ...temp);
}
// The result is stored in the last element of the 'prev' array.
return prev[n - 1];
}
// Main function
function main() {
const m = 3;
const n = 2;
// Call the countWays function and print the result.
console.log(countWays(m, n));
}
// Call the main function to start the program.
main();
Output:3
Complexity Analysis
Time Complexity: O(M*N)
Reason: There are two nested loops
Space Complexity: O(N)
Reason: We are using an external array of size ‘N’ to store only one row.
Video Explanation
Special thanks to Anshuman Sharma and Abhipsita Das for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article