LeetCode 1648 - Sell Diminishing-Valued Colored Balls

Difficulty: 🟡 Medium
Topics: Array, Math, Binary Search, Greedy, Sorting, Heap (Priority Queue)

Solution

Here is the complete, detailed technical solution guide for LeetCode 1648 - Sell Diminishing-Valued Colored Balls following your requested structure and formatting rules.

Problem Understanding

The problem asks us to sell orders number of balls from an inventory of different colored balls in a way that maximizes the total value obtained. Each ball has a diminishing value based on how many of that color remain. For example, if there are 5 balls of a color, the first one sold is worth 5, the next 4, and so on until the last ball of that color is worth 1.

The input consists of an array inventory where inventory[i] represents the number of balls of color i, and an integer orders representing how many balls the customer wants. The output is the maximum total value from selling exactly orders balls, modulo 10^9 + 7.

Constraints tell us the input can be large: up to 10^5 colors and ball counts up to 10^9. A naive approach iterating one ball at a time would be too slow, as orders could also be up to 10^9.

Key edge cases include selling fewer balls than the total inventory, having all balls of equal value, or very large numbers that risk integer overflow. The problem guarantees orders will always be valid, so we never sell more than we have.

Approaches

Brute Force Approach: The naive way is to repeatedly sell the ball with the highest current value. You could use a max-heap to always pick the largest available ball, decrement its count, and accumulate the value. While this gives the correct answer, it is far too slow for the constraints because each order operation could take O(log n) with a heap, leading to O(orders * log n) time, which is infeasible when orders can be 10^9.

Optimal Approach: A key observation is that the problem can be reduced to selling balls in blocks of equal values. We can sort the inventory in descending order and then determine how many balls we can sell at each "value level" efficiently. Instead of selling one by one, we calculate the total profit of selling a full value range from high to low using the arithmetic progression sum formula:

$$\text{sum} = \frac{(high + low + 1) * (high - low)}{2} * \text{count_of_colors}$$

This approach is greedy, always removing balls with the highest value first, and allows us to calculate sums in constant time for blocks. Sorting makes this O(n log n) for n colors.

Approach	Time Complexity	Space Complexity	Notes
Brute Force (Heap)	O(orders * log n)	O(n)	Sell one ball at a time using max-heap, too slow for large orders
Optimal (Sort + Greedy Math)	O(n log n)	O(1) or O(n)	Sell in value blocks, use arithmetic sum formula to compute efficiently

Algorithm Walkthrough

Sort the inventory in descending order so that the colors with the most balls are processed first. This ensures that the highest value balls are sold first.
Add a zero at the end of the sorted array as a sentinel to simplify calculations when processing the last value block.
Iterate through the inventory. At each step, calculate the difference diff = current_value - next_value. This represents the number of value levels we can sell for the current group of balls.
Compute how many balls we can sell from this block: count = diff * number_of_colors_at_this_level.
If orders >= count, sell all balls in this block using the arithmetic progression sum formula and decrement orders by count.
If orders < count, we cannot sell the entire block. Compute how many full value levels we can sell and handle any remaining balls individually.
Use modulo 10^9 + 7 for all accumulated sums to avoid overflow.
Continue until orders reaches zero.

Why it works: The greedy invariant is that selling the highest-valued balls first maximizes profit. By selling in blocks instead of individually, we ensure efficiency while preserving correctness.

Python Solution

from typing import List

class Solution:
    def maxProfit(self, inventory: List[int], orders: int) -> int:
        MOD = 10**9 + 7
        inventory.sort(reverse=True)
        inventory.append(0)  # sentinel
        profit = 0
        n = 1  # number of colors at current value
        
        for i in range(len(inventory) - 1):
            if inventory[i] > inventory[i + 1]:
                diff = inventory[i] - inventory[i + 1]
                total = diff * n
                if orders >= total:
                    # Sell full levels
                    profit += n * (inventory[i] + inventory[i + 1] + 1) * diff // 2
                    orders -= total
                else:
                    # Sell partial levels
                    full, remainder = divmod(orders, n)
                    profit += n * (2 * inventory[i] - full + 1) * full // 2
                    profit += remainder * (inventory[i] - full)
                    return profit % MOD
            n += 1
        
        return profit % MOD

Explanation: We sort the inventory descending and append zero for simplicity. We track how many colors share the current top value (n). For each block difference, if we can sell all balls, we use the arithmetic sum formula. If not, we compute how many full value levels and remaining balls to sell and return modulo 10^9 + 7.

Go Solution

package main

import "sort"

func maxProfit(inventory []int, orders int) int {
    const MOD = int(1e9 + 7)
    sort.Sort(sort.Reverse(sort.IntSlice(inventory)))
    inventory = append(inventory, 0)
    profit := 0
    n := 1 // number of colors at current level

    for i := 0; i < len(inventory)-1; i++ {
        if inventory[i] > inventory[i+1] {
            diff := inventory[i] - inventory[i+1]
            total := diff * n
            if orders >= total {
                profit += n * (inventory[i] + inventory[i+1] + 1) * diff / 2
                orders -= total
            } else {
                full := orders / n
                remainder := orders % n
                profit += n * (2*inventory[i] - full + 1) * full / 2
                profit += remainder * (inventory[i] - full)
                return profit % MOD
            }
        }
        n++
    }

    return profit % MOD
}

Go-specific notes: Go requires explicit sorting with sort.IntSlice and uses integer division carefully. Slices are used with append for sentinel, similar to Python.

Worked Examples

Example 1: inventory = [2,5], orders = 4

Sorted: [5,2,0]

Step 1: diff = 5-2=3, n=1, total=3. Orders=4 ≥ 3 → sell all 3 balls: profit += (5+3+1)*3/2 = 5+4+3=12, orders=1

Step 2: diff = 2-0=2, n=2, total=4. Orders=1 < 4 → sell 0 full levels, remainder=1 → profit += remainder*(current_value)=1*2=2

Total profit=12+2=14

Example 2: inventory = [3,5], orders = 6

Sorted: [5,3,0]

Step 1: diff=5-3=2, n=1, total=2. Orders=6 ≥2 → profit += (5+4)*2/2=9, orders=4

Step 2: diff=3-0=3, n=2, total=6. Orders=4 < 6 → full=4/2=2, remainder=0 → profit += 2*(3+2)/2_2=2_(5)*2/2=10

Total profit=9+10=19

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates; iteration is O(n)
Space	O(1)	Extra space only for sentinel and counters; in Python list append is negligible

The arithmetic sum formula avoids iterating through each ball individually, which reduces complexity drastically.

Test Cases

# Basic examples
assert Solution().maxProfit([2,5], 4) == 14  # example 1
assert Solution().maxProfit([3,5], 6) == 19  # example 2

# Edge cases
assert Solution().maxProfit([1], 1) == 1  # smallest possible input
assert Solution().maxProfit([1000000000], 1) == 1000000000  # very large ball count
assert Solution().maxProfit([1,1,1], 3) == 3  #