Scale Engineer

Put Marbles in Bags

Hard
#2331Time: O(n log n), where `n` is the number of marbles. Creating the `partitionCosts` array takes `O(n)` time, sorting it takes `O(n log n)`, and summing the required elements takes `O(k)`. The dominant factor is sorting.Space: O(n) to store the `partitionCosts` array. If in-place sorting is used, this is the main space overhead besides the input.2 companies
Patterns
Greedy
Algorithms
Sorting
Data structures
ArrayHeap (Priority Queue)
Companies
FlipkartDE Shaw

Prompt

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.

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 <= 105
  • 1 <= weights[i] <= 109

Approaches

2 approaches with complexity analysis and trade-offs.

This approach leverages a key insight: the total score is determined by the k-1 locations where the marbles are divided. Each division point, or 'cut', between adjacent marbles weights[i] and weights[i+1] contributes weights[i] + weights[i+1] to the total score. The base score, weights[0] + weights[n-1], is constant for any partition. Therefore, to find the maximum and minimum scores, we only need to find the k-1 largest and k-1 smallest partition costs. This can be easily done by calculating all n-1 possible partition costs and sorting them.

Algorithm

  • If k is 1 or n, return 0 as there's only one possible distribution.
  • Create an array partitionCosts of size n-1.
  • Iterate from i = 0 to n-2, calculating partitionCosts[i] = weights[i] + weights[i+1].
  • Sort the partitionCosts array.
  • Initialize minSum and maxSum to 0.
  • Iterate from i = 0 to k-2:
    • Add partitionCosts[i] to minSum.
    • Add partitionCosts[n-2-i] to maxSum.
  • Return maxSum - minSum.

Walkthrough

The algorithm proceeds as follows:

  1. First, we recognize that to divide n marbles into k bags, we must make k-1 cuts. A cut between weights[i] and weights[i+1] separates the marbles into two bags, where weights[i] is the last element of one bag and weights[i+1] is the first element of the next. The cost formula weights[start] + weights[end] for a bag means these two weights are added to the total score.
  2. The total score can be expressed as weights[0] + weights[n-1] + sum_of_costs_of_k-1_cuts.
  3. To find the difference between the maximum and minimum scores, the constant term weights[0] + weights[n-1] cancels out. The problem reduces to finding (sum of k-1 largest cut costs) - (sum of k-1 smallest cut costs).
  4. We create an array, partitionCosts, of size n-1 to store all possible cut costs, where partitionCosts[i] = weights[i] + weights[i+1].
  5. We sort this partitionCosts array.
  6. The sum of the k-1 smallest costs is the sum of the first k-1 elements of the sorted array.
  7. The sum of the k-1 largest costs is the sum of the last k-1 elements of the sorted array.
  8. The final result is the difference between these two sums.
import java.util.Arrays; class Solution {    public long putMarbles(int[] weights, int k) {        int n = weights.length;        if (k == 1 || k == n) {            return 0;        }         // There will be k-1 partitions.        // The cost of a partition at index i is weights[i] + weights[i+1].        long[] partitionCosts = new long[n - 1];        for (int i = 0; i < n - 1; i++) {            partitionCosts[i] = (long)weights[i] + weights[i+1];        }         // Sort the partition costs to easily find the smallest and largest k-1 costs.        Arrays.sort(partitionCosts);         long minScoreContribution = 0;        long maxScoreContribution = 0;         // Sum the k-1 smallest and k-1 largest partition costs.        for (int i = 0; i < k - 1; i++) {            minScoreContribution += partitionCosts[i];            maxScoreContribution += partitionCosts[n - 2 - i];        }         return maxScoreContribution - minScoreContribution;    }}

Complexity

Time

O(n log n), where `n` is the number of marbles. Creating the `partitionCosts` array takes `O(n)` time, sorting it takes `O(n log n)`, and summing the required elements takes `O(k)`. The dominant factor is sorting.

Space

O(n) to store the `partitionCosts` array. If in-place sorting is used, this is the main space overhead besides the input.

Trade-offs

Pros

  • Conceptually simple and easy to implement.

  • Correctly solves the problem by identifying the core structure.

  • Efficient enough to pass within the given constraints.

Cons

  • The time complexity is dominated by sorting the entire partitionCosts array, which is not strictly necessary.

  • Uses O(n) extra space, which can be improved if k is much smaller than n.

Solutions

class Solution {public  long putMarbles(int[] weights, int k) {    int n = weights.length;    int[] arr = new int[n - 1];    for (int i = 0; i < n - 1; ++i) {      arr[i] = weights[i] + weights[i + 1];    }    Arrays.sort(arr);    long ans = 0;    for (int i = 0; i < k - 1; ++i) {      ans -= arr[i];      ans += arr[n - 2 - i];    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem