Matrix Paths Editorial

Practice Problem Link: Matrix Paths | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given a 2D matrix, and you have to go from top-left to bottom-right. You can only move a cell right or a cell down in each step. Find out how many paths are there to go from the starting cell to the ending cell.

Naive Approach

We can solve this problem naively by using a recursive brute force approach. Note that we have only two choices to move to when we are in a certain cell. We can recursively brute force over all the possibilities, and count the number of ways required to reach the target cell.

Analysis

• Time Complexity: O(2ⁿ)
• Space Complexity: O(2ⁿ)

Implementation

C++

int solvePaths(int currRow, int currCol) {
   int countWays = 0;
   if(currRow == 1 || currCol == 1) {
       return 1;
   }
   countWays += solvePaths(currRow - 1, currCol);
   countWays += solvePaths(currRow, currCol - 1);
   return countWays;
}
int getNumPaths(int rows, int columns) {
   int count = solvePaths(rows, columns);
   return count;
}

Java

class Solution {
   int solvePaths(int currRow, int currCol) {
       int countWays = 0;
       if(currRow == 1 || currCol == 1) {
           return 1;
       }
       countWays += solvePaths(currRow - 1, currCol);
       countWays += solvePaths(currRow, currCol - 1);
       return countWays;
   }
   int getNumPaths(int rows, int columns) {
       return solvePaths(rows, columns);
   }
}

Optimal Approach

Let’s approach the problem in a mathematical way using combinatorics. In such problems, the easiest way to approach is to find an invariant.

So, what is the thing which remains constant in this problem?

We can observe that the total number of moves required, the number of rightward moves, and the number of downward moves required remain constant in this problem.

We will always require to move (row - 1) moves down and (column - 1) moves right to reach our destination cell.

So we have a total of (row + column - 2) moves, out of which we have to choose (row - 1) downward moves.

So, the answer is ^{(row + column - 2)}C_{(row - 1)}.

Analysis

• Time Complexity: O(row + column)
• Space Complexity: O(1)

Implementation

C++

int getNumPaths(int rows, int columns) {
   double result = 1;
   int n = rows + columns - 2;
   int r = rows - 1;
   for(int i = 1; i <= r; i++) {
       result *= (n--);
       result /= i;
   }
   return llround(result);
}

Java

class Solution {
   int getNumPaths(int rows, int columns) {
       double result = 1;
       int n = rows + columns - 2;
       int r = rows - 1;
       for(int i = 1; i <= r; i++) {
           result *= (n--);
           result /= i;
       }
       return (int) Math.round(result);
   }
}