Put Marbles in Bags — Solution in Python, Java & C++
Put Marbles in Bags solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on arrays and sorting.
Put Marbles in Bags is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Greedy, Heap
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Marbles of the given weights sit in a row. Split them into k non-empty consecutive groups, with no marble left over.
The cost of a group running from index i to index j is weights[i] + weights[j], and the score of a split is the sum of its groups' costs. Return the difference between the maximum and minimum possible scores.
Example 1
Input: weights = [1,3,5,1], k = 2
Output: 4
Explanation: The best split scores 10 and the worst 6.
Example 2
Input: weights = [1,3], k = 2
Output: 0
Explanation: Only one split exists.
Example 3
Input: weights = [1,4,2,5,2], k = 3
Output: 3
Constraints
1 <= k <= weights.length <= 10001 <= weights[i] <= 10^4
Hints for Put Marbles in Bags
Hint 1
Write out the score of a split and see which weights are counted twice.
Hint 2
The first and last marbles are always counted, whatever the split.
Hint 3
Each cut between
iandi + 1adds exactlyweights[i] + weights[i + 1]to the score.
How to solve Put Marbles in Bags
A split into k groups makes k - 1 cuts, and a cut between positions i and i + 1 contributes exactly weights[i] + weights[i+1]. The two ends contribute the same amount to every split, so they cancel in the difference.
Approach
- Build the
n - 1adjacent pair sums. - Sort them.
- The minimum score uses the
k - 1smallest; the maximum uses thek - 1largest. - Return the difference of those two totals.
Why it works
Because every cut is independent — choosing one never restricts another — the extremes are reached simply by picking the k - 1 smallest or largest pair sums. The fixed weights[0] + weights[n-1] term appears in both scores and drops out, which is why the answer needs no reference to the ends at all.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
k == 1means no cuts, so the answer is 0.- The ends cancel; adding them is a common slip that leaves the answer unchanged only by luck.
- The cuts are chosen from the pair sums, not from the weights.
Reference solution
Python
from typing import List
def putMarbles(weights: List[int], k: int) -> int:
n = len(weights)
if k == 1 or n == 1:
return 0
pairs = sorted(weights[i] + weights[i + 1] for i in range(n - 1))
low = sum(pairs[: k - 1])
high = sum(pairs[-(k - 1):])
return high - lowJava
public static int putMarbles(int[] weights, int k) {
int n = weights.length;
if (k == 1 || n == 1) return 0;
int[] pairs = new int[n - 1];
for (int i = 0; i + 1 < n; i++) pairs[i] = weights[i] + weights[i + 1];
Arrays.sort(pairs);
long low = 0, high = 0;
for (int i = 0; i < k - 1; i++) {
low += pairs[i];
high += pairs[pairs.length - 1 - i];
}
return (int) (high - low);
}C++
int putMarbles(vector<int>& weights, int k) {
int n = (int) weights.size();
if (k == 1 || n == 1) return 0;
vector<int> pairs;
for (int i = 0; i + 1 < n; i++) pairs.push_back(weights[i] + weights[i + 1]);
sort(pairs.begin(), pairs.end());
long long low = 0, high = 0;
for (int i = 0; i < k - 1; i++) {
low += pairs[i];
high += pairs[(int) pairs.size() - 1 - i];
}
return (int) (high - low);
}JavaScript
var putMarbles = function(weights, k) {
var n = weights.length;
if (k === 1 || n === 1) return 0;
var pairs = [];
for (var i = 0; i + 1 < n; i++) pairs.push(weights[i] + weights[i + 1]);
pairs.sort(function(a, b) { return a - b; });
var low = 0, high = 0;
for (i = 0; i < k - 1; i++) {
low += pairs[i];
high += pairs[pairs.length - 1 - i];
}
return high - low;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms