Understand Put Marbles in Bags Problem

Problem: Put Marbles in Bags

Difficulty: Hard

Problem Statement :

You have k bags and are given a 0-indexed integer array weights where weights[i] represents the weight of the iᵗʰ marble. Your task is to divide the marbles into the k bags following these rules:

  1. No bag is empty.
  2. Contiguous Assignment: If the iᵗʰ and jᵗʰ marbles are in a bag, then all marbles with indices between i and j must also be in that bag.
  3. Bag Cost: If a bag contains marbles from index i to j inclusively, its cost is calculated as weights[i] + weights[j].

The score after distributing the marbles is the sum of the costs of all k bags.

Objective: Return the difference between the maximum and minimum scores achievable through different valid distributions of the marbles.

Examples

Example 1:

Input:

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

Output:

4

Explanation:

  • Minimal score distribution: [1], [3,5,1] → (1+1) + (3+1) = 6
  • Maximal score distribution: [1,3], [5,1] → (1+3) + (5+1) = 10 Difference: 10 - 6 = 4

Input:

weights = [1, 3], k = 2

Output:

0

Explanation:

  • The only possible distribution is [1], [3], resulting in the same score for both maximum and minimum.
Category:
  • Sorting
  • Arrays
Programming Language:
  • Java
Reference Link:

https://leetcode.com/problems/put-marbles-in-bags/description/

Online IDE

Scroll down for output
Java
Output:

Loading component...

Loading component...