PROGRAMMING INTERVIEWS

Question: There is an m x n grid. One can only move either down or right at any point in time. One is trying to reach the bottom-right corner of the grid.

How many possible unique paths are there?
Below is an example of 4x4 grid. Here from moving top-left to bottom right corner, we will have 20 unique paths.

1 1 1 1
1 2 3 4
1 3 6 10
1 4 10 20

Answer: Since we know that one can only move either down or right at any point in time so one can reach to cell (i,j) only from 2 possible locations:

• One step right from cell (i-1,j)
• One step down from cell (i,j-1)

So unique no of paths to reach any cell (i,j) will be equal to sum of unique no of paths to reach any cell (i-1,j) and unique no of paths to reach any cell (i,j-1). We can convert the same formula into code using 2 approaches:

• Recursion / Backtracking
• Dynamic programming.

In backtracking we will calculate the no of paths for same locations again and again but in Dynamic programming (DP) approach, we can use memoization and will get rid of calculating same locations again and again. For DP soluton just initialize a 2D array(sat paths) of size m x n with all elements as 1. And then apply the formula:

Paths[i][j] = paths[i][j-1] + paths[i-1][j]

After calculating the entire 2D array, just return paths[m][n].

Code:
In code width is representing m and height is representing n.

 int no_of_paths(int width, int height)
 {
    //Creating paths 
    int** paths = new int*[height];
    for(int i = 0; i < height; ++i)
        paths[i] = new int[width];
    
    int i,j;
    
    //Initializing paths
    for (i=0 ;i< width; i++)
    {
        for (j=0; j< height; j++)
            paths[i][j] = 1;
    }

    //Calculating paths   
    for (i=1 ;i< width; i++)
    {
        for (j=1; j< height; j++)
        {
            paths[i][j] = paths[i-1][j] + paths[i][j-1];
        }
    }
    //just for printing/debugging purpose   
    for (i=0 ;i< width; i++)
    {
        for (j=0; j< height; j++)
        {
            cout << paths[i][j] << " ";
        }
        cout << endl;
    }
        
    int res = paths[width-1][height-1];

    //Deleting paths   
    for(int i = 0; i < height; ++i) {
        delete [] paths[i];
    }
    delete [] paths;
    
    return res;
 }

On a second thought, I see that in place of using a 2D matrix(paths) for memoization, we can just have 1-D array with length as width. Please see the code for the same as below.

int no_of_paths(int width, int height)
{ 
 int i,j;
 int* no = new int[width];
 
 for (i=0 ;i< width; i++)
 {
  no[i] = 1;
  cout << "1 "; //just for printing/debugging purpose
 }
 cout << endl;     //just for printing/debugging purpose
 
 for (i=1 ;i< height; i++)
 {
  cout << no[0] << " ";     //just for printing/debugging purpose
  for (j=1; j< width; j++)
  {
   no[j] = no[j]+no[j-1];
   cout << no[j] << " "; //just for printing/debugging purpose
  }
  cout << endl;             //just for printing/debugging purpose
 }
 int res = no[width-1];
 
 delete [] no; 
 return res;
}

Complexity: Since we are traversing each element just once, this solution has linear time complexity.
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.