Apple Pickup
Alice always loves to visit her garden and collect apples. The garden can be represented in the form of ‘N’ * ’N’ grid say ‘MATRIX’, where each cell of the grid can have one of the possible values:

1 - The cell contains an apple that Alice can pick up and pass through it. -1 - The cell contains a bush and Alice can not visit this cell. 0 - The cell is empty and Alice can pass through it.

Alice is present at the top left corner of the matrix or we can say at point (0,0).

Alice has to reach the bottom right corner of the matrix (‘N’-1,’N’-1) and return back to the starting point (0,0).

1. After picking an apple the cell will become empty. 2. While going towards the bottom right corner, Alice can either move Right or Down at each step. 3. While going towards the top left corner, Alice can either move Left or Up at each step. 4. If there is no path from (0,0) to (‘N’-1, ‘N’-1) then Alice will not pick any apple.

Your task is to help Alice to collect the maximum number of apples during her journey.

For example:

If the given matrix is : [1, 1, -1, 1] [1, 0, 1, 1] [1, 1, 0, 1] [0, -1, -1, 1] One of the possible ways to collect maximum apples is : Path for going towards bottom right corner: (0,0) - (0,1) - (1,1) - (1,2) - (1,3) - (2,3) - (3,3) Apples collected are equal to 6. Path for going towards top left corner: (3,3) - (2,3) -(2,2) - (2,1) - (2,0) - (1,0) - (0,0) Apples collected are equal to 3. So Alice can collect a maximum of 9 apples.

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases. Then each test case follows. The first line of each test case contains a space-separated integer ‘N’ representing the number of rows and columns. The next ‘N’ lines of each test case contain ‘N’ single space-separated integers denoting the values of ‘MATRIX’.

Output format:

For each test case, print a single line containing a single integer representing the maximum number of apples Alice can collect. The output of every test case will be printed in a separate line.

Note :

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints

1

Question

Apple Pickup

Alice always loves to visit her garden and collect apples. The garden can be represented in the form of ‘N’ * ’N’ grid say ‘MATRIX’, where each cell of the grid can have one of the possible values:

1 -> The cell contains an apple that Alice can pick up and pass through it.

-1 -> The cell contains a bush and Alice can not visit this cell.

0 -> The cell is empty and Alice can pass through it.

Alice is present at the top left corner of the matrix or we can say at point (0,0).

Alice has to reach the bottom right corner of the matrix (‘N’-1,’N’-1) and return back to the starting point (0,0).

1. After picking an apple the cell will become empty.

2. While going towards the bottom right corner, Alice can either move Right or Down at each step.

3. While going towards the top left corner, Alice can either move Left or Up at each step.

4. If there is no path from (0,0) to (‘N’-1, ‘N’-1) then Alice will not pick any apple.

Your task is to help Alice to collect the maximum number of apples during her journey.

For example:

If the given matrix is :
[1, 1, -1, 1]
[1, 0, 1, 1]
[1, 1, 0, 1]
[0, -1, -1, 1]

One of the possible ways to collect maximum apples is :

Path for going towards bottom right corner: 
(0,0) -> (0,1) -> (1,1) -> (1,2) -> (1,3) -> (2,3) -> (3,3)

Apples collected are equal to 6.

Path for going towards top left corner:
(3,3) -> (2,3) ->(2,2) -> (2,1) -> (2,0) -> (1,0) -> (0,0)

Apples collected are equal to 3.

So Alice can collect a maximum of 9 apples.

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of each test case contains a space-separated integer ‘N’ representing the number of rows and columns. 

The next ‘N’ lines of each test case contain ‘N’ single space-separated integers denoting the values of ‘MATRIX’.

Output format:

For each test case, print a single line containing a single integer representing the maximum number of apples Alice can collect.

The output of every test case will be printed in a separate line.

Note :

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints

1 <= T <=10
1 <= N <= 50
-1 <= MATRIX[i] <= 1

Where ‘T’ denotes the number of test cases, ‘N’ denotes the number of rows and columns of ‘MATRIX’.

Time limit: 1 sec.

Accepted Answer

I solved this using dynamic programming.

Accepted Answer

Recursion

The idea is to explore two paths simultaneously from (0,0) to (‘N’-1, ‘N’-1) and collect maximum apples. However, while implementing this approach we may count 1 apple two times, so we need to take care of this problem.

Complete Algorithm:

We will make a helper recursive function named ‘SOLVE’ which will receive 3 parameters ‘R1’, ‘C1’, ‘C2’.
We will calculate ‘R2’ = ‘R1’+’C1’-’C2’, (‘R1’+’C1’ == ‘R2’+’C2’) because at each step value of 1 variable is increased by 1 from both sides as each person will move 1 step.
Here (‘R1’, ‘C1’) will point to the current position for the first-person and (‘R2’,’ C2’) will point to the current position for a second person. All 4 variables will be initialized to a large negative value(INT_MIN).
Base Case:
- If ‘R1’ == ‘N’ -1 and ‘C1’ == ‘N’ -1 then do:
  - Return ‘MATRIX[ R1][C1]’.
- If ‘R2’ == ‘N’-1 and ‘C2’ == ‘N’-1 then do:
  - Return ‘MATRIX[ R2][C2]’.
- If both people are standing on the same point (‘R1’==’R2’ and ‘C1’==’C2’) then do:
  - Return ‘MATRIX[ R2][C2]’.
- Otherwise do:
  - Return ‘MATRIX[ R1][C1]’ + ‘MATRIX[ R2][C2]’.

Recursive Calls:
- Initialize an integer variable ‘ANS’=0.
- Now 4 possible combinations can be made :
- Let ‘DOWN_DOWN’ = Both person go to the Downside.
- Let ‘RIGHT_DOWN’ = the First-person goes to the Right side and second to the Downside.
- Let ‘DOWN_RIGHT’ = the First person goes to Downside and second to the Right side.
- Let RIGHT_RIGHT = Both person go to Right side.
- We can calculate the values of the above variable by making recursive calls.
  - DOWN_DOWN = SOLVE (R1+1, C1, R2+1, C2)
  - RIGHT_DOWN = SOLVE (R1, C1+1, R2+1, C2)
  - DOWN_RIGHT = SOLVE (R1+1, C1, R2, C2+1)
  - RIGHT_RIGHT = SOLVE (R1, C1+1, R2, C2+1)
Set ‘ANS’ = ‘ANS’ + the maximum of these 4 variables.
Return ‘ANS’.

Space Complexity: OtherExplanation:

O(4 ^ N), where ‘N’ is the number of steps.

This is the space used by the recursion stack to store 4 ^ N calls.

Time Complexity: OtherExplanation:

O(4 ^ N), where ‘N’ is the number of rows and columns.

As during each call to function we are making further 4 calls thus making time complexity as O(4 ^ N).

Accepted Answer

Recursion + Memoization

Our last approach was very simple and easy, but its time complexity was of exponential order. We can improve our solution by taking care of the overlapping subproblems. Thus, we will eliminate the need for solving the same subproblems again and again by storing them in a lookup table. This approach is known as Memoization.

We will initialize a 3-D array say ‘MEMO[N][N][N]’ with -1, where ‘N’ is the number of rows and columns. Where ‘MEMO[R1][C1][C2]’ equals -1 means the current state is not explored. Otherwise, ‘MEMO[R1][C1][C2]’ represents the max number of apples that can be collected by 2 people going from ‘R1’, ‘C1’ and ‘R2’, ‘C2’ to ‘N’-1, ‘N’-1.

So there will be two modification to the earlier approach :

In Base Case, first of all, we will check the value of ‘MEMO’ if it is not equal to -1, then simply return the value stored in the ‘MEMO’.
In Recursive Calls, before returning the ‘ANS’ we will store the value in ‘MEMO’.

Space Complexity: O(n^3)Explanation:

O(N ^ 3), where ‘N’ is the number of rows and columns.

As we will be using a 3 - D array of size N ^ 3.

Time Complexity: O(n^3)Explanation:

O(N ^ 3), where ‘N’ is the number of rows and columns.

In the worst case, after making N ^ 3 calls all the states will be explored and after that, we can use the result from ‘MEMO’.

Python (3.5)

'''

    Time Complexity: O(N ^ 3)

    Space Complexity: O(N ^ 3)



    Where N is the number of rows and columns.  

'''



import sys



memo = []



# Check whether coordinates are valid or not.

def valid(matrix, r1, c1, r2, c2):

    n = len(matrix)

    if (r1 >= 0 and c1 >= 0 and r1 < n and c1 < n and matrix[r1][c1] != -1 and r2 >= 0 and c2 >= 0 and r2 < n and c2 < n and matrix[r2][c2] != -1):

        return True

    

    return False



def solve(matrix, r1, c1, c2):

    n = len(matrix)



    # As r1+c1 == r2+c2 so, r2 = r1+c1-c2.

    r2 = r1 + c1 - c2



    # Base Case.

    if (r1 == n - 1 and c1 == n - 1):

        return matrix[r1][c1]



    if (r2 == n - 1 and c2 == n - 1):

        return matrix[r2][c2]

    

    # If state is already explored.

    if (memo[r1][c1][c2] != -1):

        return memo[r1][c1][c2]



    # Recursive Calls.

    ans = 0

    if (r1 == r2 and c1 == c2):

        ans = matrix[r1][c1]

    else:

        ans = matrix[r1][c1] + matrix[r2][c2]



    # Both down.

    downDown = -(sys.maxsize)

    if (valid(matrix, r1 + 1, c1, r2 + 1, c2)):

        downDown = solve(matrix, r1 + 1, c1, c2)



    # First down and second right.

    downRight = -(sys.maxsize)

    if (valid(matrix, r1 + 1, c1, r2, c2 + 1)):

        downRight = solve(matrix, r1 + 1, c1, c2 + 1)



    # First right and second down.

    rightDown = -(sys.maxsize)

    if (valid(matrix, r1, c1 + 1, r2 + 1, c2)):

        rightDown = solve(matrix, r1, c1 + 1, c2)

    

    # Both right.

    rightRight = -(sys.maxsize)

    if (valid(matrix, r1, c1 + 1, r2, c2 + 1)):

        rightRight = solve(matrix, r1, c1 + 1, c2 + 1)

    

    ans = ans + max(downDown, downRight, rightDown, rightRight)

    

    memo[r1][c1][c2] = ans

    return memo[r1][c1][c2]



def collectApples(matrix):

    n = len(matrix)



    # Handling corner cases.

    if (matrix[0][0] == -1 or matrix[n - 1][n - 1] == -1):

        return 0

    

    # Initializing memo table.

    global memo

    memo = [[[-1 for k in range(n)] for j in range(n)] for i in range(n)]

    return max(0, solve(matrix, 0, 0, 0))

Java (SE 1.8)

/*

    Time Complexity: O(N ^ 3)

    Space Complexity: O(N ^ 3)



    Where N is the number of rows and columns.  

*/



import java.util.ArrayList;

import java.util.Arrays;



public class Solution {



	static int memo[][][];

    

    // Check whether coordinates are valid or not.

    public static Boolean valid(ArrayList> matrix, int r1, int c1, int r2, int c2) {

        int n = matrix.size();

        if (r1 >= 0 && c1 >= 0 && r1 < n && c1 < n && matrix.get(r1).get(c1) != -1 && r2 >= 0 && c2 >= 0 && r2 < n && c2 < n && matrix.get(r2).get(c2) != -1) {

            return true;

        }



        return false;

    }



    public static int solve(ArrayList> matrix, int r1, int c1, int c2) {

        int n = matrix.size();



        // As r1+c1 == r2+c2 so, r2 = r1+c1-c2.

        int r2 = r1 + c1 - c2;



        // Base Case.

        if (r1 == n - 1 && c1 == n - 1) {

            return matrix.get(r1).get(c1);

        }

        if (r2 == n - 1 && c2 == n - 1) {

            return matrix.get(r2).get(c2);

        }



        // If state is already explored.

        if (memo[r1][c1][c2] != -1) {

            return memo[r1][c1][c2];

        }



        // Recursive Calls.

        int ans = 0;

        if (r1 == r2 && c1 == c2) {

            ans = matrix.get(r1).get(c1);

        } else {

            ans = matrix.get(r1).get(c1) + matrix.get(r2).get(c2);

        }



        // Both down.

        int downDown = Integer.MIN_VALUE;

        if (valid(matrix, r1 + 1, c1, r2 + 1, c2)) {

            downDown = solve(matrix, r1 + 1, c1, c2);

        }



        // First down and second right.

        int downRight = Integer.MIN_VALUE;

        if (valid(matrix, r1 + 1, c1, r2, c2 + 1)) {

            downRight = solve(matrix, r1 + 1, c1, c2 + 1);

        }



        // First right and second down.

        int rightDown = Integer.MIN_VALUE;

        if (valid(matrix, r1, c1 + 1, r2 + 1, c2)) {

            rightDown = solve(matrix, r1, c1 + 1, c2);

        }



        // Both right.

        int rightRight = Integer.MIN_VALUE;

        if (valid(matrix, r1, c1 + 1, r2, c2 + 1)) {

            rightRight = solve(matrix, r1, c1 + 1, c2 + 1);

        }



        ans = ans + Math.max(downDown, Math.max(downRight, Math.max(rightDown, rightRight)));

        return memo[r1][c1][c2] = ans;

    }



    public static int collectApples(ArrayList> matrix) {

        int n = matrix.size();



        // Handling corner cases.

        if (matrix.get(0).get(0) == -1 || matrix.get(n-1).get(n-1) == -1) {

            return 0;

        }



        // Initializing memo table.

        memo = new int[n][n][n];

        for(int i = 0; i < n; i++){

            for(int j = 0; j < n; j++){

                Arrays.fill(memo[i][j],-1);

            }

        }



        return Math.max(0, solve(matrix, 0, 0, 0));

    }

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N ^ 3)

    Space Complexity: O(N ^ 3)



    Where N is the number of rows and columns.    

*/



#include

#include



vector < vector < vector < int >>> memo;



// Check whether coordinates are valid or not.

bool valid(vector < vector < int >> & matrix, int r1, int c1, int r2, int c2) 

{

    int n = matrix.size();

    if (r1 >= 0 and c1 >= 0 and r1 < n and c1 < n and matrix[r1][c1] != -1 and r2 >= 0 and c2 >= 0 and r2 < n and c2 < n and matrix[r2][c2] != -1) 

    {

        return true;

    }

    return false;

}



int solve(vector < vector < int >> & matrix, int r1, int c1, int c2) 

{

    int n = matrix.size();



    // As r1+c1 == r2+c2 so, r2 = r1+c1-c2.

    int r2 = r1 + c1 - c2;



    // Base Case.

    if (r1 == n - 1 and c1 == n - 1) 

    {

        return matrix[r1][c1];

    }

    if (r2 == n - 1 and c2 == n - 1) 

    {

        return matrix[r2][c2];

    }



    // If state is already explored.

    if (memo[r1][c1][c2] != -1) 

    {

        return memo[r1][c1][c2];

    }



    // Recursive Calls.

    int ans = 0;

    if (r1 == r2 and c1 == c2) 

    {

        ans = matrix[r1][c1];

    } else 

    {

        ans = matrix[r1][c1] + matrix[r2][c2];

    }



    // Both down.

    int downDown = INT_MIN;

    if (valid(matrix, r1 + 1, c1, r2 + 1, c2)) 

    {

        downDown = solve(matrix, r1 + 1, c1, c2);

    }



    // First down and second right.

    int downRight = INT_MIN;

    if (valid(matrix, r1 + 1, c1, r2, c2 + 1)) 

    {

        downRight = solve(matrix, r1 + 1, c1, c2 + 1);

    }



    // First right and second down.

    int rightDown = INT_MIN;

    if (valid(matrix, r1, c1 + 1, r2 + 1, c2)) 

    {

        rightDown = solve(matrix, r1, c1 + 1, c2);

    }



    // Both right.

    int rightRight = INT_MIN;

    if (valid(matrix, r1, c1 + 1, r2, c2 + 1)) 

    {

        rightRight = solve(matrix, r1, c1 + 1, c2 + 1);

    }

    ans = ans + max({

        downDown,

        downRight,

        rightDown,

        rightRight

    });

    return memo[r1][c1][c2] = ans;

}



