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
- Every split has the same two unavoidable endpoints
weights[0]andweights[n-1], so they cancel in the difference. - Each interior cut between
iandi+1contributesweights[i] + weights[i+1]to the score. - Choosing
k - 1cuts means pickingk - 1of then - 1adjacent sums. - The maximum uses the
k - 1largest adjacent sums and the minimum uses thek - 1smallest; 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]andweights[-1]appear in every split, so they cancel and can be ignored. - Choosing
kcuts instead ofk - 1:kgroups need exactlyk - 1interior cuts. - Assuming
k == 1needs 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.