MediumArrayBinary SearchGreedySliding WindowSortingPrefix SumUpdated Sep 2026

3413. Maximum Coins From K Consecutive Bags

Asked at Amazon

Difficulty

Medium

Time

O(n log n)

Space

O(n)

Pattern

Array

Companies

1

Problem

Bags sit on a number line, one bag at every integer position. Some positions hold coins. You are given a list coins, where each entry [li, ri, ci] means every bag from position li to position ri (inclusive) holds exactly ci coins. All the given ranges are non-overlapping, and positions outside them hold 0 coins.

You must pick exactly k consecutive bags — that is, a block of k neighbouring positions on the number line. Return the largest total number of coins any such block can give you.

Because positions can be as large as 10^9 and k can be huge, you cannot walk the number line bag by bag. Instead, think about where the best block of length k can start and end: the answer is decided by how much of each coin range falls inside the block.

Pick a block of k neighbouring bags

positionk = 41:22:23:24:05:46:47:08:19:110:1Each cell shows position:coins. The green block is the winning window.
The block [3,4,5,6] has length 4 and collects 2 + 0 + 4 + 4 = 10 coins, the best possible.

Constraints

  • ●1 <= coins.length <= 10^5
  • ●1 <= k <= 10^9
  • ●coins[i] == [li, ri, ci]
  • ●1 <= li <= ri <= 10^9
  • ●1 <= ci <= 1000
  • ●The given segments are non-overlapping

Examples

Example 1
Inputcoins = [[8,10,1],[1,3,2],[5,6,4]], k = 4
Output10
WhyThe block [3,4,5,6] covers position 3 (2 coins), position 4 (0 coins, since no range covers it), and positions 5 and 6 (4 coins each). Total = 2 + 0 + 4 + 4 = 10, which beats every other block of 4.
Example 2
Inputcoins = [[1,10,3]], k = 2
Output6
WhyEvery position from 1 to 10 holds 3 coins. Any block of 2 consecutive bags gives 3 + 3 = 6.

Asked At

1 companies
CompanyDifficulty
AmazonMediumView all Amazon questions →

How to Think About It

1

Sort bags by their positions to ensure consecutive selection along the number line.

2

Compute prefix sums so that any window sum can be retrieved in O(1).

3

Slide a window of size k over sorted bags and track the maximum sum.

4

Consider whether "consecutive" means adjacent in sorted order or by position — clarify with interviewer.

5

The optimal approach is O(n log n) for sorting plus O(n) for the prefix-sum sliding window.

Optimal Approach

Sort the bags by their positions. Compute a prefix sum array where prefix[i] is the sum of coins from bag 0 to bag i. Iterate through all possible windows of k consecutive bags starting at index i, computing the sum as prefix[i + k - 1] - prefix[i - 1] (with appropriate boundary checks). Track and return the maximum sum found. This runs in O(n log n) due to sorting, with O(n) for the sliding window scan.

Slide the window over range boundaries

sort ranges by libuild prefix sums of ci * lengthtry start = li and start = ri - k + 1score each window with prefix sumskeep the maxThe candidate starts are limited to range edges, so the scan stayslinear.window(start) = sum of ci * overlap([li,ri], [start, start+k-1])answer = max over all candidate starts
Only window starts near a range edge can change the total, so we test those starts and use prefix sums to score each one fast.
ComplexityTime O(n log n)Space O(n)Sorting the ranges costs O(n log n); the sweep over candidate window starts costs O(n) after that.

What Trips People Up in Real Interviews

1

Clarify whether bags must be consecutive in position or just any k bags.

2

Ask if positions are guaranteed unique or if multiple bags can share a position.

3

Mention prefix sums for O(1) window sum queries — don't recalculate sums each time.

4

Discuss edge cases: k equals 1, k equals n, or all bags at the same position.

5

If positions are large and sparse, consider coordinate compression or binary search on positions.

Solution Code

O(n log n) time
def max_coins(bags, k):
    bags.sort()
    n = len(bags)
    if k > n:
        return 0
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + bags[i][1]
    max_sum = 0
    for i in range(n - k + 1):
        current = prefix[i + k] - prefix[i]
        max_sum = max(max_sum, current)
    return max_sum

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Maximum Coins From K Consecutive Bags problem?

Given a list of bags, each containing a certain number of coins and occupying a position on a number line, select exactly k consecutive bags to maximize the total coins collected. The bags may not be evenly spaced, so you need to identify which k consecutive bags yield the highest sum. Use sorting and prefix sums to efficiently compute sliding window sums.

How do you solve Maximum Coins From K Consecutive Bags?

The optimal approach runs in O(n log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Maximum Coins From K Consecutive Bags?

Maximum Coins From K Consecutive Bags is asked at Amazon. It is a medium difficulty problem.

What are common mistakes on Maximum Coins From K Consecutive Bags?
  • Clarify whether bags must be consecutive in position or just any k bags.
  • Ask if positions are guaranteed unique or if multiple bags can share a position.
  • Mention prefix sums for O(1) window sum queries — don't recalculate sums each time.
  • Discuss edge cases: k equals 1, k equals n, or all bags at the same position.
  • If positions are large and sparse, consider coordinate compression or binary search on positions.