Put Marbles in Bags Interview Question for Amazon

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.

For example:

weights = [1,3,5,1], k = 2

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, you should return their difference 10 - 6 = 4.

As another example:

weights = [1, 3], k = 2 The only distribution possible is [1],[3]. Since both the maximal and minimal score are the same, you should return 0.

Naive Approach

A brute-force approach would involve trying all possible ways to divide the weights array into k bags according to the given rules. For each such division, calculate the score and maintain the minimum and maximum scores encountered so far. After exploring all possibilities, return the difference between the maximum and minimum scores.

This approach has exponential time complexity due to the enumeration of all possible divisions, which makes it impractical for larger inputs.

Big(O) Runtime: O(2^n), where n is the length of the weights array

Big(O) Space: O(n) in the worst case for storing the recursion stack.

Optimal Approach: Greedy Algorithm

An optimal approach leverages a greedy algorithm to find the minimum and maximum scores more efficiently. The key idea is to realize that the weights at the start and end of the weights array always contribute to the score. The problem then boils down to selecting k-1 split points in the array. To minimize the score, select the k-1 smallest adjacent sums as split points. To maximize the score, select the k-1 largest adjacent sums as split points.

Algorithm:

Calculate the adjacent sums: Create a new array adjacentSums where adjacentSums[i] = weights[i] + weights[i+1] for i from 0 to n-2.
Sort the adjacentSums array.
Minimum Score: Add the first k-1 elements of the sorted adjacentSums array to weights[0] + weights[n-1].
Maximum Score: Add the last k-1 elements of the sorted adjacentSums array to weights[0] + weights[n-1].
Return the difference between the maximum and minimum scores.

Example:

weights = [1, 3, 5, 1], k = 2

adjacentSums = [1+3, 3+5, 5+1] = [4, 8, 6]
Sorted adjacentSums = [4, 6, 8]
Minimum Score: 1 + 1 + 4 = 6
Maximum Score: 1 + 1 + 8 = 10
Difference: 10 - 6 = 4

Edge Cases:

k = 1: Only one bag is possible, so the score is weights[0] + weights[n-1]. The difference between the maximum and minimum score is 0.
k = n: Each marble is in its own bag. The score is weights[0] + weights[n-1] + weights[1] + weights[1] + ... + weights[n-2] + weights[n-2]. Simplify to weights[0] + weights[n-1] + 2 * sum(weights[1] to weights[n-2]). The difference between the maximum and minimum score is 0.

import java.util.Arrays;

class Solution {
    public long putMarbles(int[] weights, int k) {
        int n = weights.length;
        if (k == 1 || k == n) {
            return 0;
        }

        long[] adjacentSums = new long[n - 1];
        for (int i = 0; i < n - 1; i++) {
            adjacentSums[i] = weights[i] + weights[i + 1];
        }

        Arrays.sort(adjacentSums);

        long minScore = weights[0] + weights[n - 1];
        for (int i = 0; i < k - 1; i++) {
            minScore += adjacentSums[i];
        }

        long maxScore = weights[0] + weights[n - 1];
        for (int i = n - 2; i >= n - k; i--) {
            maxScore += adjacentSums[i];
        }

        return maxScore - minScore;
    }
}

Big(O) Runtime: O(n log n), where n is the length of the weights array due to the sorting of the adjacentSums array. The rest of the algorithm runs in O(n) time.

Big(O) Space: O(n) space is used to store the adjacentSums array.