Problem Statement in English

You’re given an integer array weights where weights[i] is the weight of the i-th marble.

You are also given an integer k which is the number of bags you can use to store the marbles.

You must insert a range of weights into the bags. So, for example, $[0,5]$ means you can insert weights at indices 0, 1, 2, 3, 4, 5 into the bags.

The score of a bag is the sum of the first and last weights of the range of weights placed in the bag.

You must return the difference between the maximum and minimum score of the bags.

Approach

There are a couple of observations that can be made in order to solve this problem:

It is guaranteed that you will be adding the first and last marbles in the list to the final answer. And so, in a way, that is always guaranteed to be one pair.

All you really need to do, is to find the reamining $k - 1$ pairs of marbles that will be added to the bags.

Another thing to realiize is that the pairs of marbles that will be added to the bags will always be adjacent to each other.

From here, it is possible to visualize the problem better and hence solve it.

The first thing to do is to create a list of sums of pairs of adjacent marbles.

Then, sort the list of pairs in ascending order and take the first $k - 1$ pairs, in order to find the minimum score, then take the last $k - 1$ pairs, in order to find the maximum score. The final answer will be the difference between the maximum and minimum scores.

Solution in Python


class Solution:
    def putMarbles(self, weights: List[int], k: int) -> int:
        l = len(weights)

        if l == k or k == 1:
            return 0

        arr = []

        for i in range(1, l):
            pair = weights[i] + weights[i - 1]
            arr.append(pair)

        k -= 1

        arr.sort()
        smallest = sum(arr[:k])
        highest = sum(arr[-k:])

        return highest - smallest

Complexity

  • Time: $O(nlogn)$

  • Space: $O(n)$
    Since we store the pairs of adjacent marbles in a list.

Mistakes I Made

I did need the hint to realize that the first and last marble will ablays be added to the final answer.

And we are done.