Maximum Coins From K Consecutive Bags
Medium · Sliding Window · Array · Sliding Window · Sorting · Prefix Sum · Binary Search · Greedy
Problem
Bags sit at every integer position on a number line. Some runs of them hold coins: each entry coins[i] = [l, r, c] says every bag from position l to position r (inclusive) holds c coins. The runs never overlap, and they are given in no particular order. Every bag outside a run is empty.
Pick k consecutive bags — positions x, x+1, …, x+k-1 for any integer x — and collect all their coins. Return the most coins you can collect.
Examples
Input: coins = [[8,10,1],[1,3,2],[5,6,4]], k = 4 Output: 10
Take bags 3 to 6: 2 + 0 + 4 + 4 = 10. Bag 4 is empty, but the two 4-coin bags make up for it.
Input: coins = [[1,10,3]], k = 2 Output: 6
Any two bags inside the run give 3 + 3.
Constraints
- 1 <= len(coins) <= 10^5
- 1 <= k <= 10^9
- coins[i] = [l, r, c] with 1 <= l <= r <= 10^9 and 1 <= c <= 1000
- No two runs overlap
Approaches
- Try every window position — time O(span · k), space O(span)
Follow-up
Could you answer many queries with different k on the same runs? (Prefix sums over run boundaries plus a binary search per window edge.)
Related problems
Start free on Cariara · Coding problems · System design studio
