Find total number of unique paths in a grid

Companies:
  • Amazon Interview Questions
  • Apple Interview Questions
  • Bloomberg Interview Questions
  • Facebook Interview Questions
  • Goldman Sachs Interview Questions
  • Google Interview Questions
  • Microsoft Interview Questions
  • Oracle Interview Questions
  • Walmart Labs Interview Questions

Problem Statement

A robot is located at the top-left corner of a m x n grid .

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.

How many possible unique paths are there?

Constraints:

  • 1 <= m, n <= 100
  • It’s guaranteed that the answer will be less than or equal to 2 * 10 ^ 9.

Sample Test Cases

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 -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Problem Solution

We can approach this problem using Dynamic Programming. So, every DP problem has some sub-problem whose solutions leads to our final answer.

Let’s first find the sub-problem.

In this problem our aim is to reach (m,n) we can reach this cell via two paths ie (m-1 , n) and (m, n-1). So, if we have the total no of unique ways to reach (m-1 , n) and (m, n-1) we can easily find the no of unique paths for(m, n) by using the relation-

F(m, n) = F(m-1, n) + F(m, n-1)

Subsequently we can extend this relation for F(m, n-1 ) and F(m, n-1) and so on.

But we need to keep in mind that whenever m=0 or n=0 we have to return 1 because when we are in the first row we have only one single unique movement and same is the case when we are in the first column.

Complexity Analysis

Time Complexity : Since we are traversing the entire dp matrix our time complexity will be O(mn).

Space Complexity : Since we are maintaining the entire dp matrix our space complexity will be O(mn).

Code Implementation

#include<bits/stdc++.h>
using namespace std;
int dp[1000][1000];


int uniquePaths(int m,int n)
{   dp[m][n];

    for(int i=0;i<m;i++)
    {
         for(int j=0;j<n;j++)
        {
            if(i==0||j==0)
            {
                dp[i][j]=1;
            }
            else
            {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }

    }

    return dp[m-1][n-1];
}
int main()
{
    int m=3;
    int n=2;

    int x= uniquePaths(m,n);
    cout<<x;
}

 

Scroll to Top