Put Marbles in Bags — Hard Problem & Solution

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 <= 1000
• 1 <= weights[i] <= 10^4

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

1. Build the n - 1 adjacent pair sums.
2. Sort them.
3. The minimum score uses the k - 1 smallest; the maximum uses the k - 1 largest.
4. 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 == 1 means 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 - 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Count Ways to Make Array With Product Hard
• The Number of Good Subsets Hard
• Number of Ways to Reorder Array to Get Same BST Hard
• Make Array Strictly Increasing Hard
• Odd Even Jump Hard
• Maximum Number of Events That Can Be Attended II Hard