Put Marbles in Bags

Leetcode Problem:

• Put Marbles in Bags

Summary

• The problem requires finding the difference between the maximum and minimum scores of marble distributions given an array of weights and the number of bags.

Approach

• The solution uses a prefix sum array to efficiently calculate the sum of weights for each subarray
• It then sorts the prefix sum array and iterates through it to calculate the minimum and maximum scores by adding the weights at specific indices
• The difference between the maximum and minimum scores is then returned.

Complexity

• O(n log n) due to the sorting of the prefix sum array, where n is the number of weights.

Solution Code:

class Solution {
public:
    long long putMarbles(vector& weights, int k) {
        if(weights.size() == k) return 0;
        vector prefixSum;
        long long sum = weights[0];
        for(int i = 1 ; i < weights.size(); i++){
            sum += weights[i];
            prefixSum.push_back(sum);
            sum -= weights[i-1];
        }
        sort(prefixSum.begin(), prefixSum.end());

        long long maxScore = weights[0] + weights[weights.size() - 1];
        long long minScore = weights[0] + weights[weights.size() - 1];
        for(int i = 0; i < k - 1; i++){
            minScore += prefixSum[i];
            maxScore += prefixSum[prefixSum.size() - 1 - i];
        }

        return maxScore - minScore;
    }
};