Obsidian Notes

Put Marbles in Bags

3 min read

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

Divide the marbles into the k bags according to the following rules:

  • No bag is empty.
  • If the ith marble and jth marble are in a bag, then all marbles with an index between the ith and jth indices should also be in that same bag.
  • If a bag consists of all the marbles with an index from i to j inclusively, then the cost of the bag is weights[i] + weights[j].

The score after distributing the marbles is the sum of the costs of all the k bags.

Return the difference between the maximum and minimum scores among marble distributions.

Example 1:

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.
The distribution [1,3],[5,1], results in the maximal score of (1+3) + (5+1) = 10.
Thus, we return their difference 10 - 6 = 4.

Example 2:

Input: weights = [1, 3], k = 2
Output: 0
Explanation: The only distribution possible is [1],[3].
Since both the maximal and minimal score are the same, we return 0.

Constraints:

  • 1 <= k <= weights.length <= 105
  • 1 <= weights[i] <= 109

Approach

  • So the important point in this question is we can solve this by maintaining adjacent sum array why you ask? because when you will part then in calculating sum you will have last element of previous part added with first element of a partition aka adjacent sum

  • Something like this : weights = [1, 3, 5, 1], k = 2
    You need 1 cut. Possible cuts:

      Between 1|3 → groups: [1], [3,5,1] → cost: 1+1 + 3+1 = 6

  Between 3|5 → [1,3], [5,1] → cost: 1+3 + 5+1 = 10

  Between 5|1 → [1,3,5], [1] → cost: 1+5 + 1+1 = 8

  • Time: O(nlogn) time taken to sort, Space: O(n)

class Solution {
    public long putMarbles(int[] weights, int k) {
        int[] sum = new int[weights.length-1];
        for (int i = 0; i < sum.length; i++) {
            sum[i] = weights[i] + weights[i+1];
        }
 
        Arrays.sort(sum);
        long min = 0, max = 0;
        // for k bags there would be k - 1 parting lines
        for (int i = 0; i < k - 1; i++) {
            min += sum[i];
            max += sum[sum.length - i - 1];
        }
 
        return max - min;
    }
}

Backlinks