Skip to main content
Talentd

Maximum Coin Collection - Solution & Explanation

MediumPremiumFree on FleetCodeArrayDynamic Programming12 min readAsked at: Uber
Practice this problem

Problem Statement

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.

  • If Mario is in lane 1 at mile i and lane1[i] > 0, Mario gains lane1[i] coins.
  • If Mario is in lane 1 at mile i and lane1[i] < 0, Mario pays a toll and loses abs(lane1[i]) coins.
  • The same rules apply for 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 drives the first mile on lane 1.
  • He then changes to lane 2 and drives for two miles.
  • He changes back to lane 1 for the last mile.

Mario collects 1 + 10 + 0 + 3 = 14 coins.

Example 2:

Input: lane1 = [1,-1,-1,-1], lane2 = [0,3,4,-5]

Output: 8

Explanation:

  • Mario starts at mile 0 in lane 1 and drives one mile.
  • He then changes to lane 2 and drives for two more miles. He exits the freeway before mile 3.

He collects 1 + 3 + 4 = 8 coins.

Example 3:

Input: lane1 = [-5,-4,-3], lane2 = [-1,2,3]

Output: 5

Explanation:

  • Mario enters at mile 1 and immediately switches to lane 2. He stays here the entire way.

He collects a total of 2 + 3 = 5 coins.

Example 4:

Input: lane1 = [-3,-3,-3], lane2 = [9,-2,4]

Output: 11

Explanation:

  • Mario starts at the beginning of the freeway and immediately switches to lane 2. He stays here the whole way.

He collects a total of 9 + (-2) + 4 = 11 coins.

Example 5:

Input: lane1 = [-10], lane2 = [-2]

Output: -2

Explanation:

  • Since Mario must ride on the freeway for at least one mile, he rides just one mile in lane 2.

He collects a total of -2 coins.

 

Constraints:

  • 1 <= lane1.length == lane2.length <= 105
  • -109 <= lane1[i], lane2[i] <= 109

Approach Overview

Problem 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.

Solution

We design a function dfs(i, j, k), which represents the maximum number of coins Mario can collect starting from position i, currently on lane j, with k lane changes remaining. The answer is the maximum value of dfs(i, 0, 2) for all i.

The function dfs(i, j, k) is calculated as follows:

  • If i geq n, it means Mario has reached the end, return 0;
  • If no lane change is made, Mario can drive 1 mile, then exit, or continue driving, taking the maximum of the two, i.e., max(x, dfs(i + 1, j, k) + x);
  • If a lane change is possible, there are two choices: drive 1 mile and then change lanes, or change lanes directly, taking the maximum of these two cases, i.e., max(dfs(i + 1, j \oplus 1, k - 1) + x, dfs(i, j \oplus 1, k - 1)).
  • Where x represents the number of coins at the current position.

To avoid repeated calculations, we use memoized search to store the results that have already been computed.

Time complexity is O(n), and space complexity is O(n). Where n represents the length of the lanes.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force RecursionO(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

Video Solution

leetcode 3466 Maximum Coin Collection | DP, 2 versions, with comparison • Code-Yao • 462 views views

Frequently Asked Questions

Is Maximum Coin Collection easy or hard?
Maximum Coin Collection is typically classified as a Medium difficulty problem. The core challenge is recognizing the overlapping subproblems and converting a brute-force recursive search into a dynamic programming solution.
Maximum Coin Collection Python/Java solution
The standard implementation uses a memoized recursive function. Store computed results in a dp array and recursively evaluate take vs skip decisions. This pattern translates directly across Python, Java, C++, Go, and TypeScript with identical O(n) time complexity.
How to solve Maximum Coin Collection in O(n)?
Use a memoized DFS or top-down DP. Define a recursive function that returns the maximum coins from index i onward. Compute max(coins[i] + dfs(i+2), dfs(i+1)) and store the result in a memo array. Each state is solved once, giving linear O(n) time complexity.
Is Maximum Coin Collection asked at Google/Amazon/Meta?
Dynamic programming problems on arrays with take-or-skip decisions are common in interviews at companies like Amazon, Google, and Meta. Variants of this pattern frequently appear in coding rounds because they test recursion, DP state definition, and optimization skills.
What is the best approach for Maximum Coin Collection ?
The optimal approach is memoized search (top-down dynamic programming). Define dp[i] as the maximum coins you can collect starting from index i. At each step you choose between collecting the current coin and moving to i+2, or skipping it and moving to i+1. This reduces the complexity to O(n) time and O(n) space.
What data structure is used in Maximum Coin Collection ?
The solution primarily uses an array for the input and a memoization table (another array or hash map) to cache DP states. The recursion stack also acts as an implicit structure during the depth-first search.
What is the time complexity of Maximum Coin Collection ?
The optimal dynamic programming solution runs in O(n) time because each index state is computed once and cached in a memo table. The recursion checks two transitions per state, but memoization prevents repeated work. Space complexity is O(n) due to the DP cache and recursion stack.

Ready to solve this problem?

Practice Maximum Coin Collection with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays