Maximum Path Sum in the matrix
You have been given an N*M matrix filled with integer numbers, find the maximum sum that can be obtained from a path starting from any cell in the first row to any cell in the last row.

From a cell in a row, you can move to another cell directly below that row, or diagonally below left or right. So from a particular cell (row, col), we can move in three directions i.e.

Down: (row+1,col) Down left diagonal: (row+1,col-1) Down right diagonal: (row+1, col+1)

Input format :

The first line contains an integer 'T', which denotes the number of test cases or queries to be run. Then the test cases follow. The first line of each test case contains two Integers 'N' and 'M' where 'N' denotes the number of rows in the given matrix. And 'M' denotes the number of columns in the given matrix. The next 'N' line of each test case contains 'M' space-separated integers denoting the cell elements.

Output format :

For each test case/query, print the maximum sum that can be obtained by taking a path as described above. Output for every test case will be printed in a separate line.

Note :

You do not need to print anything. It has already been taken care of.

Constraints :

1

Question

Maximum Path Sum in the matrix

You have been given an N*M matrix filled with integer numbers, find the maximum sum that can be obtained from a path starting from any cell in the first row to any cell in the last row.

From a cell in a row, you can move to another cell directly below that row, or diagonally below left or right. So from a particular cell (row, col), we can move in three directions i.e.

Down: (row+1,col)
Down left diagonal: (row+1,col-1)
Down right diagonal: (row+1, col+1)

Input format :

The first line contains an integer 'T', which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains two Integers 'N' and 'M' where 'N' denotes the number of rows in the given matrix. And 'M' denotes the number of columns in the given matrix.

The next 'N' line of each test case contains 'M' space-separated integers denoting the cell elements.

Output format :

For each test case/query, print the maximum sum that can be obtained by taking a path as described above.

Output for every test case will be printed in a separate line.

Note :

You do not need to print anything. It has already been taken care of.

Constraints :

1 <= T <= 50
1 <= N <= 100
1 <= M <= 100
-10^4 <= matrix[i][j] <= 10^4

Where 'T' is the number of test cases.
Where 'N' is the number of rows in the given matrix, and 'M' is the number of columns in the given matrix.
And, matrix[i][j] denotes the value at (i,j) cell in the matrix.

Time Limit: 1sec

Accepted Answer

Brute Force

The basic approach is that we are going to explore all possible paths recursively from the first row for each cell and return the maximum sum among all paths. Steps are as follows:

Start exploring the path from each cell of the first row.
And the path can end at any cell of the last row.
If any move gets out of the boundary of the given matrix, then we return negative infinity, i.e. INT_MIN, because we do not want to consider that move in our path.
Now we can move to follow three cells from the cell (row, col)
- Down move : (row+1, col)
- Down left diagonal : (row+1, col-1)
- Down right diagonal : (row+1, col+1)
Now among the above three paths, which path has the maximum sum that will be the maximum path sum from (row, col) to any cell of the last node. So return the sum of the current cell and maximum path what we got from above three paths.
So above steps can be recursively defined as:

getMaxPathSum(row,col)=matrix[row][col]+max(getMaxPathSum(row+1,col),*max(getMaxPathSum(row+1,col+1),getMaxPathSum(row+1,col-1))

Space Complexity: O(1)Explanation:

O(N), Where ‘N’ is the number of rows in the given matrix.

We are using recursion to explore the path so for each step, we are pushing the function into the stack, and there can be total ‘N’ steps Because for each step we are going one step down. So overall space complexity is O(N).

Time Complexity: O(1)Explanation:

O(M*3^(N*M)), Where ‘N’ is the number of rows and ‘M’ is the number of columns in the given matrix.

We are exploring all possible paths for all cells from the first row. So there are ‘M’ cells in the first row, and each cell is going to explore all possible paths. So for each cell in the matrix, we have three choices to move, so there are N*M cells, and each cell has three moves, i.e. down, down left diagonal and downright diagonal. So for N*M cell, we will have 3^(N*M) moves. So overall complexity will be O(M*3^(N*M)).

Accepted Answer

Using Memoization

If we draw the recursion tree for the recursive solution of Approach-1, we can observe that there is a lot of overlapping subproblems, there is only N*M distinct recursive call. Since the problem has overlapping subproblems so we can solve it more efficiently using memoization.

Let’s say we have “dp” such that:

Dp[row][col], will store the maximum sum which will path from (row, col) to any cell of the last row including (row, col) cells.

Before calling the function for any valid (row, col), we will first check whether we have already a solution corresponding to the (row, col), if we have already a solution then we return the solution else we will solve it with following steps :

We can move to follow three cells from a cell (row, col)
1. Down move : (row+1,col)
2. Down left diagonal : (row+1 , col-1)
3. Down right diagonal : (row+1, col+1)
Now among the above three paths, which path has the maximum sum that will be the maximum path sum from (row, col). So return the sum of the current cell and maximum path what we got from above three paths.
So the above steps can be recursively defined as:

getMaxPathSum(row,col)=matrix[row][col]+max(getMaxPathSum(row+1,col),max(getMaxPathSum(row+1,col+1), getMaxPathSum(row+1, col-1) )

4. And finally, before returning the answer, we will save it in “dp” for later use.

Space Complexity: O(1)Explanation:

O(N*M), Where ‘N’ is the number of rows and ‘M’ is the number of columns in the given matrix.

We will be memorizing the result for N*M cells using O(N*M) space.

Time Complexity: O(1)Explanation:

O(N*M), Where ‘N’ is the number of rows and ‘M’ is the number of columns in the given matrix.

There will be only N*M distinct recursion calls in recursion because we are saving the result so there will be no duplicate calls. So overall time complexity will be O(N*M).

Accepted Answer

Using Dynamic Programming

We are given an N*M matrix. Our idea behind this approach is while traversing in the given matrix, and we will keep updating the matrix with the best sum path till now. That means, we are going to the next row after completing the current row, So for each cell, all the cells from where we can reach here already contain the best path sum from any cell of the first row to that cell. Let’s say we are at (row, col), So there is only three way to reach (row, call):

From up:(row-1, col)
From up left diagonal:(row-1,col-1)
From upright diagonal:(row-1,col+1)

So, matrix[row][col] will be,

matrix[row][col] = matrix[row][col] + max(matrix[row - 1][col], max(matrix[row - 1][max(0, col - 1)], matrix[row - 1][min(m-1, col + 1)]));

Where ‘M’ is the number of columns in the given matrix.

Once we have updated the “matrix” then each cell of the matrix (row, col) will represent the maximum path sum for any cell from the first row to current (row, col) cell. So we will traverse in the last row and find the maximum value that will be the maximum path sum from any cell of the first row to any cell of the last row.

Space Complexity: O(1)Explanation:

O(1)

Since we are not using any extra space, we are just modifying the given matrix. So space complexity will be O(1).

Time Complexity: O(1)Explanation:

O(N*M), Where ‘N’ is the number of rows and ‘M’ is the number of columns in the given matrix.

There will be a total N*M cell in the given matrix, and we are traversing each cell. So time complexity will be O(N*M).

You have been given an N*M matrix filled with integer numbers, find the maximum sum that can be obtained from a path starting from any cell in the first row to any cell in the last row.

From a cell in a row, you can move to another cell directly below that row, or diagonally below left or right. So from a particular cell (row, col), we can move in three directions i.e.

Input format :

Output format :

Note :

Constraints :

Top Quess Software Engineer interview questions & answers

Popular interview questions of Software Engineer