InterviewBit - Grid Unique Path  

by ne on 2021-09-29 under Algo/DS/Problems

This problem is a property of InterviewBit (www.interviewbit.com).

Full details of the question, and if you want to try it out yourself, proceed to interviewbit : https://www.interviewbit.com/problems/grid-unique-paths/

In the following solution, I am using simple dynamic programming technique.

At every position, there can be only 2 incoming paths, top and left. So, at current position X, we can come from either x-1,y OR x,y-1.

And, if we start analyzing from x,y, and keep back tracking using above approach till we reach x==1 OR y==1, because once we are in that extreme path x=1 or y=1, there's only one way to back track till 0, we will find the total number of ways.

Here's the implementation:

 


public class Solution {
    public int uniquePaths(int x, int y) {
        if(y==1 || x==1) return 1;
        return uniquePaths(x-1,y) + uniquePaths(x,y-1);
    }    
}




Happy Coding !