LeetCode 3466 - Maximum Coin Collection

LeetCode Problem 3466

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem describes Mario driving along a two-lane freeway with coins (or tolls) on each mile. The arrays lane1 and lane2 represent the coin values at each mile for each lane. Positive numbers mean Mario collects coins, negative numbers mean Mario loses coins. Mario always starts in lane 1 but can switch lanes up to two times anywhere along the path, including immediately at the start or just before exiting. He must travel at least one mile, and we are asked to find the maximum number of coins he can collect given the lane switch constraints.

The input arrays can be as long as 10^5 elements, and coin values can range from -10^9 to 10^9, meaning any solution must be linear or near-linear in time. A naive approach that tries every possible combination of lane switches would be too slow.

Key edge cases include single-mile freeways, all negative coin values, and optimal strategies where Mario switches lanes immediately or multiple times within a very short freeway segment.

Approaches

A brute-force approach would try all possible combinations of lane switches and starting/ending points. This would involve iterating over all subsequences of lane1 and lane2 and considering 0, 1, or 2 lane switches at every possible mile. While this approach is correct, its time complexity is O(n^3) or worse, which is infeasible for n = 10^5.

The key insight for a better solution is that Mario's path can be decomposed into at most three contiguous segments due to the 2-switch limit: he can travel in lane1, switch to lane2, and then optionally switch back to lane1. Because of this structure, we can precompute the maximum subarray sums for each lane using a variant of Kadane's algorithm. Once we have these sums, we can efficiently compute the best combination of up to three segments, accounting for 0, 1, or 2 lane switches.

By leveraging prefix sums or Kadane-style scanning, we can reduce the problem to linear time, O(n), and constant space per lane segment.

Algorithm Walkthrough

1. Compute the maximum subarray sum for each lane individually. This handles the scenario where Mario never switches lanes (0 switches). This is a straightforward application of Kadane's algorithm.
2. Compute the maximum subarray sum with exactly one lane switch. To do this, iterate through each possible mile to switch lanes. At each mile i, consider switching from lane1 to lane2 or from lane2 to lane1. Track the maximum prefix sum in the first lane and combine it with the maximum suffix sum in the second lane to find the optimal one-switch path.
3. Compute the maximum subarray sum with exactly two lane switches. This involves choosing two switch points: the first from lane1 to lane2 and the second back to lane1. We can precompute prefix sums for lane1 and suffix sums for lane1 to efficiently combine them with the middle segment in lane2.
4. Track the global maximum across 0, 1, and 2 switch scenarios. This gives the answer.

Why it works: The invariant is that any valid path with at most two switches can be represented as up to three contiguous segments, where the first and last segments are in lane1 and the middle segment (if present) is in lane2. By precomputing maximum subarrays for each lane, we efficiently find the optimal segments without trying every combination explicitly.

Python Solution

from typing import List

class Solution:
    def maxCoins(self, lane1: List[int], lane2: List[int]) -> int:
        n = len(lane1)
        
        # Helper to compute max subarray sum for a single lane
        def max_subarray(arr: List[int]) -> List[int]:
            max_end = arr[0]
            max_so_far = arr[0]
            max_sums = [arr[0]]
            for x in arr[1:]:
                max_end = max(x, max_end + x)
                max_so_far = max(max_so_far, max_end)
                max_sums.append(max_so_far)
            return max_sums
        
        # Max subarray sums from start
        max1_prefix = max_subarray(lane1)
        max2_prefix = max_subarray(lane2)
        
        # Max subarray sums from end (for suffix combination)
        max1_suffix = max_subarray(lane1[::-1])[::-1]
        max2_suffix = max_subarray(lane2[::-1])[::-1]
        
        # Case 0: no switches
        max_coins = max(max1_prefix[-1], max2_prefix[-1])
        
        # Case 1: one switch
        for i in range(n - 1):
            max_coins = max(max_coins, max1_prefix[i] + max2_suffix[i + 1])
            max_coins = max(max_coins, max2_prefix[i] + max1_suffix[i + 1])
        
        # Case 2: two switches
        max1_prefix_only = [0]*n
        max_end = lane1[0]
        max1_prefix_only[0] = max_end
        for i in range(1, n):
            max_end = max(lane1[i], max_end + lane1[i])
            max1_prefix_only[i] = max(max1_prefix_only[i-1], max_end)
        
        max1_suffix_only = [0]*n
        max_end = lane1[-1]
        max1_suffix_only[-1] = max_end
        for i in range(n-2, -1, -1):
            max_end = max(lane1[i], max_end + lane1[i])
            max1_suffix_only[i] = max(max1_suffix_only[i+1], max_end)
        
        for i in range(n - 2):
            max_coins = max(max_coins, max1_prefix_only[i] + max2_prefix[i + 1] + max1_suffix_only[i + 2])
        
        return max_coins

Implementation Explanation: First, we compute maximum subarrays for both lanes from start to end and end to start. For zero switches, we take the maximum of single-lane sums. For one switch, we combine prefix from the first lane with suffix from the second. For two switches, we combine three segments: prefix in lane1, middle segment in lane2, and suffix in lane1. The code carefully avoids index overflow and ensures each segment is at least one mile.

Go Solution

func maxCoins(lane1 []int, lane2 []int) int64 {
    n := len(lane1)
    
    maxSubarray := func(arr []int) []int64 {
        res := make([]int64, n)
        maxEnd := int64(arr[0])
        maxSoFar := int64(arr[0])
        res[0] = maxSoFar
        for i := 1; i < n; i++ {
            val := int64(arr[i])
            if maxEnd+val > val {
                maxEnd += val
            } else {
                maxEnd = val
            }
            if maxEnd > maxSoFar {
                maxSoFar = maxEnd
            }
            res[i] = maxSoFar
        }
        return res
    }
    
    max1Prefix := maxSubarray(lane1)
    max2Prefix := maxSubarray(lane2)
    
    reverse := func(arr []int) []int64 {
        res := make([]int64, n)
        for i := 0; i < n; i++ {
            res[i] = int64(arr[n-1-i])
        }
        return res
    }
    
    max1Suffix := maxSubarray(reverse(lane1))
    for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
        max1Suffix[i], max1Suffix[j] = max1Suffix[j], max1Suffix[i]
    }
    max2Suffix := maxSubarray(reverse(lane2))
    for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
        max2Suffix[i], max2Suffix[j] = max2Suffix[j], max2Suffix[i]
    }
    
    maxCoins := max(max1Prefix[n-1], max2Prefix[n-1])
    
    for i := 0; i < n-1; i++ {
        maxCoins = maxInt64(maxCoins, max1Prefix[i]+max2Suffix[i+1])
        maxCoins = maxInt64(maxCoins, max2Prefix[i]+max1Suffix[i+1])
    }
    
    // Two switches
    max1PrefixOnly := make([]int64, n)
    maxEnd := int64(lane1[0])
    max1PrefixOnly[0] = maxEnd
    for i := 1; i < n; i++ {
        val := int64(lane1[i])
        if maxEnd+val > val {
            maxEnd += val
        } else {
            maxEnd = val
        }
        if maxEnd > max1PrefixOnly[i-