HardArrayGreedySortingHeapUpdated Sep 2026

2551. Put Marbles in Bags

Asked at Salesforce

Difficulty

Hard

Time

O(n log n)

Space

O(n)

Pattern

Array

Companies

1

Problem

You have n marbles in a row, with weights given by the array weights. You must split this row into exactly k bags.

The rules are: every bag must hold at least one marble, and each bag must be a contiguous block of the row. So if marble i and marble j are in the same bag, every marble between them is in that bag too. A bag that covers indices i through j costs weights[i] + weights[j] — only its two end marbles matter.

The score of a split is the sum of the costs of all k bags. Return the difference between the largest score and the smallest score over all valid splits.

Splitting the row into k blocks

weightsbag 1bag 213510123Split [1,3] | [5,1] gives score (1+3) + (5+1) = 10weightsbag 1bag 213510123Split [1] | [3,5,1] gives score (1+1) + (3+1) = 6
Each cut point is a gap between two neighbours. A bag's cost is the sum of the two marbles at its ends.

Constraints

  • ●1 <= k <= weights.length <= 10^5
  • ●1 <= weights[i] <= 10^9

Examples

Example 1
Inputweights = [1,3,5,1], k = 2
Output4
WhyThe cheapest split is [1] and [3,5,1]: costs (1+1) + (3+1) = 6. The most expensive split is [1,3] and [5,1]: costs (1+3) + (5+1) = 10. The difference is 10 - 6 = 4.
Example 2
Inputweights = [1,3], k = 2
Output0
WhyWith two marbles and two bags, the only split is [1] and [3]. The max and min scores are both 1 + 3 = 4, so the difference is 0.

Asked At

1 companies
CompanyDifficulty
SalesforceHardView all Salesforce questions →

How to Think About It

1

Brute force: try all ways to partition n marbles into k non-empty groups — exponential and infeasible.

2

Key insight: the cost of a split depends on the endpoints of consecutive elements. For a sorted array, adjacent differences matter.

3

For minimum cost: sort the array, compute adjacent differences, and greedily select the k-1 smallest differences to avoid splitting.

4

For maximum cost: sort the array, compute adjacent differences, and greedily select the k-1 largest differences to create splits.

5

Optimal: O(n log n) time for sorting. Use a min-heap or max-heap of size k to track the k-1 differences, or simply sort the differences array.

Optimal Approach

Sort the weights array. Compute the differences between each pair of adjacent elements. The minimum cost is achieved by keeping the k-1 smallest differences as merge points (avoiding those splits), and the maximum cost by choosing the k-1 largest differences as split points. Specifically, the min cost is weights[0] + weights[n-1] + sum of the smallest (n-k) adjacent differences, and the max cost is the same base plus the sum of the largest (n-k) adjacent differences. Use a heap or simply sort the differences to extract the required values. Total time is O(n log n) due to sorting.

Only the cut gaps matter

pair sums486012Gap sums: 1+3=4, 3+5=8, 5+1=6. One gap must be cutsince k=2.sortedsmallestmiddlelargest468Cut the smallest gap (4) for the min score, thelargest gap (8) for the max score.answer = sum of largest (k-1) gaps − sum of smallest (k-1) gaps= 8 − 4 = 4
Every split shares the two outer marbles, so the score difference comes purely from which gaps you cut.
ComplexityTime O(n log n)Space O(n)Sorting the n-1 adjacent pair sums dominates; the rest is a single pass to add them up.

What Trips People Up in Real Interviews

1

Clarify whether the bags are distinguishable or indistinguishable — here they are indistinguishable.

2

Work through a small example (e.g., weights = [1, 3, 5, 1], k = 2) to find the pattern.

3

Explain why sorting the weights first is the right approach — the optimal splits use contiguous sorted elements.

4

Describe the greedy strategy clearly: differences between adjacent sorted elements represent potential split costs.

5

Mention that the minimum uses the k-1 smallest gaps and the maximum uses the k-1 largest gaps.

Solution Code

O(n log n) time
def putMarbles(weights, k):
    n = len(weights)
    if k == 1 or k == n:
        return 0
    diffs = []
    for i in range(n - 1):
        diffs.append(weights[i] + weights[i + 1])
    diffs.sort()
    pairs = n - k
    minCost = sum(diffs[:pairs])
    maxCost = sum(diffs[pairs:])
    return maxCost - minCost

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Put Marbles in Bags problem?

You have n bags of marbles, each with some number of marbles. You are given an integer array weights of length n where weights[i] is the number of marbles in the i-th bag. You must split the marbles into exactly k non-empty groups (bags). The cost of a group is the sum of the weights in that group. The total cost is the sum of the costs of all k groups. Find the minimum and maximum possible total cost of splitting the marbles into k groups.

How do you solve Put Marbles in Bags?

The optimal approach runs in O(n log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Put Marbles in Bags?

Put Marbles in Bags is asked at Salesforce. It is a hard difficulty problem.

What are common mistakes on Put Marbles in Bags?
  • Clarify whether the bags are distinguishable or indistinguishable — here they are indistinguishable.
  • Work through a small example (e.g., weights = [1, 3, 5, 1], k = 2) to find the pattern.
  • Explain why sorting the weights first is the right approach — the optimal splits use contiguous sorted elements.
  • Describe the greedy strategy clearly: differences between adjacent sorted elements represent potential split costs.
  • Mention that the minimum uses the k-1 smallest gaps and the maximum uses the k-1 largest gaps.