Watch the video solution for Maximum Coin Collection , a medium level problem involving Array, Dynamic Programming. This walkthrough by Code-Yao has 449 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Mario drives on a two-lane freeway with coins every mile. You are given two integer arrays, lane1 and lane2, where the value at the ith index represents the number of coins he gains or loses in the ith mile in that lane.
i and lane1[i] > 0, Mario gains lane1[i] coins.i and lane1[i] < 0, Mario pays a toll and loses abs(lane1[i]) coins.lane2.Mario can enter the freeway anywhere and exit anytime after traveling at least one mile. Mario always enters the freeway on lane 1 but can switch lanes at most 2 times.
A lane switch is when Mario goes from lane 1 to lane 2 or vice versa.
Return the maximum number of coins Mario can earn after performing at most 2 lane switches.
Note: Mario can switch lanes immediately upon entering or just before exiting the freeway.
Example 1:
Input: lane1 = [1,-2,-10,3], lane2 = [-5,10,0,1]
Output: 14
Explanation:
Mario collects 1 + 10 + 0 + 3 = 14 coins.
Example 2:
Input: lane1 = [1,-1,-1,-1], lane2 = [0,3,4,-5]
Output: 8
Explanation:
He collects 1 + 3 + 4 = 8 coins.
Example 3:
Input: lane1 = [-5,-4,-3], lane2 = [-1,2,3]
Output: 5
Explanation:
He collects a total of 2 + 3 = 5 coins.
Example 4:
Input: lane1 = [-3,-3,-3], lane2 = [9,-2,4]
Output: 11
Explanation:
He collects a total of 9 + (-2) + 4 = 11 coins.
Example 5:
Input: lane1 = [-10], lane2 = [-2]
Output: -2
Explanation:
He collects a total of -2 coins.
Constraints:
1 <= lane1.length == lane2.length <= 105-109 <= lane1[i], lane2[i] <= 109Problem Overview: You are given an array of coins. Each position represents the number of coins you can collect from that index. The goal is to compute the maximum coins you can collect while respecting the problem’s selection constraints. A naive greedy pick fails because taking a large value early can block better future combinations.
Approach 1: Brute Force Recursion (Exponential Time, O(2^n) time, O(n) space)
The most direct idea is to explore every possible decision at each index. For each position i, you either collect the coins at that index or skip it. If you collect from i, the constraint prevents taking the immediate neighbor, so the next valid decision moves to i + 2. If you skip, move to i + 1. This creates a binary decision tree that evaluates every valid subset. The recursion depth is O(n), but the number of states grows exponentially, leading to O(2^n) time. This approach helps understand the structure of the problem but quickly becomes impractical for large inputs.
Approach 2: Memoized Search / Top-Down Dynamic Programming (O(n) time, O(n) space)
The recursive structure reveals overlapping subproblems. The maximum coins collectible starting from index i is independent of how you arrived there. Store results in a memo table dp[i] to avoid recomputation. Each state evaluates two choices: take the current coin (coins[i] + dp[i+2]) or skip it (dp[i+1]). Cache the maximum result for each index so every state is computed once. With memoization, the recursion collapses to O(n) time and O(n) space.
This technique is a classic pattern in dynamic programming problems over an array. The key insight is defining a state that represents the best answer from a given index onward and reusing it across recursive calls. The memoized DFS keeps the code clean while achieving optimal performance.
Recommended for interviews: Interviewers typically expect the dynamic programming formulation. Starting with brute force shows you understand the decision tree. Converting it to memoized search demonstrates recognition of overlapping subproblems and the ability to optimize recursion using DP. The top-down solution is both efficient and easy to explain during a whiteboard discussion.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursion | O(2^n) | O(n) | Conceptual understanding of the decision tree and valid combinations |
| Memoized Search (Top-Down DP) | O(n) | O(n) | General case and interview solution where overlapping subproblems exist |