Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C#

Solution: Put Marbles in Bags

Explore how to optimally divide marbles into k bags by applying sorting and pairwise sums. Understand how to calculate the difference between maximum and minimum possible scores and implement a solution with efficient time and space complexity. This lesson builds skills in problem decomposition and applying the sort and search pattern for coding interviews.

We'll cover the following...

Statement

You are given k bags and a 0-indexed integer array, weights, where weights[i] represents the weight of the ithi^{th} marble.

Your task is to divide the marbles into the k bags according to the following rules:

  1. No bag can be empty.

  2. If the ithi^{th} marble and the jthj^{th} marble are placed in the same bag, then all marbles with indexes between i and j (inclusive) must also be placed in that same bag.

  3. If a bag contains all the marbles from index i to j (inclusive), its cost is calculated as weights[i] + weights[j].

After distributing the marbles, the sum of the costs of all the k bags is called the score.

Return the difference between the maximum and minimum scores achievable by distributing the marbles into the k bags.

Constraints:

  • ...