What is the time complexity of Cherry Pickup?

The optimal solution has a time complexity of O(n^3).

What is the space complexity of Cherry Pickup?

The space complexity is O(n^2).

What data structures are used to solve Cherry Pickup?

This problem uses Array, Dynamic Programming, Matrix. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Cherry Pickup?

Insight 1: Two paths can be considered as two people walking from (0,0) at the same time. This is crucial because we need to account for picking the same cherry twice if we simply do two independent pathfinding attempts. Insight 2: Dynamic programming is suitable because the optimal solution depends on the optimal solutions of subproblems (i.e., the maximum cherries collected up to a certain point).

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Cherry Pickup - LeetCode 741 Solution

Q: Which companies ask LeetCode 741. Cherry Pickup in interviews?

This problem is frequently asked at Akuna Capital, Atlassian, Cisco, Flipkart, J.P. Morgan and 2 more companies.

Cherry Pickup - Complete Solution Guide

Cherry Pickup is LeetCode problem 741, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given an n x n grid representing a field of cherries, each cell is one of three possible integers. 0 means the cell is empty, so you can pass through, 1 means the cell contains a cherry that you can pick up and pass through, or -1 means the cell contains a thorn that blocks your way. Return the maximum number of cherries you can collect by following the rules below : Starting at the position (0, 0) and reaching (n - 1, n - 1) by moving right or down through valid path cells (cells with v

Detailed Explanation

The Cherry Pickup problem presents an n x n grid representing a field of cherries. Each cell can be empty (0), contain a cherry (1), or be blocked by a thorn (-1). The goal is to find the maximum number of cherries that can be collected by starting at the top-left corner (0, 0), moving only right or down to reach the bottom-right corner (n-1, n-1), and then returning to (0, 0) by moving only left or up. When a cherry is picked, the cell becomes empty (0). If no valid path exists, the output should be 0. The key is to maximize cherry collection during both forward and backward paths.

Solution Approach

The provided solutions use a dynamic programming approach. Instead of thinking about two separate trips (forward and backward), the problem is reframed as two people starting at (0, 0) and moving simultaneously towards (n-1, n-1). `dp[r1][r2]` stores the maximum cherries collected when the first person is at row `r1` and the second person is at row `r2` after `k` steps (where k = r1 + c1 = r2 + c2). The code iterates through all possible values of `k` from 1 to `2n - 2`. For each `k`, it considers all possible row positions `r1` and `r2` for the two people. It calculates the corresponding column positions `c1` and `c2` based on `k`. The code then checks if these positions are valid (within the grid bounds and not blocked by a thorn). The value of `dp[r1][r2]` is updated based on the maximum cherries collected from the previous steps (up, left, up-left), plus the cherries picked up at the current positions. If both people are at the same location, the cherry is only counted once. The final result is stored in `dp[n-1][n-1]` after `2n-2` steps.

Step-by-Step Algorithm

Step 1: Initialize a 2D DP table `dp` of size n x n, where `dp[i][j]` represents the maximum number of cherries that can be collected when the first person is at row `i` and the second person is at row `j` after `k` steps.
Step 2: Set the base case: `dp[0][0] = grid[0][0]`. This means that initially, both people are at (0, 0) and have collected the cherry (if any) at that location.
Step 3: Iterate through all possible values of `k` from 1 to `2 * n - 1`. This represents the number of steps taken by both people.
Step 4: For each value of `k`, iterate through all possible row positions `r1` and `r2` for the two people.
Step 5: Calculate the corresponding column positions `c1` and `c2` based on the equations `c1 = k - r1` and `c2 = k - r2`.
Step 6: Check if the positions (r1, c1) and (r2, c2) are valid: within the grid bounds, not blocked by a thorn (-1).
Step 7: If the positions are valid, calculate the maximum number of cherries collected from the previous steps by considering all possible combinations of previous row positions: `dp[r1][r2]`, `dp[r1 - 1][r2]`, `dp[r1][r2 - 1]`, and `dp[r1 - 1][r2 - 1]`. The maximum of these becomes `prev_cherries`.
Step 8: Add the cherries picked up at the current positions (r1, c1) and (r2, c2) to `prev_cherries`. If `r1 == r2`, only add the cherry once; otherwise, add both.
Step 9: Update `dp_next[r1][r2]` with the calculated value ( `prev_cherries` + cherries at current position ).
Step 10: After processing all possible row positions for the current value of `k`, update the `dp` table with the `dp_next` table.
Step 11: Finally, return `max(0, dp[n - 1][n - 1])`. This returns the maximum number of cherries collected, or 0 if no valid path exists.

Key Insights

Insight 1: Two paths can be considered as two people walking from (0,0) at the same time. This is crucial because we need to account for picking the same cherry twice if we simply do two independent pathfinding attempts.
Insight 2: Dynamic programming is suitable because the optimal solution depends on the optimal solutions of subproblems (i.e., the maximum cherries collected up to a certain point).
Insight 3: The problem can be simplified by considering two people moving from (0,0) to (n-1, n-1) simultaneously, as the time taken for the first person to go from (0,0) to (n-1, n-1) and the second person from (n-1, n-1) to (0,0) is equivalent to them both going from (0,0) to (n-1,n-1) since they are simply the reverse path.

Complexity Analysis

Time Complexity: O(n^3)

Space Complexity: O(n^2)

Topics

This problem involves: Array, Dynamic Programming, Matrix.

Companies

Asked at: Akuna Capital, Atlassian, Cisco, Flipkart, J.P. Morgan, Snowflake, Zomato.

Cherry Pickup | LeetCode 741

Hard

Array Dynamic Programming Matrix

Time: O(n^3)Space: O(n^2)

Solution Code

Available in:

class Solution {
    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = -1;
            }
        }
        dp[0][0] = grid[0][0];

        for (int k = 1; k < 2 * n - 1; k++) {
            int[][] dp_next = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dp_next[i][j] = -1;
                }
            }
            for (int r1 = 0; r1 < n; r1++) {
                for (int r2 = 0; r2 < n; r2++) {
                    int c1 = k - r1;
                    int c2 = k - r2;

                    if (!(0 <= c1 && c1 < n && 0 <= c2 && c2 < n && grid[r1][c1] != -1 && grid[r2][c2] != -1)) {
                        continue;
                    }

                    int prev_cherries = dp[r1][r2];
                    if (r1 > 0) {
                        prev_cherries = Math.max(prev_cherries, dp[r1 - 1][r2]);
                    }
                    if (r2 > 0) {
                        prev_cherries = Math.max(prev_cherries, dp[r1][r2 - 1]);
                    }
                    if (r1 > 0 && r2 > 0) {
                        prev_cherries = Math.max(prev_cherries, dp[r1 - 1][r2 - 1]);
                    }

                    if (prev_cherries == -1) {
                        continue;
                    }

                    int cherries_at_k = grid[r1][c1];
                    if (r1 != r2) {
                        cherries_at_k += grid[r2][c2];
                    }
                    
                    dp_next[r1][r2] = prev_cherries + cherries_at_k;
                }
            }
            
            dp = dp_next;
        }
        
        return Math.max(0, dp[n - 1][n - 1]);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 741: Cherry Pickup - Detailed explanation and solution approaches.

Topics

Array Dynamic Programming Matrix

Companies

Akuna CapitalAtlassianCiscoFlipkartJ.P. MorganSnowflakeZomato

Stats

Difficulty:Hard

Languages:4

Companies:7

Problem #:741

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

11 steps

1
Step 1: Initialize a 2D DP table `dp` of size n x n, where `dp[i][j]` represents the maximum number of cherries that can be collected when the first person is at row `i` and the second person is at row `j` after `k` steps.
2
Step 2: Set the base case: `dp[0][0] = grid[0][0]`. This means that initially, both people are at (0, 0) and have collected the cherry (if any) at that location.
3
Step 3: Iterate through all possible values of `k` from 1 to `2 * n - 1`. This represents the number of steps taken by both people.
4
Step 4: For each value of `k`, iterate through all possible row positions `r1` and `r2` for the two people.
5
Step 5: Calculate the corresponding column positions `c1` and `c2` based on the equations `c1 = k - r1` and `c2 = k - r2`.
6
Step 6: Check if the positions (r1, c1) and (r2, c2) are valid: within the grid bounds, not blocked by a thorn (-1).
7
Step 7: If the positions are valid, calculate the maximum number of cherries collected from the previous steps by considering all possible combinations of previous row positions: `dp[r1][r2]`, `dp[r1 - 1][r2]`, `dp[r1][r2 - 1]`, and `dp[r1 - 1][r2 - 1]`. The maximum of these becomes `prev_cherries`.
8
Step 8: Add the cherries picked up at the current positions (r1, c1) and (r2, c2) to `prev_cherries`. If `r1 == r2`, only add the cherry once; otherwise, add both.
9
Step 9: Update `dp_next[r1][r2]` with the calculated value ( `prev_cherries` + cherries at current position ).
10
Step 10: After processing all possible row positions for the current value of `k`, update the `dp` table with the `dp_next` table.
11
Step 11: Finally, return `max(0, dp[n - 1][n - 1])`. This returns the maximum number of cherries collected, or 0 if no valid path exists.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n^3)

💾

Space Complexity

O(n^2)

📚 Quadratic space - Uses lots of memory!

📝

Why?

The outer loop iterates `2n - 1` times. The nested loops iterate `n` times each. Inside the inner loops, we perform constant time operations to update the DP table. This leads to O(n * n * n) = O(n^3) time complexity. The DP table `dp` has a size of `n x n`, resulting in O(n^2) space complexity.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Recursion with Memoization

A recursive solution with memoization could be used, where the recursive function explores all possible paths and the memoization table stores the results of already computed subproblems. This helps avoid recomputation.

Time: O(n^3)Space: O(n^3)

Trade-offs: While conceptually simpler to understand initially, recursion with memoization might have a higher space complexity due to the call stack and the memoization table, which needs to store the state (r1, c1, r2, c2) or (r1, r2, k).

✨

Key Insights

1Insight 1: Two paths can be considered as two people walking from (0,0) at the same time. This is crucial because we need to account for picking the same cherry twice if we simply do two independent pathfinding attempts.
2Insight 2: Dynamic programming is suitable because the optimal solution depends on the optimal solutions of subproblems (i.e., the maximum cherries collected up to a certain point).
3Insight 3: The problem can be simplified by considering two people moving from (0,0) to (n-1, n-1) simultaneously, as the time taken for the first person to go from (0,0) to (n-1, n-1) and the second person from (n-1, n-1) to (0,0) is equivalent to them both going from (0,0) to (n-1,n-1) since they are simply the reverse path.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Edge Cases

Edge case 1: If there is no valid path from (0, 0) to (n - 1, n - 1), the `dp` table will remain filled with -1, and the code correctly returns 0 as the maximum number of cherries.
Edge case 2: The grid contains only thorns (-1) except for the starting and ending points. The algorithm will correctly identify that no cherries can be collected and return 0.
Edge case 3: The grid is a 1x1 grid. The algorithm handles this correctly by returning the value of grid[0][0] directly.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Treating the problem as two independent pathfinding problems without accounting for the fact that picking up a cherry on the first path affects the second path. This can lead to double-counting the cherries.

✗Common mistake 2: Not properly handling the case when both people are at the same location (r1 == r2). In this case, the cherry should only be counted once.

✗Common mistake 3: Forgetting to handle the case where there is no valid path, and returning a negative value instead of 0.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Path planning for multiple robots in a warehouse, where each robot needs to collect items while avoiding obstacles. The goal is to maximize the number of items collected by both robots.

🏦Real-world scenario 2: Resource allocation in a network, where two agents need to access shared resources with limited capacity. The objective is to maximize the utilization of resources by both agents while avoiding conflicts.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Hard problems often combine multiple techniques. Break the problem into sub-problems.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 22, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

Should I use top-down (memoization) or bottom-up (tabulation)?

Start with top-down (recursion + memoization) as it directly maps to the recursive thinking and handles only needed subproblems. Convert to bottom-up for better space efficiency and to avoid stack overflow. Bottom-up is often faster due to no recursion overhead.

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Cherry Pickup"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?