Watch 4 video solutions for Maximum Coins From K Consecutive Bags, a medium level problem involving Array, Binary Search, Greedy. This walkthrough by Aryan Mittal has 4,849 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There are an infinite amount of bags on a number line, one bag for each coordinate. Some of these bags contain coins.
You are given a 2D array coins, where coins[i] = [li, ri, ci] denotes that every bag from li to ri contains ci coins.
The segments that coins contain are non-overlapping.
You are also given an integer k.
Return the maximum amount of coins you can obtain by collecting k consecutive bags.
Example 1:
Input: coins = [[8,10,1],[1,3,2],[5,6,4]], k = 4
Output: 10
Explanation:
Selecting bags at positions [3, 4, 5, 6] gives the maximum number of coins: 2 + 0 + 4 + 4 = 10.
Example 2:
Input: coins = [[1,10,3]], k = 2
Output: 6
Explanation:
Selecting bags at positions [1, 2] gives the maximum number of coins: 3 + 3 = 6.
Constraints:
1 <= coins.length <= 1051 <= k <= 109coins[i] == [li, ri, ci]1 <= li <= ri <= 1091 <= ci <= 1000Problem Overview: You are given ranges of bags where each bag in the range contains a certain number of coins. The task is to choose exactly k consecutive bag indices and collect the maximum total coins possible. Since ranges can overlap and bag indices can be large, the challenge is computing the maximum sum efficiently without iterating every bag index.
Approach 1: Brute Force Range Simulation (High Complexity)
The direct idea is to simulate the number of coins in every bag, then evaluate every window of length k. Build an array representing coins per bag by expanding each range and accumulating contributions. After that, iterate through all possible windows and track the maximum sum. This works conceptually but fails when bag indices are large because the array size becomes impractical. Time complexity is O(N * range + M) where M is the maximum bag index, and space complexity is O(M). This approach mainly helps understand the structure of the problem.
Approach 2: Prefix Sum on Compressed Coordinates (O(n log n))
Instead of expanding every bag index, compress the coordinates of all relevant boundaries. Convert ranges into events and compute coin contributions using a prefix sum. After building the cumulative coins for each compressed segment, evaluate the total coins inside any window of length k. This reduces memory usage dramatically because you only track meaningful breakpoints. Time complexity becomes O(n log n) due to sorting and coordinate compression, with O(n) extra space.
Approach 3: Sorting + Sliding Window on Intervals (Optimal)
The efficient solution works directly on the interval representation. First sort the coin ranges by starting index using standard sorting. Then treat the chosen segment [x, x + k - 1] as a window and compute how much each interval contributes based on overlap length. Use a sliding window with two pointers to maintain intervals intersecting the current window while adjusting contributions when the window shifts. Prefix sums or partial overlap calculations ensure each interval is processed once. Sorting dominates the runtime, giving O(n log n) time and O(n) space.
Recommended for interviews: Interviewers expect the interval-based sliding window solution. Starting with the brute force approach shows you understand the problem constraints, but recognizing that bag indices can be large leads naturally to sorting ranges and computing overlaps. Using sliding window with prefix-style accumulation demonstrates strong knowledge of interval processing and optimization techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Bag Simulation | O(N * range) | O(M) | Useful only for understanding the problem or when bag indices are very small |
| Coordinate Compression + Prefix Sum | O(n log n) | O(n) | When bag indices are large but the number of ranges is moderate |
| Sorting + Sliding Window on Intervals | O(n log n) | O(n) | Best general solution for interview settings and competitive programming |