Chocolate Pickup
Ninja has a 'GRID' of size 'R' X 'C'. Each cell of the grid contains some chocolates. Ninja has two friends Alice and Bob, and he wants to collect as many chocolates as possible with the help of his friends.

Initially, Alice is in the top-left position i.e. (0, 0), and Bob is in the top-right place i.e. (0, ‘C’ - 1) in the grid. Each of them can move from their current cell to the cells just below them. When anyone passes from any cell, he will pick all chocolates in it, and then the number of chocolates in that cell will become zero. If both stay in the same cell, only one of them will pick the chocolates in it.

If Alice or Bob is at (i, j) then they can move to (i + 1, j), (i + 1, j - 1) or (i + 1, j + 1). They will always stay inside the ‘GRID’.

Your task is to find the maximum number of chocolates Ninja can collect with the help of his friends by following the above rules.

Example:

Input: ‘R’ = 3, ‘C’ = 4 ‘GRID’ = [[2, 3, 1, 2], [3, 4, 2, 2], [5, 6, 3, 5]] Output: 21 Initially Alice is at the position (0,0) he can follow the path (0,0) - (1,1) - (2,1) and will collect 2 + 4 + 6 = 12 chocolates. Initially Bob is at the position (0, 3) and he can follow the path (0, 3) - (1,3) - (2, 3) and will colllect 2 + 2 + 5 = 9 chocolates. Hence the total number of chocolates collected will be 12 + 9 = 21. there is no other possible way to collect a greater number of chocolates than 21.

Input Format :

The first line of input contains an integer 'T', denoting the number of test cases. For each test case, the first line contains two integers' R' and 'C' denoting the number of rows and number of columns in the grid. Next 'R' lines will contain 'C' integers each the value of each cell in the grid.

Output format :

For each test case, print the maximum number of chocolates that can be collected. Output for each test case will be printed in a separate line.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1

Question

Chocolate Pickup

Ninja has a 'GRID' of size 'R' X 'C'. Each cell of the grid contains some chocolates. Ninja has two friends Alice and Bob, and he wants to collect as many chocolates as possible with the help of his friends.

Initially, Alice is in the top-left position i.e. (0, 0), and Bob is in the top-right place i.e. (0, ‘C’ - 1) in the grid. Each of them can move from their current cell to the cells just below them. When anyone passes from any cell, he will pick all chocolates in it, and then the number of chocolates in that cell will become zero. If both stay in the same cell, only one of them will pick the chocolates in it.

If Alice or Bob is at (i, j) then they can move to (i + 1, j), (i + 1, j - 1) or (i + 1, j + 1). They will always stay inside the ‘GRID’.

Your task is to find the maximum number of chocolates Ninja can collect with the help of his friends by following the above rules.

Example:

Input: ‘R’ = 3, ‘C’ = 4
       ‘GRID’ = [[2, 3, 1, 2], [3, 4, 2, 2], [5, 6, 3, 5]]
Output: 21

Initially Alice is at the position (0,0) he can follow the path (0,0) -> (1,1) -> (2,1) and will collect 2 + 4 + 6 = 12 chocolates.

Initially Bob is at the position (0, 3) and he can follow the path (0, 3) -> (1,3) -> (2, 3) and will colllect 2 + 2 + 5 = 9 chocolates.

Hence the total number of chocolates collected will be 12 + 9 = 21. there is no other possible way to collect a greater number of chocolates than 21.

Input Format :

The first line of input contains an integer 'T', denoting the number of test cases. 

For each test case, the first line contains two integers' R' and 'C' denoting the number of rows and number of columns in the grid. 

Next 'R' lines will contain 'C' integers each the value of each cell in the grid.

Output format :

For each test case, print the maximum number of chocolates that can be collected.

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

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= ‘T’ <= 10
2 <= 'R', 'C' <= 50
0 <= 'GRID[i][j]'<= 10^2
Time Limit: 1sec

Accepted Answer

I was able to pass only 1 test case out of 5

Accepted Answer

Brute Force Solution

Approach: Say Alice is at column 'C1' and Bob is at column 'C2' of row 'R'. We will try all possible ways of moving both of them to the next row 'R' + 1 under the given conditions.

Each person has three choices in the next row, so combined, they have 3 * 3 = 9 choices. Among these nine choices, we will consider the path which gives us the maximum score. In case both of them land on the same cell in a row, we will add that cell's value only once.

We will implement the above logic recursively.

Algorithm :

We will pass the ‘currRow’ as 0 as both are on the starting point and ‘C1’ as 0 and ‘C2’ as ‘C’ - 1 as coordinates of Alice and Bob respectively.
Return 'getMaximumChocolates(0, 0, C - 1, grid)’.

maximumChocolatesHelper(currRow, C1, C2, GRID):

Check if current coordinates 'currRow', 'C1', and 'C2' are valid or not. If they are not valid, then return 0.
Declare and Initialize variable 'maximumChocolates' with 0.
Run a loop from -1 to 1 with variable 'i' and another nested loop from -1 to 1 with variable 'j'.
Update 'maximumChocolates' with the maximum of it and 'maximumChocolatesHelper(currRow + 1, C1 + i, C2 + j, GRID)'
If ‘C1!=C2’ then add ‘grid[r][c2]’ to the ‘maximumChocolates’.
Return '(maximumChocolates + grid[r][c1])’.

Space Complexity: OtherExplanation:

O(R*C), where 'R' is the number of rows, and 'C' is the number of columns in the grid.

As we are using the recursion, the recursion stack's maximum depth will be the 'R*C'; hence, the space complexity will be the O(R*C).

Time Complexity: OtherExplanation:

O(3^(R*C)), where 'R' is the number of rows, and 'C' is the number of columns in the grid.

As we are using the recursive solution, there can be at max three calls per coordinates in the recursion, and there are N*M possible coordinates for the grid. Hence there will be a maximum 3^(R*C) calls. Thus asymptotically, the time complexity will be O(3^(R*C)

Accepted Answer

Recursive Dynamic Programming Solution

Approach: In the first recursive brute force approach, there are repeated calculations due to overlapping paths. We will use memoization to speed things up.

We will use dynamic programming, and 'dp[R][C1][C2]' will maintain the maximum total score that both robots can accumulate till the end when starting from columns 'C1' and 'C2' of row 'R'.

We will optimize it more by skipping 'C1' > 'C2' paths because scores of those paths would already be counted in symmetrical 'C1' < 'C2' paths.

Algorithm :

Initialize one 3D ‘DP’ array with all values -1.
We will pass the ‘currRow’ as 0 as both are on the starting point and ‘C1’ as 0 and ‘C2’ as ‘C’ - 1 as coordinates of Alice and Bob respectively.
Return 'getMaximumChocolates(0, 0, C - 1, grid, dp)’.

maximumChocolatesHelper(currRow, C1, C2, grid, DP):

Check if current coordinates 'currRow', 'C1', and 'C2' are valid or not. If they are not valid, then return 0.
If ‘DP[currRow][C1][C2]’ is not -1 then return it’s value.
Declare and Initialize variable 'maximumChocolates' with 0.
Run a loop from -1 to 1 with variable 'i' and another nested loop from -1 to 1 with variable 'j'.
Update 'maximumChocolates' with the maximum of it and 'maximumChocolatesHelper(currRow + 1, C1 + i, C2 + j, grid)'
If ‘C1!=C2’ then add ‘grid[r][c2]’ to the ‘maximumChocolates’.
Return ‘DP[currRow][C1][C2]’ = '(maximumChocolates + grid[r][c1]).

Space Complexity: OtherExplanation:

O(R*(C^2)), where 'R' is the number of rows, and 'C' is the number of columns in the grid.

We are using an extra ‘DP’ array of size R*(C^2) and we are using the recursion with maximum recursive stack (R*C) hence the space complexity will be O(R*(C^2)).

Time Complexity: OtherExplanation:

O(R*(C^2)), where 'R' is the number of rows, and 'C' is the number of columns in the grid.

As we are using memoization to optimize the recursion here. There will be a maximum of R*(C^2) recursion calls and further calls will be optimized by dynamic programming. Hence the time complexity will be O(R*(C^2))

Python (3.5)

'''

    Time complexity: O(R*(C^2))

    Space complexity: O(R*(C^2))



    Where 'R' is the number of rows and 'C' is the number of columns in the grid.

'''



from typing import List





def maximumChocolatesHelper(currRow: int, c1: int, c2: int, grid: List[List[int]], dp: List[List[List[int]]]) -> int:



    # Return 0 if current coordinates are not valid.

    if (currRow == len(grid) or c1 < 0 or c1 >= len(grid[0]) or c2 < 0 or c2 >= len(grid[0]) or c1 > c2):

        return 0



    # If current state is already visited.

    if (dp[currRow][c1][c2] != -1):

        return dp[currRow][c1][c2]



    # Initializing the variable 'maximumChocolates'.

    maximumChocolates = 0



    for i in range(-1, 2):

        for j in range(-1, 2):



            # Updating the variable 'maximumChocolates'.

            maximumChocolates = max(maximumChocolates, maximumChocolatesHelper(

                currRow + 1, c1 + i, c2 + j, grid, dp))



    # Condition when both of them are on same coordinate.

    if (c1 != c2):

        maximumChocolates += grid[currRow][c2]



    dp[currRow][c1][c2] = (maximumChocolates + grid[currRow][c1])

    return dp[currRow][c1][c2]





def maximumChocolates(r: int, c: int, grid: List[List[int]]) -> int:



    dp = [[[-1 for i in range(c)] for j in range(c)] for k in range(r)]

    return maximumChocolatesHelper(0, 0, c - 1, grid, dp)

Java (SE 1.8)

/*
    Time complexity: O(R * (C^2))
    Space complexity: O(R * (C^2))

    Where 'R' is the number of rows and 'C' is the number of columns in the grid.
*/

public class Solution {
    public static int maximumChocolates(int r, int c, int[][] grid) {
        int[][][] dp = new int[r][c][c];
        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){
                for(int k = 0; k < c; k++){
                    dp[i][j][k] = -1;
                }
            }
        }

        return maximumChocolatesHelper(0, 0, c - 1, grid, dp);
    }

    // Helper function to find the maximum chocolates can be collected.
    public static int maximumChocolatesHelper(int currRow, int c1, int c2, 
        int[][] grid, int[][][] dp) {

        // Return 0 if current coordinates are not valid.
        if (currRow == grid.length || c1 < 0 || c1 >= grid[0].length || 
            c2 < 0 || c2 >= grid[0].length || c1 > c2) {

            return 0;
        }

        // If current state is already visited.
        if (dp[currRow][c1][c2] != -1) {
            return dp[currRow][c1][c2];
        }

        // Initializing the variable 'maximumChocolates'.
        int maximumChocolates = 0;
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                // Updating the variable 'maximumChocolates'.
                maximumChocolates = Math.max(maximumChocolates, 
                    maximumChocolatesHelper(currRow + 1, c1 + i, c2 + j, grid, dp));
            }
        }

        // Condition when both of them are on same coordinate.
        if (c1 != c2) {
            maximumChocolates += grid[currRow][c2];
        }

        dp[currRow][c1][c2] = (maximumChocolates + grid[currRow][c1]);

        return dp[currRow][c1][c2];
    }
}

C++ (g++ 5.4)

/*

    Time complexity: O(R*(C^2))

    Space complexity: O(R*(C^2))



    Where 'R' is the number of rows and 'C' is the number of columns in the grid.

*/



// Helper function to find the maximum chocolates can be collected.

int maximumChocolatesHelper(int currRow, int c1, int c2, vector> &grid, vector>> &dp) {

    // Return 0 if current coordinates are not valid.

    if (currRow == grid.size() || c1 < 0 || c1 >= grid[0].size() || c2 < 0 || c2 >= grid[0].size() || c1 > c2) {

        return 0;

    }



    // If current state is already visited.

    if (dp[currRow][c1][c2] != -1) {

        return dp[currRow][c1][c2];

    }



    // Initializing the variable 'maximumChocolates'.

    int maximumChocolates = 0;

    for (int i = -1; i <= 1; i++) {

        for (int j = -1; j <= 1; j++) {

            // Updating the variable 'maximumChocolates'.

            maximumChocolates = max(maximumChocolates, maximumChocolatesHelper(currRow + 1, c1 + i, c2 + j, grid, dp));

        }

    }



    // Condition when both of them are on same coordinate.

    if (c1 != c2) {

        maximumChocolates += grid[currRow][c2];

    }

    return dp[currRow][c1][c2] = (maximumChocolates + grid[currRow][c1]);

}



int maximumChocolates(int r, int c, vector> &grid) {

    vector>> dp(r, vector>(c, vector(c, -1)));

    return maximumChocolatesHelper(0, 0, c - 1, grid, dp);

}

Accepted Answer

Iterative Dynamic Programming Solution

Approach:

We can also solve this problem using iterative dynamic programming. The approach is similar to the recursive approach with a slight change. We will start from the base conditions instead of the other way around. The idea is to keep only the previous row dp array in memory and construct the current row dp array thanks to it. Then when the current loop is finished, we just have to assign the previous row dp array to be the current row dp array.

Algorithm :

Initialize the 2D vector 'prev_dp' of size 'C^2'
Run a loop from 0 to 'R' with variable 'row'
- Initialize a 2D vector 'current_dp' of size 'C^2'
- Run a loop from 0 to 'min(c, row + 1) with variable 'C1'
  - Run a nested loop from 0 to 'max(0, c - 1 - row)' with variable 'C2'
    - Initialize a variable 'prev_max' with 0.
    - Run a loop from 'max(0, c1 - 1)' to 'min(c - 1, c1 + 1)' with variable 'offset1'
      - Run a nested loop from 'max(0, c2 - 1)' to 'min(c - 1, c2 + 1)' with variable 'offset2'
        Update 'prev_max' with 'max(prev_max, prev_dp[offset1][offset2])'
    - If ‘C1’ == 'C2' then update 'current_dp[c1][c2]' with 'prev_max + grid[row][c1]'
    - Else update 'current_dp[c1][c2]' with 'prev_max + grid[row][c1] + grid[row][c2]'
Initialize a variable 'res' by 0
Run a loop from 0 to 'C' with variable 'i' and run a nested loop from 0 to 'C' with variable 'j'
- Update 'res' with 'max(res, prev_dp[i][j])'
Return 'res'

Space Complexity: OtherExplanation:

O(C^2), where 'R' is the number of rows, and 'C' is the number of columns in the grid.

As we are using an extra ‘prev_dp’ array of size ‘C^2’ and ‘current_dp’ array of size ‘C^2’ the space complexity will be O(C^2).

Time Complexity: OtherExplanation:

O(R*(C^2)), where 'R' is the number of rows, and 'C' is the number of columns in the grid.

As we are using three nested loops one iterates ‘R’ times and the other two iterates ‘C’ times. Hence the time complexity will be O(R * (C^2))

Python (3.5)

'''

    Time complexity: O(R*(C^2))

    Space complexity: O(C^2)



    Where 'R' is the number of rows and 'C' is the number of columns in the grid.

'''





from typing import List





def maximumChocolates(r: int, c: int, grid: List[List[int]]) -> int:

    # Initializing the 'prev_dp' vector.

    prev_dp = [[0 for i in range(c)] for j in range(c)]



    # Running a loop from 0 to 'r'.

    for row in range(r):

        # Initializing a 'current_dp' vector.

        current_dp = [[0 for i in range(c)] for j in range(c)]



        # Running a loop from 0 to 'min(c, row + 1)'.

        for c1 in range(min(c, row + 1)):

            # Running a loop from 'max(0, c - 1 - row)' to 'c'.

            for c2 in range(max(0, c-1-row), c):



                # Initializing a variable 'prev_max'.

                prev_max = 0



                for offset1 in range(max(0, c1 - 1), min(c-1, c1 + 1) + 1):

                    for offset2 in range(max(0, c2-1), min(c-1, c2 + 1)+1):

                        #  Updating the variable 'prev_max'.

                        prev_max = max(prev_max, prev_dp[offset1][offset2])



                # Case when both are in same row.

                if (c1 == c2):

                    current_dp[c1][c2] = prev_max + grid[row][c1]

                else:

                    current_dp[c1][c2] = prev_max + \

                        grid[row][c1] + grid[row][c2]



        prev_dp = current_dp



    res = 0

    for i in range(c):

        for j in range(c):

            # Updating the variable 'res' with max possible answer.

            res = max(res, prev_dp[i][j])



    return res

Java (SE 1.8)

