The Put Marbles in Bags problem asks you to distribute marbles into k bags such that the cost (sum of first + last marble in each bag) is maximized or minimized. The difference between maximum and minimum cost is the answer. This hard coding problem has an elegant key insight: only the split points between bags matter. The array, sorting, heap, and greedy interview pattern is fully tested.
Uber, Microsoft, Meta, Amazon, TikTok, and Google ask this because the reduction — from "distribute into k bags" to "pick k-1 split points" — is non-obvious. Once you see it, sorting the pair sums at split points gives the answer in O(n log n).
Split-point reduction + sort. Key insight: the cost for any distribution equals marbles[0] + marbles[n-1] (always included) plus the sum of marbles[i] + marbles[i+1] for each chosen split between index i and i+1. There are n-1 possible split points; you choose k-1 of them. To maximize cost: pick largest k-1 pair sums. To minimize: pick smallest k-1 pair sums. Answer = sum of largest k-1 - sum of smallest k-1.
marbles=[1,3,5,1], k=2. Pair sums at splits: [1+3=4, 3+5=8, 5+1=6]. Base = 1+1=2. Choose 1 split (k-1=1). Max split: pick 8. Max cost = 2+8=10. Min split: pick 4. Min cost = 2+4=6. Answer = 10-6 = 4.
Put Marbles in Bags demonstrates a powerful reduction: "k groups" → "k-1 split choices." This reduction appears in many interval and partitioning problems. Once you identify the invariant (first+last are always included), the problem reduces to choosing from n-1 candidates. Sorting these candidates and summing the top/bottom k-1 gives the answer in O(n log n).
| Title | Difficulty | Topics | LeetCode |
|---|---|---|---|
| Maximum Performance of a Team | Hard | Solve | |
| Minimum Cost to Hire K Workers | Hard | Solve | |
| IPO | Hard | Solve | |
| Course Schedule III | Hard | Solve | |
| Maximum Subsequence Score | Medium | Solve |
