Put Marbles in Bags

How it works

Instead of sorting all adjacent pair sums, we can use two heaps to efficiently track just the k-1 largest and k-1 smallest values. A min-heap keeps the k-1 largest sums (evicting smaller ones), while a max-heap keeps the k-1 smallest sums (evicting larger ones). This is more efficient when k is small relative to n.

Steps

1. If k == 1, return 0.
2. Initialize a min-heap and a max-heap, both of size at most k-1.
3. For each adjacent pair sum weights[i] + weights[i+1]:
   • Add to the min-heap. If size exceeds k-1, remove the smallest.
   • Add to the max-heap. If size exceeds k-1, remove the largest.
4. Sum all elements in the min-heap for the max score.
5. Sum all elements in the max-heap for the min score.
6. Return maxScore - minScore.

Complexity

• Time complexity: O(n log k)
• Space complexity: O(k)

Where n is the number of marbles, and k is the number of bags.

Things to watch for

Misunderstanding the Score Contribution

Each bag's score is the sum of its first and last marble weights. A common mistake is thinking only endpoints matter globally. The key insight is that internal partition points contribute weights[i] + weights[i+1] to the total score, while the first and last marbles of the entire array always contribute and cancel out in the difference.

Off-by-One in Number of Splits

With k bags, we need exactly k-1 partition points (splits), not k. Selecting k splits creates k+1 bags. This off-by-one error leads to selecting too many or too few adjacent pair sums when computing max and min scores.

Not Handling k=1 Edge Case

When k=1, there are no partition choices since all marbles go into one bag. The max and min scores are identical, so the answer is 0. Forgetting this case and attempting to select 0 elements from the splits array causes errors.

Integer Overflow in Sum Calculations

Adjacent pair sums can be up to 2 * 10^9, and summing k-1 of them can overflow 32-bit integers. Using 64-bit integers (long in Java, int64 in Go) prevents overflow issues when computing max and min scores.

from typing import List
import heapq

class Solution:
    def putMarbles(self, weights: List[int], k: int) -> int:
        if k == 1:
            return 0

        min_heap = []
        max_heap = []

        for i in range(len(weights) - 1):
            split = weights[i] + weights[i + 1]

            if len(min_heap) < k - 1:
                heapq.heappush(min_heap, split)
            else:
                heapq.heappushpop(min_heap, split)

            if len(max_heap) < k - 1:
                heapq.heappush(max_heap, -split)
            else:
                heapq.heappushpop(max_heap, -split)

        max_score = sum(min_heap)
        min_score = -sum(max_heap)
        return max_score - min_score

class Solution {
public:
    long long putMarbles(vector<int>& weights, int k) {
        if (k == 1) return 0LL;

        priority_queue<int, vector<int>, greater<int>> minHeap;
        priority_queue<int> maxHeap;

        for (int i = 0; i < weights.size() - 1; ++i) {
            int split = weights[i] + weights[i + 1];

            if ((int)minHeap.size() < k - 1) minHeap.push(split);
            else if (split > minHeap.top()) {
                minHeap.pop();
                minHeap.push(split);
            }

            if ((int)maxHeap.size() < k - 1) maxHeap.push(split);
            else if (split < maxHeap.top()) {
                maxHeap.pop();
                maxHeap.push(split);
            }
        }

        long long maxScore = 0, minScore = 0;
        while (!minHeap.empty()) {
            maxScore += minHeap.top();
            minHeap.pop();
        }
        while (!maxHeap.empty()) {
            minScore += maxHeap.top();
            maxHeap.pop();
        }

        return maxScore - minScore;
    }
};