Maximum Coins From K Consecutive Bags
Asked at Amazon
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | MEDIUM | View all Amazon questions → |
How to Think About It
Sort bags by their positions to ensure consecutive selection along the number line.
Compute prefix sums so that any window sum can be retrieved in O(1).
Slide a window of size k over sorted bags and track the maximum sum.
Consider whether "consecutive" means adjacent in sorted order or by position — clarify with interviewer.
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.
What Trips People Up in Real Interviews
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.
Solution Code
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_sumFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.