⚡Flashcard Drill➔
NeetCode #823LC-2551HardGreedy
← Back to All Problems

#823 · #2551 · Put Marbles in Bags(将珠子放入背包中)

📌 Problem Statement & Constraints

You are given an array weights and an integer k. Split the array into k contiguous groups; the score of a group is the sum of its first and last weight, and the total score is the sum over groups. Return the difference between the maximum and minimum possible total score. Constraints: 2 <= k <= weights.length <= 10^5, 1 <= weights[i] <= 10^9.

💡 Core Algorithmic Approaches

  1. Every split has the same two unavoidable endpoints weights[0] and weights[n-1], so they cancel in the difference.
  2. Each interior cut between i and i+1 contributes weights[i] + weights[i+1] to the score.
  3. Choosing k - 1 cuts means picking k - 1 of the n - 1 adjacent sums.
  4. The maximum uses the k - 1 largest adjacent sums and the minimum uses the k - 1 smallest; their difference is the answer.

💻 Benchmark Python3 Implementation

class Solution:
    def putMarbles(self, weights: List[int], k: int) -> int:
        n = len(weights)
        if k == 1:
            return 0                        # only one split -> score is fixed
        pairs = [weights[i] + weights[i + 1] for i in range(n - 1)]
        pairs.sort()
        cuts = k - 1
        return sum(pairs[-cuts:]) - sum(pairs[:cuts])

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): sorting the adjacent sums dominates.
💾 Space Complexity
O(n): the list of adjacent sums.

⚠️ Interview Pitfalls & Follow-ups

  • Adding the global endpoints into the comparison: weights[0] and weights[-1] appear in every split, so they cancel and can be ignored.
  • Choosing k cuts instead of k - 1: k groups need exactly k - 1 interior cuts.
  • Assuming k == 1 needs special care: with one group the max and min coincide, so the difference is 0.
  • Trying to simulate all splits: the number of splits is exponential; the reduction to adjacent sums makes it a simple selection problem.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems