Put Marbles in Bags — LeetCode 2551 Python Solution

The problem

You have k bags. You are given a 0-indexed integer array weights where weights[i] is the weight of the ith marble.

Example

Input

weights = [1,3,5,1], k = 2

Output

4

Explanation

The distribution [1],[3,5,1] results in the minimal score of (1+1) + (3+1) = 6.

Python solution

class Solution:
    def putMarbles(self, weights: List[int], k: int) -> int:
        arr = sorted(a + b for a, b in pairwise(weights))
        return sum(arr[len(arr) - k + 1 :]) - sum(arr[: k - 1])

Complexity

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2551. Put Marbles in Bags is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems