Watch 10 video solutions for Put Marbles in Bags, a hard level problem involving Array, Greedy, Sorting. This walkthrough by NeetCodeIO has 14,713 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |