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] <= 109In 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(k * n^2) where we analyze subarray splits and their costs.
Space Complexity: O(k * n) to store subproblem solutions.
| 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. |
Put Marbles in Bags | Full Intuition | Dry Run | Leetcode-2551 | AMAZON | codestorywithMIK • codestorywithMIK • 11,803 views views
Watch 9 more video solutions →Practice Put Marbles in Bags with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor