Put Marbles in Bags solution and explanation
Google
9 more videos on this problem
Put Marbles in Bags - Leetcode 2551 - PythonNeetCodeIO · 16:55 · 14K views
Put Marbles in Bags | Full Intuition | Dry Run | Leetcode 2551 | AMAZON | codestorywithMIKcodestorywithMIK · 26:36 · 14K views
Put Marbles in Bags II Greedy II Sorting II Leetcode 2551 II Code & NotesAryan Mittal · 12:29 · 8K views
2551. Put Marbles in Bags | Weekly Contest 330 | LeetCode 2551Bro Coders · 9:41 · 6K views
LeetCode 2551 Put Marbles in BagsJeevan Kumar - Cracckify · 9:44 · 2K views
2551. Put Marbles in Bags | LeetCode HardDeep Tech · 14:06 · 1K views
2551. Put Marbles in Bags | Leetcode contest 330A Code Daily! · 8:55 · 1K views
【每日一题】LeetCode 2551. Put Marbles in BagsHuifeng Guan · 8:28 · 934 views
2551. Put Marbles in Bags | Greedy | Sorting | Priority Queue | LeetcodeRapid Syntax · 10:51 · 762 views
2551. Put Marbles in Bags (Leetcode Hard)Programming Live with Larry · 15:40 · 687 views
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. 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
ithmarble andjthmarble are in a bag, then all marbles with an index between theithandjthindices should also be in that same bag. - If a bag consists of all the marbles with an index from
itojinclusively, then the cost of the bag isweights[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 <= 1051 <= weights[i] <= 109
Approach overview
Problem Overview: You are given an array where weights[i] represents the weight of the i-th marble. The marbles must be split into k consecutive bags. The score of a bag equals the sum of the first and last marble in that bag. The task is to compute the difference between the maximum possible score and the minimum possible score across all valid partitions.
Approach 1: Greedy Picking for Minimum and Maximum Score (Sorting / Pair Contributions) (Time: O(n log n), Space: O(n))
The key observation is that every partition introduces a boundary between two marbles. If a split occurs between indices i and i+1, it contributes weights[i] + weights[i+1] to the total score. Since exactly k-1 splits are required, the problem reduces to choosing which k-1 pair contributions to include. Compute all adjacent pair sums, store them in an array, then sort it. The maximum score comes from picking the largest k-1 values, while the minimum score comes from picking the smallest k-1 values. Subtract the two totals to get the answer. This greedy insight removes the need to simulate partitions explicitly and converts the problem into selecting extremes from pair contributions. The logic relies on properties of arrays and ordering with greedy choice.
An alternative implementation uses a heap (priority queue) instead of sorting. Push all pair sums into a min-heap and max-heap, then extract the smallest and largest k-1 contributions. The complexity remains O(n log n), though sorting is typically simpler and faster in practice.
Approach 2: Dynamic Programming Partitioning (Time: O(n^2 * k), Space: O(n * k))
A more general approach treats the problem as a partition DP. Define dp[i][j] as the best score achievable when splitting the first i marbles into j bags. For each state, iterate over the possible previous partition point p and add the score contribution weights[p] + weights[i]. Running the DP twice (once for minimum score and once for maximum score) yields the required difference. While this approach directly models the partitioning process, it becomes expensive because each state scans earlier positions. The time complexity grows to O(n^2 * k), making it unsuitable for large inputs.
Recommended for interviews: Interviewers expect the greedy pair-sum insight. The brute-force or DP formulation shows you understand the partition structure, but the optimal solution recognizes that only the k-1 boundary contributions matter. Converting the problem into selecting the smallest and largest adjacent pair sums reduces the search space dramatically and leads to the clean O(n log n) solution.
Approach 1: Greedy Picking for Minimum and Maximum Score
In this approach, we will use a greedy strategy to partition the weights such that we achieve both the minimum and maximum possible scores for the marble distribution. The key observation here is to leverage sorting of the weights to maximize or minimize the cost of each bag.
def put_marbles(weights, k):
weights.sort()
total_min = 0
total_max = 0
n = len(weights)
for i in range(k):
total_min += weights[i] + weights[n - 1 - i]
total_max += weights[n - 1 - i] + weights[i]
return total_max - total_min
weights = [1, 3, 5, 1]
print(put_marbles(weights, 2))import java.util.Arrays;
class Solution {
public int putMarbles(int[] weights, int k) {
Arrays.sort(weights);
int total_min = 0, total_max = 0;
for(int i = 0; i < k; i++) {
total_min += weights[i] + weights[weights.length - 1 - i];
total_max += weights[weights.length - 1 - i] + weights[i];
}
return total_max - total_min;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] weights = {1, 3, 5, 1};
System.out.println(solution.putMarbles(weights, 2));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int putMarbles(std::vector<int>& weights, int k) {
std::sort(weights.begin(), weights.end());
int total_min = 0, total_max = 0;
for(int i = 0; i < k; ++i) {
total_min += weights[i] + weights[weights.size() - 1 - i];
total_max += weights[weights.size() - 1 - i] + weights[i];
}
return total_max - total_min;
}
int main() {
std::vector<int> weights = {1, 3, 5, 1};
std::cout << putMarbles(weights, 2) << std::endl;
return 0;
}function putMarbles(weights, k) {
weights.sort((a, b) => a - b);
let total_min = 0, total_max = 0;
let n = weights.length;
for (let i = 0; i < k; i++) {
total_min += weights[i] + weights[n - 1 - i];
total_max += weights[n - 1 - i] + weights[i];
}
return total_max - total_min;
}
console.log(putMarbles([1, 3, 5, 1], 2));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return *(int*)a - *(int*)b;
}
int putMarbles(int* weights, int weightsSize, int k) {
int total_min = 0, total_max = 0;
qsort(weights, weightsSize, sizeof(int), compare);
for(int i = 0; i < k; i++) {
total_min += weights[i] + weights[weightsSize - 1 - i];
total_max += weights[weightsSize - 1 - i] + weights[i];
}
return total_max - total_min;
}
int main() {
int weights[] = {1, 3, 5, 1};
int result = putMarbles(weights, 4, 2);
printf("%d\n", result);
return 0;
}using System;
using System.Linq;
public class Solution {
public int PutMarbles(int[] weights, int k) {
Array.Sort(weights);
int total_min = 0, total_max = 0;
for(int i = 0; i < k; i++) {
total_min += weights[i] + weights[weights.Length - 1 - i];
total_max += weights[weights.Length - 1 - i] + weights[i];
}
return total_max - total_min;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] weights = new int[] { 1, 3, 5, 1 };
Console.WriteLine(solution.PutMarbles(weights, 2));
}
}Using Python's built-in sort functionality, we calculate the min and max scores by pairing sorted elements for the desired partitions.
Time Complexity: O(n log n) for sorting.
Space Complexity: O(1) extra space.
Approach 2: Dynamic Programming Approach
The dynamic programming route considers evaluating partial solutions and utilizing them to form the global optimum. Here, DP arrays keep track of the best possible score up to each marble in the sequence. This methodology, while more complex, offers an exhaustive evaluation and solution-guarantee mechanism for larger constraints when direct greedy methods might struggle.
import sys
def put_marbles(weights, k):
n = len(weights)
dp = [[float('inf')] * n for _ in range(k)]
for j in range(n):
dp[0][j] = weights[0] + weights[j]
for i in range(1, k):
for j in range(i, n):
for p in range(i - 1, j):
dp[i][j] = min(dp[i][j], dp[i - 1][p] + weights[p + 1] + weights[j])
min_score = dp[k-1][n-1]
max_score = 0 # Same procedure would be used to find max_score
return max_score - min_score
weights = [1, 3, 5, 1]
print(put_marbles(weights, 2))import java.util.*;
public class Solution {
public int putMarbles(int[] weights, int k) {
int n = weights.length;
int[][] dp = new int[k][n];
for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
for (int j = 0; j < n; ++j) {
dp[0][j] = weights[0] + weights[j];
}
for (int i = 1; i < k; ++i) {
for (int j = i; j < n; ++j) {
for (int p = i - 1; p < j; ++p) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][p] + weights[p + 1] + weights[j]);
}
}
}
int min_score = dp[k-1][n-1];
int max_score = 0; // same for max calculations
return max_score - min_score;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] weights = {1, 3, 5, 1};
System.out.println(sol.putMarbles(weights, 2));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int putMarbles(const vector<int>& weights, int k) {
int n = weights.size();
vector<vector<int>> dp(k, vector<int>(n, INT_MAX));
for (int j = 0; j < n; ++j) {
dp[0][j] = weights[0] + weights[j];
}
for (int i = 1; i < k; ++i) {
for (int j = i; j < n; ++j) {
for (int p = i - 1; p < j; ++p) {
dp[i][j] = min(dp[i][j], dp[i - 1][p] + weights[p + 1] + weights[j]);
}
}
}
int min_score = dp[k-1][n-1];
int max_score = 0; // Use similar logic with max function
return max_score - min_score;
}
int main() {
vector<int> weights = {1, 3, 5, 1};
cout << putMarbles(weights, 2) << endl;
return 0;
}function putMarbles(weights, k) {
let n = weights.length;
let dp = Array.from({ length: k }, () => Array(n).fill(Infinity));
for (let j = 0; j < n; ++j) {
dp[0][j] = weights[0] + weights[j];
}
for (let i = 1; i < k; ++i) {
for (let j = i; j < n; ++j) {
for (let p = i - 1; p < j; ++p) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][p] + weights[p + 1] + weights[j]);
}
}
}
let min_score = dp[k-1][n-1];
let max_score = 0; // This can be similarly calculated
return max_score - min_score;
}
console.log(putMarbles([1, 3, 5, 1], 2));#include <stdio.h>
#include <limits.h>
int putMarbles(int* weights, int weightsSize, int k) {
int dp[k][weightsSize];
for(int i = 0; i < k; ++i) {
for(int j = 0; j < weightsSize; ++j) {
dp[i][j] = INT_MAX;
}
}
for(int j = 0; j < weightsSize; ++j) {
dp[0][j] = weights[0] + weights[j];
}
for(int i = 1; i < k; i++) {
for(int j = i; j < weightsSize; ++j) {
for(int p = i - 1; p < j; ++p) {
dp[i][j] = fmin(dp[i][j], dp[i - 1][p] + weights[p + 1] + weights[j]);
}
}
}
int min_score = dp[k-1][weightsSize-1];
int max_score = 0; // Similar logic, replacing fmin with fmax
return max_score - min_score;
}
int main() {
int weights[] = {1, 3, 5, 1};
printf("%d\n", putMarbles(weights, 4, 2));
return 0;
}using System;
namespace MarbleBags {
public class Solution {
public int PutMarbles(int[] weights, int k) {
int n = weights.Length;
int[,] dp = new int[k, n];
for (int i = 0; i < k; ++i)
for (int j = 0; j < n; ++j)
dp[i, j] = int.MaxValue;
for (int j = 0; j < n; ++j) {
dp[0, j] = weights[0] + weights[j];
}
for (int i = 1; i < k; ++i) {
for (int j = i; j < n; ++j) {
for (int p = i - 1; p < j; ++p) {
dp[i, j] = Math.Min(dp[i, j], dp[i - 1, p] + weights[p + 1] + weights[j]);
}
}
}
int min_score = dp[k-1, n-1];
int max_score = 0; // mirrored computation for maximum
return max_score - min_score;
}
public static void Main(string[] args) {
int[] weights = { 1, 3, 5, 1 };
Solution sol = new Solution();
Console.WriteLine(sol.PutMarbles(weights, 2));
}
}
}Python's implementation extends the problem by dynamically deciding subproblem sequences into complete solutions, minimizing errors.
Time Complexity: O(k * n^2) concurrent with established modeling division.
Space Complexity: O(k * n) representing the DP fix memory.
Approach 3: Problem Transformation + Sorting
We can transform the problem into: dividing the array weights into k consecutive subarrays, that is, we need to find k-1 splitting points, each splitting point's cost is the sum of the elements on the left and right of the splitting point. The difference between the sum of the costs of the largest k-1 splitting points and the smallest k-1 splitting points is the answer.
Therefore, we can process the array weights and transform it into an array arr of length n-1, where arr[i] = weights[i] + weights[i+1]. Then we sort the array arr, and finally calculate the difference between the sum of the costs of the largest k-1 splitting points and the smallest k-1 splitting points.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the array weights.
function putMarbles(weights: number[], k: number): number {
const n = weights.length;
const arr: number[] = [];
for (let i = 0; i < n - 1; ++i) {
arr.push(weights[i] + weights[i + 1]);
}
arr.sort((a, b) => a - b);
let ans = 0;
for (let i = 0; i < k - 1; ++i) {
ans += arr[n - i - 2] - arr[i];
}
return ans;
}func putMarbles(weights []int, k int) (ans int64) {
n := len(weights)
arr := make([]int, n-1)
for i, w := range weights[:n-1] {
arr[i] = w + weights[i+1]
}
sort.Ints(arr)
for i := 0; i < k-1; i++ {
ans += int64(arr[n-2-i] - arr[i])
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Picking for Minimum and Maximum Score | Time Complexity: O(n log n) for sorting. |
| Dynamic Programming Approach | Time Complexity: O(k * n^2) concurrent with established modeling division. |
| Problem Transformation + Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting (Pair Sums) | O(n log n) | O(n) | Best general solution. Simple implementation and optimal for interview constraints. |
| Greedy with Heaps (Priority Queue) | O(n log n) | O(n) | Useful when extracting extremes dynamically instead of sorting. |
| Dynamic Programming Partitioning | O(n^2 * k) | O(n * k) | Educational approach when learning partition DP, but inefficient for large inputs. |
Frequently asked questions
Is Put Marbles in Bags easy or hard?
The problem is labeled Hard because the greedy insight is not obvious at first glance. Once you recognize that only the k-1 partition boundaries contribute variable scores, the solution becomes straightforward with sorting and runs efficiently in O(n log n).
Put Marbles in Bags Python/Java solution
In Python or Java, compute all adjacent pair sums, store them in a list, sort the list, then sum the first k-1 and last k-1 values. The final answer is the difference between these totals. The implementation typically takes fewer than 20 lines of code.
How to solve Put Marbles in Bags in O(n)?
A strict O(n) solution is generally not used because selecting the largest and smallest k-1 pair sums requires ordering. The practical optimal method computes all adjacent pair sums and sorts them, resulting in O(n log n). With specialized selection algorithms, partial selection could approach linear time, but sorting is simpler and standard in interviews.
What is the best approach for Put Marbles in Bags?
The optimal approach is a greedy strategy based on adjacent pair contributions. Compute all values of weights[i] + weights[i+1], sort them, then choose the smallest k-1 for the minimum score and the largest k-1 for the maximum score. This reduces the partitioning problem to selecting extremes and runs in O(n log n) time.
Is Put Marbles in Bags asked at Google/Amazon/Meta?
Problems involving greedy boundary selection, partition scoring, and pair contributions appear frequently in interviews at companies like Google, Amazon, and Meta. Variants test your ability to transform partition problems into simpler array or sorting problems using greedy insights.
What data structure is used in Put Marbles in Bags?
The solution primarily uses arrays to store adjacent pair sums and either sorting or heaps (priority queues) to select the smallest and largest k-1 contributions. Sorting is the most common implementation because it keeps the logic simple and efficient.
What is the time complexity of Put Marbles in Bags?
The optimal greedy solution runs in O(n log n) time due to sorting the adjacent pair sums. Space complexity is O(n) to store the pair contributions. A dynamic programming approach exists but can take up to O(n^2 * k) time, which is significantly slower for large inputs.