In this guide, you will get 2551. Put Marbles in Bags LeetCode Solution with the best time and space complexity. The solution to Put Marbles in Bags problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
2551. Put Marbles in Bags LeetCode Solution in C++
class Solution {
public:
long long putMarbles(vector<int>& weights, int k) {
// To distribute marbles into k bags, there will be k - 1 cuts. If there's a
// cut after weights[i], then weights[i] and weights[i + 1] will be added to
// the cost. Also, no matter how we cut, weights[0] and weights[n - 1] will
// be counted. So, the goal is to find the max/min k - 1 weights[i] +
// weights[i + 1].
vector<int> arr; // weights[i] + weights[i + 1]
long mn = 0;
long mx = 0;
for (int i = 0; i + 1 < weights.size(); ++i)
arr.push_back(weights[i] + weights[i + 1]);
ranges::sort(arr);
for (int i = 0; i < k - 1; ++i) {
mn += arr[i];
mx += arr[arr.size() - 1 - i];
}
return mx - mn;
}
}; /* code provided by PROGIEZ */
2551. Put Marbles in Bags LeetCode Solution in Java
class Solution {
public long putMarbles(int[] weights, int k) {
// To distribute marbles into k bags, there will be k - 1 cuts. If there's a
// cut after weights[i], then weights[i] and weights[i + 1] will be added to
// the cost. Also, no matter how we cut, weights[0] and weights[n - 1] will
// be counted. So, the goal is to find the max/min k - 1 weights[i] +
// weights[i + 1].
int[] arr = new int[weights.length - 1]; // weights[i] + weights[i + 1]
long mn = 0;
long mx = 0;
for (int i = 0; i < arr.length; ++i)
arr[i] = weights[i] + weights[i + 1];
Arrays.sort(arr);
for (int i = 0; i < k - 1; ++i) {
mn += arr[i];
mx += arr[arr.length - 1 - i];
}
return mx - mn;
}
} // code provided by PROGIEZ
2551. Put Marbles in Bags LeetCode Solution in Python
class Solution:
def putMarbles(self, weights: list[int], k: int) -> int:
# To distribute marbles into k bags, there will be k - 1 cuts. If there's a
# cut after weights[i], then weights[i] and weights[i + 1] will be added to
# the cost. Also, no matter how we cut, weights[0] and weights[n - 1] will
# be counted. So, the goal is to find the max//min k - 1 weights[i] +
# weights[i + 1].
# weights[i] + weights[i + 1]
arr = [a + b for a, b in itertools.pairwise(weights)]
return sum(heapq.nlargest(k - 1, arr)) - sum(heapq.nsmallest(k - 1, arr)) # code by PROGIEZ
