Maximum Coins
You are given a two-dimensional matrix of integers of dimensions N*M, where each cell represents the number of coins in that cell. Alice and Bob have to collect the maximum number of coins. The followings are the conditions to collect coins:

Alice starts from top left corner, i.e., (0, 0) and should reach left bottom corner, i.e., (N-1, 0). Bob starts from top right corner, i.e., (0, M-1) and should reach bottom right corner, i.e., (N-1, M-1).

From a point (i, j), Alice and Bob can move to (i+1, j+1) or (i+1, j-1) or (i+1, j)

They have to collect all the coins that are present at a cell. If Alice has already collected coins of a cell, then Bob gets no coins if goes through that cell again.

For example :

If the matrix is 0 2 4 1 4 8 3 7 2 3 6 2 9 7 8 3 1 5 9 4 Then answer is 47. As, Alice will collect coins 0+8+3+9+1 = 21 coins. Bob will collect coins 1+7+6+8+4 = 26 coins. Total coins is 21+26 = 47 coins.

Input Format:

The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow. The first line of input contains two single space-separated integers 'N' and 'M' representing the number of rows and columns of the matrix respectively. The next 'N' lines contain 'M' single space-separated integers each representing the coins in a row of the matrix.

Output Format:

The only line of output contains a single integer i.e. The minimum coins that can be collected by Alice and Bob.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints:

1

Question

Maximum Coins

You are given a two-dimensional matrix of integers of dimensions N*M, where each cell represents the number of coins in that cell. Alice and Bob have to collect the maximum number of coins. The followings are the conditions to collect coins:

Alice starts from top left corner, i.e., (0, 0) and should reach left bottom corner, i.e., (N-1, 0). Bob starts from top right corner, i.e., (0, M-1) and should reach bottom right corner, i.e., (N-1, M-1).

From a point (i, j), Alice and Bob can move to (i+1, j+1) or (i+1, j-1) or (i+1, j)

They have to collect all the coins that are present at a cell. If Alice has already collected coins of a cell, then Bob gets no coins if goes through that cell again.

For example :

If the matrix is 
0 2 4 1
4 8 3 7
2 3 6 2
9 7 8 3
1 5 9 4

Then answer is 47. As, Alice will collect coins 0+8+3+9+1 = 21 coins. Bob will collect coins 1+7+6+8+4 = 26 coins. Total coins is 21+26 = 47 coins.

Input Format:

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 
Then the T test cases follow.

The first line of input contains two single space-separated integers 'N' and 'M' representing the number of rows and columns of the matrix respectively.

The next 'N' lines contain 'M' single space-separated integers each representing the coins in a row of the matrix.

Output Format:

The only line of output contains a single integer i.e. The minimum coins that can be collected by Alice and Bob.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 5
1 <= N <= 10^2
1 <= M <= 10^2
0 <= MAT[i][j] <= 10^3

Time Limit: 1 sec

Accepted Answer

Given a matrix of coins, Alice and Bob have to collect maximum coins with certain conditions.

Alice starts from top left corner and Bob starts from top right corner
They can move to (i+1, j+1) or (i+1, j-1) or (i+1, j)
They have to collect all the coins that are present at a cell
If Alice has already collected coins of a cell, then Bob gets no coins if goes through that cell again

Accepted Answer

Since we want to maximum the value we can get, and we always get the middle value of three selection.
We can first sort piles and take 3 coins [Li, Mi, Hi] in following manners.

n=9
piles = [L1,L2,L3,M2,H3,M2,H3]

As this kind of greedy approach, we can maximize the number of coins we can have.

time: O(nlogn)
space: O(1)

Accepted Answer

Recursive Brute Force

Intuition:

The idea is to do both traversals concurrently. We start first from (0, 0) and second traversal from (0, m-1) simultaneously. The important thing to note is, at any particular step both traversals will be in the same row as in all possible three moves, row number is increased. Since variation in y could occur in 3 ways i.e bottom, bottom right, bottom right. So in total 9 combinations are possible among y coordinates.

Approach:

We will use recursion and define a helper function having parameters (MAT, ROW_NO, COL_NO1, COL_NO2, N, M), where ROW_NO is the row number at which Alice and Bob will present, COL_NO1 is the column number of Alice and COL_NO2 is the column number of Bob.
From the function, initially we will call helper function which will take parameters (MAT, 0, 0, M-1, N, M), as initially Alice will be at (0,0) hence ROW_NO and COL_NO1 will be 0, and Bob will be at (0, M-1) hence COL_NO2 will be M-1.
In helper function, firstly, we will check for the valid condition as no coordinates should get out of matrix dimensions.
Then we will check whether we have reached the last row of the matrix , if we have then we should check whether both coordinates are at the end then we return the coins otherwise we should return minus infinity.
Initialise the variable coins by minus infinity.
Recur for all possible ways:
1. (i, x) -> (i+1, x-1) or (i+1, x) or (i+1, x+1)
2. (i, y) -> (i+1, y-1) or (i+1, y) or (i+1, y+1)
Update the variable coins by the maximum value that is returned by recursion calls.
Final answer would be MAT[i][x] + MAT[i][y] + COINS, if x is not equal to y, otherwise the final answer would be MAT[i][x] + COINS.
Return the final answer.

Space Complexity: O(n)Explanation:

O(N), where N is the number of rows and M is the number of columns of the matrix.

As, we are using stack for recursion and recursion depth will be equal to number of rows.

Time Complexity: O(3^n)Explanation:

O(9^N), where N is the number of rows and M is the number of columns of the matrix.

As we are making 9 function calls for a particular row.

Accepted Answer

Recursive Memoization DP

Intuition:

The idea is to do both traversals concurrently. We start first from (0, 0) and second traversal from (0, m-1) simultaneously. The important thing to note is, at any particular step both traversals will be in the same row as in all possible three moves, row number is increased. Since variation in y could occur in 3 ways i.e bottom, bottom right, bottom right. So in total 9 combinations are possible among y coordinates.

Approach:

We will use recursion and memoization and define a helper function having parameters (MAT, DP, ROW_NO, COL_NO1, COL_NO2, N, M), where rowNo is the row number at which Alice and Bob will present, COL_NO1 is the column number of Alice and COL_NO2 is the column number of Bob and DP is the three-dimensional array of dimensions N*M*M initialised with -1.
From the function, initially, we will call helper function which will take parameters (MAT, DP, 0, 0, M-1, N, M), as initially Alice will be at (0,0) hence ROW_NO and COL_NO1 will be 0, and Bob will be at (0, M-1) hence COL_NO2 will be M-1.
In the helper function, firstly, we will check for the valid condition as no coordinates should get out of matrix dimensions.
Then we will check whether we have reached the last row of the matrix, if we have then we should check whether both coordinates are at the final position, then we return the coins otherwise we should return the minus infinity.
Check if the value is already calculated or not, if it is already calculated then return the value from the DP array.
Otherwise, Initialise the variable coins by minus infinity.
Recur for all possible ways:
1. (i, x) -> (i+1, x-1) or (i+1, x) or (i+1, x+1)
2. (i, y) -> (i+1, y-1) or (i+1, y) or (i+1, y+1)
Update the variable coins by the maximum value that is returned by recursion calls.
Final answer would be MAT[i][x] + MAT[i][y] + COINS, if x is not equal to y, otherwise the final answer would be MAT[i][x] + COINS.
Save the final answer in the DP array and return the final answer.

Space Complexity: O(n^3)Explanation:

O(N*M*M), where N is the number of rows and M is the number of columns of the matrix.

As we are using DP array of dimensions N*M*M to store answers.

Time Complexity: O(n^3)Explanation:

O(N*M*M) where N is the number of rows and M is the number of columns of the matrix.

We are row will be the same for both iterations but the column will not be the same thus, the dimension of DP will be N*M*M, thus time complexity will be O(N*M*M).

Accepted Answer

Iterative DP

Intuition:

The idea is to do both traversals concurrently. We start first from (0, 0) and second traversal from (0, m-1) simultaneously. The important thing to note is, at any particular step both traversals will be in the same row as in all possible three moves, the row number is increased. Since variation in y could occur in 3 ways i.e bottom, bottom right, bottom right. So in total 9 combinations are possible among y coordinates.

Approach:

Create a 3d DP array of dimensions N*M*M, where DP[i][j][k] will denote the maximum coins Alice and Bob can collect when Alice reaches at MAT[i][j] and Bob reaches at MAT[i][k]. It will contain minus infinity when the state is not reachable.
For 0th row, Alice and Bob have only one reachable state i.e MAT[0][0] for Alice and MAT[0][M-1] for Bob, thus fill the base conditions (dp[0]) as follows:
- Fill the DP[0] array by running a nested loop. Check if j is 0 and K is M-1 then the state is reachable check If there is only one column then DP[0][j][k] would be MAT[j][k], else DP[0][j][k] would be summation of MAT[0][j] + MAT[0][k].
- Otherwise, the current state is not reachable, thus fill DP[0][j][k] as minus infinity.
Fill the rest of the DP array.
- For any state DP[i][j][k], it will be the maximum of the following 9 cases.
  - COINS = MAX(DP[i-1][j-1][k-1], DP[i-1][j-1][k], DP[i-1][j-1][k+1], DP[i-1][j][k-1], DP[i-1][j][k], DP[i-1][j][k+1], DP[i-1][j+1][k-1], DP[i-1][j+1][k], DP[i-1][j+1][k+1])
Now DP[i][j][k] would depend on the condition that if j is equal to k then both Alice and Bob will be at the same cell, then
- DP[i][j][k] = COINS + MAT[i][j].
- Otherwise , DP[i][j][k] = MAT[i][j] + MAT[i][k] + COINS.
Finally, our answer would be DP[N-1][0][M-1]. The final destination of Alice and Bob are (N-1, 0) and (N-1, M-1) respectively.

Space Complexity: O(n^3)Explanation:

O(N*M*M), where N is the number of rows and M is the number of columns of the matrix.

As, we are using DP array of dimensions N*M*M to store answers.

Time Complexity: O(n^3)Explanation:

O(N*M*M) where N is the number of rows and M is the number of columns of the matrix.

Since we are filling the DP array of dimension N*M*M, thus it will take O(N*M*M).

Accepted Answer

State Compressed DP

Intuition:

The idea is to do both traversals concurrently. We start first from (0, 0) and second traversal from (0, m-1) simultaneously. The important thing to note is, at any particular step both traversals will be in the same row as in all possible three moves, the row number is increased. Since variation in y could occur in 3 ways i.e bottom, bottom right, bottom right. So in total 9 combinations are possible among y coordinates.

Approach:

Since maximum coins that are collected at any row ith will only depend on the number of coins that are collected at (i-1)th row, thus instead of using 3d array of size N*M*M we will use two 3d arrays of size 2*M*M with two variables (CURR and PREV) where to curr will store the answer of the ith row and PREV will store the answer of (i-1)th row, Now, if we will be at (i+1)th row then CURR array will become PREV array.

Create an array DP of dimensions 2*M*M, where DP[CURR][j][k] will denote the maximum coins Alice and Bob can collect when Alice reaches the jth column and Bob reaches the kth column. It will contain minus infinity when the state is not reachable.
We will have two variables CURR initialized with 0 and PREV initialized with 1 to denote the previous row and current row.
For the 0th row, Alice and Bob have only one reachable state i.e MAT[0][0] for Alice and MAT[0][M-1] for Bob, thus fill the base conditions as follows:
- Fill the DP[CURR] array by running a nested loop. Check if j is 0 and K is M-1 then the state is reachable check If there is only one column then DP[CURR][j][k] would be MAT[j][k], else DP[CURR][j][k] would be summation of MAT[0][j] + MAT[0][k].
- Otherwise, the current state is not reachable, thus fill DP[CURR][j][k] as minus infinity.
After the Base case for the next row, we will flip curr and prev
- CURR = CURR^1
- PREV = PREV^1
Now for the rest of the row from 1 to N-1.
- For any state DP[CURR][j][k], it will be the maximum of the following 9 cases.
  - COINS = MAX(DP[PREV][j-1][k-1], DP[PREV][j-1][k], DP[PREV][j-1][k+1], DP[PREV][j][k-1], DP[PREV][j][k], DP[PREV][j][k+1], DP[PREV][j+1][k-1], DP[PREV][j+1][k], DP[PREV][j+1][k+1])
Now DP[CURR][j][k] would depend on the condition that if j is equal to k then both Alice and Bob will be at the same cell, then
- DP[CURR][j][k] = COINS + MAT[i][j].
- Otherwise , DP[CURR][j][k] = MAT[i][j] + MAT[i][k] + COINS.
After we have traversed all the rows, our answer would be CURR[0][M-1]. The final destination of Alice and Bob are (N-1, 0) and (N-1, M-1) respectively.

Space Complexity: O(n^2)Explanation:

O(M*M), where M is the number of columns of the matrix.

As we are using arrays of dimensions 2*M*M to store answers of two consecutive rows at any particular instant.

Time Complexity: O(n^3)Explanation:

O(N*M*M) where N is the number of rows and M is the number of columns of the matrix.

Since we are creating and filling the DP[CURR] array of dimension M*M N times, thus it will take O(N*M*M).

You are given a two-dimensional matrix of integers of dimensions N*M, where each cell represents the number of coins in that cell. Alice and Bob have to collect the maximum number of coins. The followings are the conditions to collect coins:

Alice starts from top left corner, i.e., (0, 0) and should reach left bottom corner, i.e., (N-1, 0). Bob starts from top right corner, i.e., (0, M-1) and should reach bottom right corner, i.e., (N-1, M-1).

From a point (i, j), Alice and Bob can move to (i+1, j+1) or (i+1, j-1) or (i+1, j)

They have to collect all the coins that are present at a cell. If Alice has already collected coins of a cell, then Bob gets no coins if goes through that cell again.

For example :

Input Format:

Output Format:

Note:

Constraints:

Top Dunzo Software Developer interview questions & answers

Popular interview questions of Software Developer