Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

2681. Put Marbles in Bags

My accepted Python solution to LeetCode problem 2681, Put Marbles in Bags, running in 135ms.

  • Difficulty: Hard
  • Python
  • Runtime 135ms
  • Memory 28.4MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 135ms, memory 28.4MB, accepted 2025-12-31.

python
class Solution:
    def putMarbles(self, weights: List[int], k: int) -> int:
        n = len(weights)
        if k == 1 or k == n:
            return 0
        
        # Score = sum of (weights[i] + weights[j]) for each bag
        # where i is start and j is end of bag
        # When we split at position i, we add weights[i] + weights[i+1]
        # We need to choose k-1 split points
        
        # Calculate the contribution of each potential split point
        pairs = []
        for i in range(n - 1):
            pairs.append(weights[i] + weights[i + 1])
        
        pairs.sort()
        
        # For minimum score, choose k-1 smallest pairs
        # For maximum score, choose k-1 largest pairs
        min_score = sum(pairs[:k-1])
        max_score = sum(pairs[-(k-1):])
        
        return max_score - min_score

Source