LeetCode 3466 - Maximum Coin Collection
We are given two arrays, lane1 and lane2, of equal length. Each index represents a mile on a freeway, and the value at that index represents how many coins Mario gains or loses if he drives through that mile in that lane. A positive value means Mario gains coins.
Difficulty: š” Medium
Topics: Array, Dynamic Programming
Solution
Problem Understanding
We are given two arrays, lane1 and lane2, of equal length. Each index represents a mile on a freeway, and the value at that index represents how many coins Mario gains or loses if he drives through that mile in that lane.
A positive value means Mario gains coins. A negative value means he pays a toll and loses coins.
Mario may choose any starting mile and any ending mile, as long as he travels at least one mile. The important restriction is that he always enters the freeway on lane 1, but he may switch lanes at most two times during the trip.
Because lane switches can happen immediately upon entering, Mario is allowed to start driving on lane 2 by using one switch at the beginning. Similarly, because a switch can happen immediately before exiting, some switch patterns may contain empty segments.
The goal is to find the maximum total number of coins Mario can collect.
The constraints are large:
ncan be as large as100000- Coin values can be as large as
10^9in magnitude
These constraints immediately rule out any solution that examines all possible start positions, end positions, and switching patterns explicitly. We need a linear-time dynamic programming solution.
Several edge cases are important:
- All values may be negative, meaning the answer is the least negative valid route.
- The optimal route may start in the middle of the freeway.
- The optimal route may immediately switch to lane 2.
- The optimal route may never switch lanes.
- The optimal route may use exactly two switches.
- The array length may be
1, meaning Mario must choose exactly one mile.
Approaches
Brute Force
A brute-force solution would enumerate every possible trip.
We could choose every starting mile, every ending mile, and every valid switching pattern that uses at most two lane changes. For each possibility, we would compute the resulting coin total and keep the maximum.
This approach is correct because it explicitly evaluates every legal route Mario can take.
The problem is the number of possibilities. There are O(n^2) start/end intervals alone. For every interval, we would also need to consider different switching positions. Since n can be 100000, this becomes completely infeasible.
Key Observation
The most important observation is that with at most two switches, there are only three meaningful states Mario can be in while processing the freeway from left to right:
- Currently in lane 1 with zero switches used.
- Currently in lane 2 with one switch used.
- Currently in lane 1 with two switches used.
These states correspond to the only possible lane sequences:
- Lane1
- Lane1 ā Lane2
- Lane1 ā Lane2 ā Lane1
Because immediate switching is allowed, the second state also naturally handles routes that start directly in lane 2.
Instead of considering all intervals, we can compute the best route ending at each position for each state. This transforms the problem into a dynamic programming problem similar to Kadane's maximum subarray algorithm.
At every mile, we either:
- Extend a previous route.
- Start a new route.
- Perform a lane switch and transition to a different state.
This gives a linear-time solution.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(nĀ³) or worse | O(1) | Enumerates intervals and switch positions |
| Optimal DP | O(n) | O(1) | Tracks best route ending at each mile for each switch state |
Algorithm Walkthrough
We define three DP states.
dp0= maximum coins for a route ending at the current mile while staying in lane 1 and using zero switches.dp1= maximum coins for a route ending at the current mile while being in lane 2 after using one switch.dp2= maximum coins for a route ending at the current mile while being in lane 1 after using two switches.
For mile i, let:
a = lane1[i]b = lane2[i]
Step 1: Update the zero-switch state
A route ending in lane 1 with zero switches can either:
- Start at this mile.
- Extend a previous zero-switch route.
So:
$dp0'=\max(0,dp0)+a$
The 0 represents starting a new route immediately before this mile.
Step 2: Update the one-switch state
A route ending in lane 2 can come from:
- Starting directly in lane 2 via an immediate switch.
- Extending a previous lane-2 route.
- Switching from the zero-switch lane-1 state.
Therefore:
$dp1'=\max(0,dp0,dp1)+b$
Step 3: Update the two-switch state
A route ending in lane 1 after two switches can come from:
- Extending a previous two-switch route.
- Switching from the one-switch lane-2 state.
Therefore:
$dp2'=\max(dp1,dp2)+a$
Step 4: Replace old states
After computing the new values, assign them back to dp0, dp1, and dp2.
Step 5: Update the answer
The best route seen so far may end in any state.
We continuously update:
answer = max(answer, dp0, dp1, dp2)
Step 6: Process all miles
Repeat the transitions for every index from left to right.
Why it works
Each state stores the best possible route ending at the current mile under a specific switching pattern. Every legal route with at most two switches must belong to exactly one of these three patterns:
- Lane1
- Lane1 ā Lane2
- Lane1 ā Lane2 ā Lane1
The transitions consider every valid way such a route can be extended or started. Since we always keep the maximum value for each state, the DP invariant is maintained. By the time we finish processing the array, the global maximum among all states is the optimal answer.
Python Solution
from typing import List
class Solution:
def maxCoins(self, lane1: List[int], lane2: List[int]) -> int:
n = len(lane1)
dp0 = lane1[0]
dp1 = lane2[0]
dp2 = float("-inf")
answer = max(dp0, dp1)
for i in range(1, n):
a = lane1[i]
b = lane2[i]
new_dp0 = max(0, dp0) + a
new_dp1 = max(0, dp0, dp1) + b
new_dp2 = max(dp1, dp2) + a
dp0 = new_dp0
dp1 = new_dp1
dp2 = new_dp2
answer = max(answer, dp0, dp1, dp2)
return answer
The implementation uses three variables instead of a full DP table because each state depends only on the previous mile.
dp0 tracks routes that never switched lanes.
dp1 tracks routes currently in lane 2 after one switch.
dp2 tracks routes currently back in lane 1 after two switches.
The expression max(0, ...) is the same idea used in Kadane's algorithm. It allows us to discard a bad prefix and start a new route at the current mile.
The answer is updated after every iteration because the optimal route may end anywhere.
Go Solution
func maxCoins(lane1 []int, lane2 []int) int64 {
n := len(lane1)
const negInf int64 = -1 << 60
dp0 := int64(lane1[0])
dp1 := int64(lane2[0])
dp2 := negInf
ans := max3(dp0, dp1, dp2)
for i := 1; i < n; i++ {
a := int64(lane1[i])
b := int64(lane2[i])
newDp0 := max64(0, dp0) + a
newDp1 := max64Three(0, dp0, dp1) + b
newDp2 := max64(dp1, dp2) + a
dp0 = newDp0
dp1 = newDp1
dp2 = newDp2
ans = max64(ans, max3(dp0, dp1, dp2))
}
return ans
}
func max64(a, b int64) int64 {
if a > b {
return a
}
return b
}
func max64Three(a, b, c int64) int64 {
return max64(a, max64(b, c))
}
func max3(a, b, c int64) int64 {
return max64(a, max64(b, c))
}
The Go version uses int64 because the coin values can reach 10^9 and the array length can reach 10^5. The total sum can therefore exceed the range of a 32-bit integer.
Unlike Python, Go does not have built-in infinity values for integers, so a large negative sentinel value is used for the initial dp2.
Worked Examples
Example 1
lane1 = [1, -2, -10, 3]
lane2 = [-5, 10, 0, 1]
Initial state:
| Mile | dp0 | dp1 | dp2 | Answer |
|---|---|---|---|---|
| 0 | 1 | -5 | -inf | 1 |
Processing mile 1:
| Value | Result |
|---|---|
| new_dp0 | max(0,1)-2 = -1 |
| new_dp1 | max(0,1,-5)+10 = 11 |
| new_dp2 | max(-5,-inf)-2 = -7 |
| Mile | dp0 | dp1 | dp2 | Answer |
|---|---|---|---|---|
| 1 | -1 | 11 | -7 | 11 |
Processing mile 2:
| Value | Result |
|---|---|
| new_dp0 | max(0,-1)-10 = -10 |
| new_dp1 | max(0,-1,11)+0 = 11 |
| new_dp2 | max(11,-7)-10 = 1 |
| Mile | dp0 | dp1 | dp2 | Answer |
|---|---|---|---|---|
| 2 | -10 | 11 | 1 | 11 |
Processing mile 3:
| Value | Result |
|---|---|
| new_dp0 | max(0,-10)+3 = 3 |
| new_dp1 | max(0,-10,11)+1 = 12 |
| new_dp2 | max(11,1)+3 = 14 |
Final answer:
14
Example 2
lane1 = [1,-1,-1,-1]
lane2 = [0,3,4,-5]
| Mile | dp0 | dp1 | dp2 | Best |
|---|---|---|---|---|
| 0 | 1 | 0 | -inf | 1 |
| 1 | 0 | 4 | -1 | 4 |
| 2 | -1 | 8 | 3 | 8 |
| 3 | -1 | 3 | 7 | 8 |
Final answer:
8
Example 3
lane1 = [-5,-4,-3]
lane2 = [-1,2,3]
| Mile | dp0 | dp1 | dp2 | Best |
|---|---|---|---|---|
| 0 | -5 | -1 | -inf | -1 |
| 1 | -4 | 2 | -5 | 2 |
| 2 | -3 | 5 | -1 | 5 |
Final answer:
5
Example 4
lane1 = [-3,-3,-3]
lane2 = [9,-2,4]
| Mile | dp0 | dp1 | dp2 | Best |
|---|---|---|---|---|
| 0 | -3 | 9 | -inf | 9 |
| 1 | -3 | 7 | 6 | 9 |
| 2 | -3 | 11 | 10 | 11 |
Final answer:
11
Example 5
lane1 = [-10]
lane2 = [-2]
Initial state:
| dp0 | dp1 | dp2 |
|---|---|---|
| -10 | -2 | -inf |
Answer:
-2
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each mile is processed exactly once |
| Space | O(1) | Only three DP states are stored |
The algorithm performs a constant amount of work for every index in the arrays. No auxiliary data structures proportional to n are required because every transition depends only on the previous states.
Test Cases
sol = Solution()
assert sol.maxCoins([1, -2, -10, 3], [-5, 10, 0, 1]) == 14 # two switches
assert sol.maxCoins([1, -1, -1, -1], [0, 3, 4, -5]) == 8 # exit early
assert sol.maxCoins([-5, -4, -3], [-1, 2, 3]) == 5 # immediate switch
assert sol.maxCoins([-3, -3, -3], [9, -2, 4]) == 11 # stay on lane2
assert sol.maxCoins([-10], [-2]) == -2 # single mile
assert sol.maxCoins([5], [1]) == 5 # single positive lane1
assert sol.maxCoins([-1], [-5]) == -1 # choose less negative
assert sol.maxCoins([1, 2, 3], [-10, -10, -10]) == 6 # never switch
assert sol.maxCoins([-10, -10, -10], [1, 2, 3]) == 6 # immediate switch
assert sol.maxCoins([10, -100, 10], [0, 50, 0]) == 60 # one switch beneficial
assert sol.maxCoins(
[1, -100, -100, 10],
[0, 50, 50, 0]
) == 111 # uses two switches
assert sol.maxCoins(
[-100, 100],
[50, -100]
) == 100 # start later
assert sol.maxCoins(
[0, 0, 0],
[0, 0, 0]
) == 0 # all zeros
Test Summary
| Test | Why |
|---|---|
| Example 1 | Validates two-switch path |
| Example 2 | Validates early exit |
| Example 3 | Validates immediate switch on entry |
| Example 4 | Validates staying entirely on lane2 |
| Example 5 | Validates single-element arrays |
[5] vs [1] |
Single positive value |
[-1] vs [-5] |
Single negative value |
| Positive lane1 only | No switch needed |
| Positive lane2 only | Immediate switch optimal |
| Large negative middle | One-switch transition |
| Two profitable lane2 miles | Two-switch pattern |
| Start later | Route need not begin at index 0 |
| All zeros | Neutral values |
Edge Cases
One important edge case is when every value in both lanes is negative. A naive maximum-subarray implementation may incorrectly return 0 by allowing an empty route. The problem requires Mario to travel at least one mile, so the answer must be one of the actual lane values or combinations of them. The DP initialization uses real array values rather than starting from zero, ensuring that at least one mile is always included.
Another important edge case is when the optimal route starts directly in lane 2. Since Mario officially enters on lane 1, it is easy to incorrectly forbid such routes. The statement explicitly allows an immediate switch upon entering. The dp1 state is initialized with lane2[0], and the transition max(0, dp0, dp1) + lane2[i] allows a new lane-2 route to begin at any position.
A third important edge case is when the array length is 1. There is no opportunity to build a longer route, and the answer is simply the better of the two lanes at that single mile. The initialization handles this naturally because the loop never runs and the maximum of the initial states is returned.
A fourth edge case is when the best route uses exactly two switches. Many implementations accidentally handle only one switch because they track only the current lane. The dedicated dp2 state explicitly represents routes that have already performed the second switch and returned to lane 1, guaranteeing these routes are considered correctly.