Put Marbles in Bags - Practice Coding Problems

Put Marbles in Bags - Problem

You have k bags. You are given a 0-indexed integer array weights where weights[i] is the weight of the i^th 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 i^th marble and j^th marble are in a bag, then all marbles with an index between the i^th and j^th 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.

Input & Output

Example 1 — Basic Case

$ Input: weights = [1,3,5,1], k = 2

› Output: 4

💡 Note: Two bags needed. Min score: [1,3] + [5,1] = (1+3) + (5+1) = 10. Max score: [1] + [3,5,1] = (1+1) + (3+1) = 6. Difference = 10-6 = 4.

Example 2 — Three Bags

$ Input: weights = [1,3], k = 2

› Output: 0

💡 Note: Only one way to split into 2 bags: [1] + [3]. Cost = (1+1) + (3+3) = 8. Since only one arrangement exists, difference is 0.

Example 3 — Larger Array

$ Input: weights = [1,3,5,1,2], k = 3

› Output: 7

💡 Note: Need 3 bags. Different cuts create different total scores. The difference between maximum and minimum possible scores is 7.

Constraints

1 ≤ k ≤ weights.length ≤ 10⁵
1 ≤ weights[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array of marble weights and k bags needed

Partition Rules

Contiguous subarrays, bag cost = first + last marble

Score Difference

Find max score - min score across all valid partitions

Key Takeaway

🎯 Key Insight: Focus on the k-1 cuts needed and sort their edge contributions to find optimal max/min partitions efficiently

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that we need k-1 cuts to create k bags, and each cut creates two new edges (adjacent marble pairs). By focusing on the contribution of these edge pairs and sorting them, we can greedily select the optimal cuts for maximum and minimum scores. Best approach uses greedy sorting with Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Partitions	O(C(n-1,k-1))	O(k)	Generate all possible ways to partition the array into k bags and calculate max-min difference
Greedy - Sort Edge Pairs by Contribution	O(n log n)	O(n)	Focus on the k-1 cuts and sort edge pairs by their contribution to maximize/minimize scores

Brute Force - Try All Partitions — Algorithm Steps

Generate all valid k-way partitions using backtracking
For each partition, calculate total cost as sum of (first+last) for each bag
Track maximum and minimum scores across all partitions

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Partitions

Use backtracking to create all k-way divisions

Calculate Scores

For each partition, sum up bag costs (first+last)

Find Difference

Track max and min scores, return difference

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

long long minScore, maxScore;

void backtrack(int* weights, int start, int bagsLeft, long long currentScore, int n) {
    if (bagsLeft == 1) {
        long long cost = weights[start] + weights[n-1];
        long long totalScore = currentScore + cost;
        if (totalScore < minScore) minScore = totalScore;
        if (totalScore > maxScore) maxScore = totalScore;
        return;
    }
    
    for (int end = start; end <= n - bagsLeft; end++) {
        long long cost = weights[start] + weights[end];
        backtrack(weights, end + 1, bagsLeft - 1, currentScore + cost, n);
    }
}

long long solution(int* weights, int n, int k) {
    if (k == 1 || k == n) return 0;
    
    minScore = LLONG_MAX;
    maxScore = LLONG_MIN;
    backtrack(weights, 0, k, 0, n);
    return maxScore - minScore;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int weights[1000];
    int n = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            weights[n++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%lld\n", solution(weights, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(C(n-1,k-1))

Need to choose k-1 cut positions from n-1 possible positions, leading to exponential combinations

✓ Linear Growth

Space Complexity

O(k)

Recursion stack depth for backtracking plus storage for current partition

✓ Linear Space

28.5K Views

Medium Frequency

~35 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Partitions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler