DEV Community

Dhilip kumar

Posted on • Updated on

Find Max. Paths to last Index in a 2D Matrix in Javascript

It has been a while since my last blog.
I will be writing and explaining some algos as well as some interesting Javascript/React concepts that I come across.

PROBLEM STATEMENT:

• Given the length of Row and Column of a 2D matrix.
• Starting from origin (0,0), find the maximum number of Paths one can take to reach the last index.
• Allowed ways to move => Right and Bottom.

Example:

• Let, row's length and column length be (2, 2)
• Starting from (0,0) one should reach (1,1)
• So the number of paths for that are: 2

Path 1: (0,0) -> (0,1) -> (1,1)
Path 2: (0,0) -> (1,0) -> (1,1)

Thought Process:

Checking for a Pattern:

• We are allowed to traverse in two ways Down and Right for every Index. So this is a pattern.

Edge Cases:

• While we iterate we need to be careful about the ending index's count and so we should handle those cases.
• Path is 0 when the input is less than 1 for either row or column.(i.e.) Input cant be less than 1 for row length and column length

We found a pattern to go through for every index we can choose to solve with iteration / recursion.

Here we will solve it through RECURSION!

``````const num_of_paths = findMaxPathSrcToDes(3, 3);
console.log('Number of Paths', num_of_paths);
``````

We call `findMaxPathSrcToDes` and pass row length and column length and log it.

The intermediate Function:

``````function findMaxPathSrcToDes(rows, cols) {
// Initial rows and columns to begin with.0,0 is the first row and col index we are choosing
return findMaxPath(0, 0, rows - 1, cols - 1);
}
``````
• `findMaxPathSrcToDes` function accepts the row length and column length from the user.
• It then returns the output from `findMaxPath` function to which we pass the origin which is (0,0) and destination index(rows -1, cols - 1).
• We can modify this origin and destination index to user defined positions by accepting those, so that we can identify the number of paths any index from any index.

Finding the Paths:

`findMaxPath` function takes in 4 params and outputs the number of path.

• `currentRow` - Which indicates the current index's Row that is being processed.
• `currentColumn` - Which indicates the current index's Column that is being processed.
• `destRow` - Destination row index
• `destCol` - Destination column index

In any Recursive solution, start with writing the base conditions or Exit conditions.

So, what is a Base condition or Exit condition?

It is basically the case on satisfying which our algorithm should terminate. So, let's formulate one.

• When `currentRow > destRow` (In this case it indicates that the `currentRow` count has gone out of bound).
• When `currentColumn > destCol` (In this case it indicates that the `currentColumn` count has gone out of bound). So we return '0' in both the cases.
``````function findMaxPath(currentRow, currentColumn, destRow, destCol) {
// Base condition
if (currentRow > destRow || currentColumn > destCol) {
return 0;
}
}
``````

Success Case:

• if `currentRow === destRow` or `currentColumn === destCol` this indicates that we have reached the destination index so we return `1` to indicate a successful path.
``````if (currentRow === destRow && currentColumn === destCol) {
return 1;
}
``````

Recursion Case:

• For each index there are two ways 1.Right and 2.Down
• So, we have to recurse in both ways and add the path formed from each ways.
• We call `findMaxPath` by incrementing `currentRow` by 1.
• Then again by incrementing `currentColumn` by 1 and adding the outputs of these two and return them.
``````const pathsInRows = findMaxPath(currentRow + 1, currentColumn, destRow, destCol);
const pathsInColums = findMaxPath(currentRow, currentColumn + 1, destRow, destCol);
return (pathsInRows + pathsInColums);
``````