Put Marbles in Bags

Hard
967.

Put Marbles in Bags

Put Marbles in Bags is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} weights
 * @param {number} k
 * @return {number}
 */
var putMarbles = function(weights, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Put Marbles in Bags

  1. Hint 1

    Write out the score of a split and see which weights are counted twice.

  2. Hint 2

    The first and last marbles are always counted, whatever the split.

  3. Hint 3

    Each cut between i and i + 1 adds exactly weights[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

  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

Java

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