We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Put Marbles in Bags

Number: 2681

Difficulty: Hard

Paid? No

Companies: Amazon, Meta, TikTok, Google, Uber, Microsoft, Flipkart

Problem Description

Given an array of marbles' weights and an integer k representing the number of bags, partition the array into k contiguous subarrays (bags) such that no bag is empty. The cost of a bag that covers indices i through j is defined as weights[i] + weights[j]. The total score is the sum of the costs of all bags. Return the difference between the maximum and minimum possible total scores achievable by different valid distributions.

Key Insights

  • The first and last weights always contribute to the cost since the first bag starts with weights[0] and the last bag ends with weights[n-1].
  • Any additional bag creation requires making a cut between marbles; a cut between indices i and i+1 adds an extra cost weights[i] + weights[i+1].
  • To minimize the total score, one should choose the k-1 cuts with the smallest additional costs; conversely, to maximize the total score, choose the k-1 largest additional costs.
  • The problem reduces to computing candidate values for cuts (for every adjacent pair) and then picking the smallest and largest sums appropriately.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the candidate costs computed from the adjacent pairs. Space Complexity: O(n) for storing the candidate values.

Solution

We first compute a base cost using the first and last elements (weights[0] + weights[n-1]), which is included in every valid partition. For each possible cut between marbles (from index 0 to n-2), we calculate an additional candidate cost = weights[i] + weights[i+1]. These candidates represent the extra cost that would get added if we choose that particular cut to separate a bag.

Since we need to create exactly k bags, we have to make exactly k-1 cuts. The minimal configuration is achieved by selecting the k-1 smallest candidate costs, while the maximum configuration is achieved by selecting the k-1 largest candidate costs. We then sum these chosen candidate costs with the base cost. The final answer is the difference between the maximum total score and the minimum total score.

The algorithm uses a greedy approach and a sorting step to pick the appropriate candidate cuts.

Code Solutions

# Python solution for "Put Marbles in Bags"

def put_marbles_in_bags(weights, k):
    n = len(weights)
    # Base cost is always the sum of the first and last marble weights
    base_cost = weights[0] + weights[n - 1]

    # Compute all candidate costs for possible cuts
    candidate_costs = []
    for i in range(n - 1):
        candidate_costs.append(weights[i] + weights[i + 1])
    
    # Sort candidate costs
    candidate_costs.sort()
    
    # If k == 1, no additional cuts are needed
    if k == 1:
        return 0
    
    # Sum of the k-1 smallest candidates gives extra cost for the minimum score configuration
    min_extra = sum(candidate_costs[:k - 1])
    # Sum of the k-1 largest candidates gives extra cost for the maximum score configuration
    max_extra = sum(candidate_costs[-(k - 1):])
    
    # Return the difference between maximum and minimum total score.
    return (base_cost + max_extra) - (base_cost + min_extra)

# Example usage:
# weights = [1,3,5,1], k = 2 should return 4
print(put_marbles_in_bags([1, 3, 5, 1], 2))
← Back to All Questions