/*
    Time complexity: O(R * (C^2))
    Space complexity: O(C^2)

    Where 'R' is the number of rows and 'C' is the number of columns in the grid.
*/

public class Solution {
    public static int maximumChocolates(int r, int c, int[][] grid) {
        // Initializing the 'prev_dp' vector.
        int[][] prev_dp = new int[c][c];

        // Running a loop from 0 to 'r'.
        for (int row = 0; row < r; row++) {

            // Initializing a 'current_dp' vector.
            int[][] current_dp = new int[c][c];

            // Running a loop from 0 to 'min(c, row + 1)'.
            for (int c1 = 0; c1 < Math.min(c, row + 1); c1++) {

                // Running a loop from 'max(0, c - 1 - row)' to 'c'.
                for (int c2 = Math.max(0, c - 1 - row); c2 < c; c2++) {

                    // Initializing a variable 'prev_max'.
                    int prev_max = 0;
                    for (int offset1 = Math.max(0, c1 - 1); 
                        offset1 <= Math.min(c - 1, c1 + 1); offset1++) {

                        for (int offset2 = Math.max(0, c2 - 1); 
                            offset2 <= Math.min(c - 1, c2 + 1); offset2++) {

                            // Updating the variable 'prev_max'.
                            prev_max = Math.max(prev_max, prev_dp[offset1][offset2]);
                        }
                    }

                    // Case when both are in same row.
                    if (c1 == c2) {
                        current_dp[c1][c2] = prev_max + grid[row][c1];
                    } else {
                        current_dp[c1][c2] = prev_max + grid[row][c1] + grid[row][c2];
                    }
                }
            }

            prev_dp = current_dp;
        }

        int res = 0;
        for (int i = 0; i < c; i++) {
            for (int j = 0; j < c; j++) {
                // Updating the variable 'res' with max possible answer.
                res = Math.max(res, prev_dp[i][j]);
            }
        }
        
        return res;
    }
}

C++ (g++ 5.4)

/*

    Time complexity: O(R*(C^2))

    Space complexity: O(C^2)



    Where 'R' is the number of rows and 'C' is the number of columns in the grid.

*/



int maximumChocolates(int r, int c, vector> &grid) {

    // Initializing the 'prev_dp' vector.

    vector> prev_dp(c, vector(c));



    // Running a loop from 0 to 'r'.

    for (int row = 0; row < r; row++) {

        // Initializing a 'current_dp' vector.

        vector> current_dp(c, vector(c));

        // Running a loop from 0 to 'min(c, row + 1)'.

        for (int c1 = 0; c1 < min(c, row + 1); c1++) {

            // Running a loop from 'max(0, c - 1 - row)' to 'c'.

            for (int c2 = max(0, c - 1 - row); c2 < c; c2++) {

                // Initializing a variable 'prev_max'.

                int prev_max = 0;

                for (int offset1 = max(0, c1 - 1); offset1 <= min(c - 1, c1 + 1); offset1++) {

                    for (int offset2 = max(0, c2 - 1); offset2 <= min(c - 1, c2 + 1); offset2++) {

                        // Updating the variable 'prev_max'.

                        prev_max = max(prev_max, prev_dp[offset1][offset2]);

                    }

                }

                // Case when both are in same row.

                if (c1 == c2) {

                    current_dp[c1][c2] = prev_max + grid[row][c1];

                } else {

                    current_dp[c1][c2] = prev_max + grid[row][c1] + grid[row][c2];

                }

            }

        }

        prev_dp = current_dp;

    }

    int res = 0;

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

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

            // Updating the variable 'res' with max possible answer.

            res = max(res, prev_dp[i][j]);

        }

    }

    return res;

}

Ninja has a 'GRID' of size 'R' X 'C'. Each cell of the grid contains some chocolates. Ninja has two friends Alice and Bob, and he wants to collect as many chocolates as possible with the help of his friends.

If Alice or Bob is at (i, j) then they can move to (i + 1, j), (i + 1, j - 1) or (i + 1, j + 1). They will always stay inside the ‘GRID’.

Your task is to find the maximum number of chocolates Ninja can collect with the help of his friends by following the above rules.

Example:

Input Format :

Output format :

Note :

Constraints :

Top HashedIn by Deloitte Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in HashedIn by Deloitte Software Developer