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:
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.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 <= 1051 <= weights[i] <= 109Problem 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.
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.
This C solution sorts the weights array and calculates the minimum and maximum possible scores by picking k smallest and largest weights to form the bags.
Time Complexity: O(n log n) due to sorting the weights array.
Space Complexity: O(1) as we only use a fixed amount of extra space.
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.
This solution applies a dynamic programming technique to compute minimum scores through segment evaluations. A similar approach is employed to compute the maximum possible score.
Time Complexity: O(k * n^2) where we analyze subarray splits and their costs.
Space Complexity: O(k * n) to store subproblem solutions.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Picking for Minimum and Maximum Score | Time Complexity: O(n log n) due to sorting the weights array. |
| Dynamic Programming Approach | Time Complexity: O(k * n^2) where we analyze subarray splits and their costs. |
| Problem Transformation + Sorting | — |
| 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. |
Put Marbles in Bags - Leetcode 2551 - Python • NeetCodeIO • 14,713 views views
Watch 9 more video solutions →Practice Put Marbles in Bags with our built-in code editor and test cases.
Practice on FleetCode