int collectApples(vector < vector < int >> & matrix) 

{

    int n = matrix.size();



    // Handling corner cases.

    if (matrix[0][0] == -1 or matrix[n - 1][n - 1] == -1) 

    {

        return 0;

    }



    // Initializing memo table.

    memo = vector < vector < vector < int >>> (n, vector < vector < int >> (n, vector < int > (n, -1)));

    return max(0, solve(matrix, 0, 0, 0));

}

Accepted Answer

Bottom-UP DP

As our earlier approach recursion with memoization surely avoided some subproblems but we can still improve time complexity using a bottom-up approach and we will also reduce the space complexity to O(N^2).

Complete Algorithm:

We will initialize a 2-D array ‘DP[N][N]’ with -1, where ‘N’ is the number of rows and columns. Here DP represents the maximum number of apples two k-length paths can pickup and two k-length paths arrive at (i, k - i) and (j, k - j), respectively.
Set ‘DP[0][0]’ = ‘MATRIX[0][0]’.
Intialise an integer variable ‘MAXK’ = 2*N -1.
Run a loop for 1<= ‘k’ <= ‘MAXK’ and do:
- Run a loop for min(N-1,K)<= ‘i’ <=0 and do:
  - If (k-i) is greater than ‘N’ then do:
    - Continue iterating.
  - Run a loop for min(N-1,K)<= ‘j’ <=0 and do:
    - If (k-j) >= ‘N’ or ‘MATRIX[i][k-1]’ <0 or ‘MATRIX[j][k-j] <0 then do:
      - Set ‘DP[i][j]’ = -1.
    - Intialise an integer variables “COUNT’ = ‘DP[i][j]’.
    - ‘COUNT’ = maximum of ( ‘DP[i][j-1]’ , ‘DP[i-1][j]’ , ‘DP[i-1][j-1]’ , ‘COUNT’ ) .
    - Set DP[i][j] = ‘COUNT’ + ‘MATRIX[i][k-i]’
    - If i is not equal to j then do:
      - Set DP[i][j] = ‘DP[i][j]’ + ‘MATRIX[j][k-j]’
Return DP[N-1][N-1].

Space Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the number of rows and columns.

As we will are using a 2-D array of size N ^ 2.

Time Complexity: O(n^3)Explanation:

O(N ^ 3), where ‘N’ is the number of rows and columns.

As we are running 3 nested loops.

Python (3.5)

'''

    Time Complexity: O(N ^ 3)

    Space Complexity: O(N ^ 2)



    Where N is the number of rows and columns.   

'''



def collectApples(matrix):

    n = len(matrix)



    # Handling corner cases.

    if (matrix[0][0] == -1 or matrix[n - 1][n - 1] == -1):

        return 0



    # Intialising DP table.

    dp = [[-1 for j in range(n)] for i in range(n)]

    

    dp[0][0] = matrix[0][0]

    maxK = 2 * n - 2

    for k in range(1, maxK + 1):

        for i in range(min(n - 1, k), -1, -1):

            if (k - i >= n):

                continue



            for j in range(min(n - 1, k), -1, -1):

                if (k - j >= n or matrix[i][k - i] < 0 or matrix[j][k - j] < 0):

                    dp[i][j] = -1

                    continue



                count = dp[i][j]

                if (i > 0):

                    count = max(count, dp[i - 1][j])



                if (j > 0):

                    count = max(count, dp[i][j - 1])

                

                if (i > 0 and j > 0):

                    count = max(count, dp[i - 1][j - 1])



                if (count < 0):

                    continue

        

                dp[i][j] = count + matrix[i][k - i]

                if (i != j):

                    dp[i][j] += matrix[j][k - j]               



    return max(dp[n - 1][n - 1], 0)

C++ (g++ 5.4)

/*

    Time Complexity: O(N ^ 3)

    Space Complexity: O(N ^ 2)



    Where N is the number of rows and columns.   

*/



int collectApples(vector < vector < int >> & matrix) {

    int n = matrix.size();

    // Handling corner cases.

    if (matrix[0][0] == -1 or matrix[n - 1][n - 1] == -1) 

    {

        return 0;

    }



    // Intialising DP table.

    vector> dp(n, vector < int > (n, -1));

    

    dp[0][0] = matrix[0][0];

    int maxK = 2 * n - 2;

    for (int k = 1; k <= maxK; k++) 

    {

        for (int i = min(n - 1, k); i >= 0; i--) 

        {

            if (k - i >= n)

            {

                continue;

            }

            for (int j = min(n - 1, k); j >= 0; j--) 

            {

                if (k - j >= n or matrix[i][k - i] < 0 or matrix[j][k - j] < 0) 

                {

                    dp[i][j] = -1;

                    continue;

                }



                int count = dp[i][j];

                if (i > 0) 

                {

                    count = max(count, dp[i - 1][j]);

                }

                if (j > 0) 

                {

                    count = max(count, dp[i][j - 1]);

                }

                if (i > 0 and j > 0) 

                {

                    count = max(count, dp[i - 1][j - 1]);

                }



                if (count < 0) 

                {

                    continue;

                }

                dp[i][j] = count + matrix[i][k - i];

                if (i != j) 

                {

                    dp[i][j] += matrix[j][k - j];

                }



            }

        }

    }

    return max(dp[n - 1][n - 1], 0);

}

Java (SE 1.8)

/*

    Time Complexity: O(N ^ 3)

    Space Complexity: O(N ^ 2)



    Where N is the number of rows and columns.  

*/



import java.util.ArrayList;

import java.util.Arrays;



public class Solution {

    public static int collectApples(ArrayList> matrix) {

        int n = matrix.size();



        // Handling corner cases.

        if (matrix.get(0).get(0) == -1 || matrix.get(n-1).get(n - 1) == -1) {

            return 0;

        }



        // Intialising DP table.

        int dp[][] = new int[n][n];

        for(int i = 0; i < n; i++)

        {

            Arrays.fill(dp[i],-1);

        }

        dp[0][0] = matrix.get(0).get(0);

        int maxK = 2 * n - 2;

        for (int k = 1; k <= maxK; k++) {

            for (int i = Math.min(n - 1, k); i >= 0; i--) {

                if (k - i >= n){

                    continue;

                }

                for (int j = Math.min(n - 1, k); j >= 0; j--) {

                    if (k - j >= n || matrix.get(i).get(k - i) < 0 || matrix.get(j).get(k - j) < 0) {

                        dp[i][j] = -1;

                        continue;

                    }



                    int count = dp[i][j];

                    if (i > 0) {

                        count = Math.max(count, dp[i - 1][j]);

                    }

                    if (j > 0) {

                        count = Math.max(count, dp[i][j - 1]);

                    }

                    if (i > 0 && j > 0) {

                        count = Math.max(count, dp[i - 1][j - 1]);

                    }



                    if (count < 0) {

                        continue;

                    }

                    dp[i][j] = count + matrix.get(i).get(k - i);

                    if (i != j) {

                        dp[i][j] += matrix.get(j).get(k - j);

                    }



                }

            }

        }

        return Math.max(dp[n - 1][n - 1], 0);

    }

}

Alice always loves to visit her garden and collect apples. The garden can be represented in the form of ‘N’ * ’N’ grid say ‘MATRIX’, where each cell of the grid can have one of the possible values:

Alice is present at the top left corner of the matrix or we can say at point (0,0).

Alice has to reach the bottom right corner of the matrix (‘N’-1,’N’-1) and return back to the starting point (0,0).

Your task is to help Alice to collect the maximum number of apples during her journey.

For example:

Input Format:

Output format:

Note :

Constraints

Top Cisco Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Cisco Software Developer