741. Cherry Pickup

Problem

Cherry Pickup - LeetCodeLeetCode

Intuition

The initial intuition was to travel from (0,0) to (N-1, N-1) in the best possible path and do the reverse i.e. travel from (N-1, N-1) to (0,0) in the best possible path. Combining these two best paths would give me the solution.

But that won't give right solution all the time. That is because when we travel from top to bottom we modify the grid, i.e. whenever we get the cherry we convert it into 0. So the travel from (N-1, N-1) to (0,0), might not always get the best path as the grid is modified.

For interview purposes, if you do not know the below intuition it is almost impossible to arrive at correct solution, (not even optimised solution).

The next level of intuition is we need to check the paths simultaneously. That is traversing the grid in all possible ways from top-left and bottom-right. But this will also end up like the above first mentioned intuition as to avoid double counting, we need to keep modifying the grid.

Then the next level of intuition is we can start two pointers from start grid and reach till the end. This ensures that all the possible states are checked at single go. Double counting can be easily avoided adding one condition. This way we can make sure we are taking the best possible path at every iteration.

There can be space optimised version for this, but for a 45 minute interview, if we come up with above approach, it is an achievement in itself.

Time Complexity

Space Complexity

Solution

class Solution {
    public int cherryPickup(int[][] grid) {
        int N = grid.length;
        // return Math.max(0, recursiveHelper(0, 0, 0, 0, grid.length, grid));
        Integer[][][][] dp = new Integer[N][N][N][N];

        return Math.max(0, memoizationHelper(0, 0, 0, 0, N, grid, dp));
    }

    private int memoizationHelper(int row1, int col1, int row2, int col2, int N, int[][] grid, Integer[][][][] dp) {    
        // Time Complexity: O(N^4), as we have N^4 states/subproblems to solve. And each sub problem can be solved in constant time
        // Space Complexity: O(N^4), for the DP array

        // Base case: If any of the indices exceed the grid size or the cells are blocked (-1),
        // return the minimum value to indicate invalid path.
        if (row1 >= N || col1 >= N || row2 >= N || col2 >= N || grid[row1][col1] == -1 || grid[row2][col2] == -1) {
            return Integer.MIN_VALUE;
        }

        // If the result for the current cell combination is already memoized, return it.
        if (dp[row1][col1][row2][col2] != null) {
            return dp[row1][col1][row2][col2];
        }

        // Base case: If either of the robots reaches the bottom-right cell, return the cell value.
        if (row1 == N - 1 && col1 == N - 1) {
            return grid[row1][col1];
        }

        if (row2 == N - 1 && col2 == N - 1) {
            return grid[row2][col2];
        }

        int cherries;

        // Determine the number of cherries picked up in the current cells.
        if (row1 == row2 && col1 == col2) {
            cherries = grid[row1][col1];
        } else {
            cherries = grid[row1][col1] + grid[row2][col2];
        }

        // Recursively calculate the maximum cherries collected by moving each robot in different directions.
        int p1Downp2Down = memoizationHelper(row1 + 1, col1, row2 + 1, col2, N, grid, dp);
        int p1Downp2Right = memoizationHelper(row1 + 1, col1, row2, col2 + 1, N, grid, dp);
        int p1Rightp2Down = memoizationHelper(row1, col1 + 1, row2 + 1, col2, N, grid, dp);
        int p1Rightp2Right = memoizationHelper(row1, col1 + 1, row2, col2 + 1, N, grid, dp);

        // Add the maximum cherries obtained from different robot movements to the current cherries.
        cherries += getMax(p1Downp2Down, p1Downp2Right, p1Rightp2Down, p1Rightp2Right);

        // Memoize the result for the current cell combination.
        dp[row1][col1][row2][col2] = cherries;

        return cherries;
    }

    private int recursiveHelper(int row1, int col1, int row2, int col2, int N, int[][] grid) {
        // Time Complexity: O(4^(2n)), as we have 4 states/subproblems to solve at each cell and there are two persons for it. And each sub problem can be solved in constant time
        // Space Complexity: O(N), for the recursion stack

        // Base case: If any of the indices exceed the grid size or the cells are blocked (-1),
        // return the minimum value to indicate invalid path.
        if (row1 >= N || col1 >= N || row2 >= N || col2 >= N || grid[row1][col1] == -1 || grid[row2][col2] == -1) {
            return Integer.MIN_VALUE;
        }

        // Base case: If either of the robots reaches the bottom-right cell, return the cell value.
        if (row1 == N - 1 && col1 == N - 1) {
            return grid[row1][col1];
        }

        if (row2 == N - 1 && col2 == N - 1) {
            return grid[row2][col2];
        }

        int cherries;

        // Determine the number of cherries picked up in the current cells.
        if (row1 == row2 && col1 == col2) {
            cherries = grid[row1][col1];
        } else {
            cherries = grid[row1][col1] + grid[row2][col2];
        }

        // Recursively calculate the maximum cherries collected by moving each robot in different directions.
        int p1Downp2Down = recursiveHelper(row1 + 1, col1, row2 + 1, col2, N, grid);
        int p1Downp2Right = recursiveHelper(row1 + 1, col1, row2, col2 + 1, N, grid);
        int p1Rightp2Down = recursiveHelper(row1, col1 + 1, row2 + 1, col2, N, grid);
        int p1Rightp2Right = recursiveHelper(row1, col1 + 1, row2, col2 + 1, N, grid);

        // Add the maximum cherries obtained from different robot movements to the current cherries.
        cherries += getMax(p1Downp2Down, p1Downp2Right, p1Rightp2Down, p1Rightp2Right);

        return cherries;
    }

    private int getMax(Integer... cherryPaths) {
        int maxVal = Integer.MIN_VALUE;

        for(int cherries: cherryPaths) {
            maxVal = Math.max(maxVal, cherries);
        }

        return maxVal;
    }
}