Code Implementation

from typing import List
import heapq

class Solution:
    def maxProfit(self, inventory: List[int], orders: int) -> int:
        MOD = 10**9 + 7
        # Use a max heap to always sell the most valuable ball
        inventory = [-x for x in inventory]
        heapq.heapify(inventory)
        result = 0
        
        while orders > 0:
            curr = -heapq.heappop(inventory)
            next_val = -inventory[0] if inventory else 0
            count = 1
            # Count how many balls have the same value
            while inventory and -inventory[0] == curr:
                heapq.heappop(inventory)
                count += 1
            sell = min(orders, count * (curr - next_val))
            full_rows = sell // count
            remain = sell % count
            result += count * (curr + curr - full_rows + 1) * full_rows // 2
            result += remain * (curr - full_rows)
            result %= MOD
            orders -= sell
            if curr - full_rows > 0:
                for _ in range(count):
                    heapq.heappush(inventory, -(curr - full_rows))
        return result
      

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int maxProfit(vector<int>& inventory, int orders) {
        const int MOD = 1e9 + 7;
        priority_queue<int> pq;
        for (int val : inventory) pq.push(val);
        long long res = 0;
        while (orders > 0) {
            int curr = pq.top(); pq.pop();
            int next = pq.empty() ? 0 : pq.top();
            int count = 1;
            // Count how many have the same value
            while (!pq.empty() && pq.top() == curr) {
                pq.pop();
                count++;
            }
            long long sell = min((long long)orders, (long long)count * (curr - next));
            long long full_rows = sell / count;
            long long remain = sell % count;
            res = (res + count * (curr + curr - full_rows + 1) * full_rows / 2) % MOD;
            res = (res + remain * (curr - full_rows)) % MOD;
            orders -= sell;
            if (curr - full_rows > 0) {
                for (int i = 0; i < count; ++i)
                    pq.push(curr - full_rows);
            }
        }
        return (int)res;
    }
};
      

import java.util.*;

class Solution {
    public int maxProfit(int[] inventory, int orders) {
        final int MOD = 1_000_000_007;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int val : inventory) pq.offer(val);
        long res = 0;
        while (orders > 0) {
            int curr = pq.poll();
            int next = pq.isEmpty() ? 0 : pq.peek();
            int count = 1;
            while (!pq.isEmpty() && pq.peek() == curr) {
                pq.poll();
                count++;
            }
            long sell = Math.min((long)orders, (long)count * (curr - next));
            long fullRows = sell / count;
            long remain = sell % count;
            res = (res + count * (curr + curr - fullRows + 1) * fullRows / 2) % MOD;
            res = (res + remain * (curr - fullRows)) % MOD;
            orders -= sell;
            if (curr - fullRows > 0) {
                for (int i = 0; i < count; ++i)
                    pq.offer(curr - (int)fullRows);
            }
        }
        return (int)res;
    }
}
      

/**
 * @param {number[]} inventory
 * @param {number} orders
 * @return {number}
 */
var maxProfit = function(inventory, orders) {
    const MOD = 1e9 + 7;
    inventory.sort((a, b) => b - a);
    inventory.push(0);
    let res = 0, i = 0, n = inventory.length;
    while (orders > 0) {
        while (inventory[i] === inventory[i+1]) i++;
        let cnt = i + 1;
        let sell = Math.min(orders, cnt * (inventory[i] - inventory[i+1]));
        let fullRows = Math.floor(sell / cnt);
        let remain = sell % cnt;
        res = (res + cnt * (inventory[i] + inventory[i] - fullRows + 1) * fullRows / 2) % MOD;
        res = (res + remain * (inventory[i] - fullRows)) % MOD;
        orders -= sell;
        inventory[i] -= fullRows;
        i = 0;
        inventory.sort((a, b) => b - a);
    }
    return res;
};
      

Problem Description

You are given an array inventory where each element represents the number of colored balls of a certain color, and an integer orders representing the total number of balls you must sell. Each time you sell a colored ball, you gain coins equal to the current number of balls of that color (i.e., the value of the ball decreases by 1 after each sale of that color). Your goal is to maximize the total number of coins you can obtain by selling exactly orders balls.

• You can sell any color at any time, but after selling, the value of that color's balls diminishes by 1.
• You must sell exactly orders balls.
• You cannot reuse or "restore" a ball's value once sold.
• Return the maximum coins you can collect, modulo 10^9 + 7.

Thought Process

At first glance, the brute-force approach would be to always pick the ball with the current highest value, sell it, decrease its value by 1, and repeat this process orders times. However, this is inefficient for large inputs, as it could require tens or hundreds of thousands of iterations.

To optimize, we notice that selling the highest-valued balls first always yields the most coins, and if multiple balls have the same value, we can process them in batches. Instead of selling one ball at a time, we can sell all balls of the highest value down to the next lower value in one step, using arithmetic sums to calculate the profit quickly.

This reduces the number of operations drastically and leverages the mathematical patterns in the diminishing values.

Solution Approach

• Step 1: Data Structure Choice
  To always access the highest valued balls efficiently, we use a max-heap (priority queue) or sort the inventory and process it in descending order.
• Step 2: Batch Processing
  Instead of selling one ball at a time, we process all balls at the current highest value together. If there are k colors with the same highest value, we can decrease all their values together down to the next highest value or as much as orders allows.
• Step 3: Calculating Profit Efficiently
  The profit from selling balls from value high down to low (exclusive) is the sum of an arithmetic sequence, which can be computed in O(1) time:
  • Sum = (high + low + 1) * (high - low) / 2 per color
• Step 4: Iterative Reduction
  After selling as many as possible at the current highest value, update the inventory (or heap) and repeat until all orders are fulfilled.
• Step 5: Modulo Operation
  Since the answer can be very large, take modulo 10^9 + 7 at each step.

Example Walkthrough

Suppose inventory = [2, 5] and orders = 4.

1. Start with values [5, 2]. The highest value is 5 (one ball). The next highest is 2.
2. We can sell the ball of value 5, earning 5 coins. Now inventory is [4, 2], orders left: 3.
3. Next, sell the ball of value 4, earning 4 coins. Now inventory is [3, 2], orders left: 2.
4. Now, both balls are at value 3 and 2. Sell the ball of value 3, earning 3 coins. Inventory: [2, 2], orders left: 1.
5. Finally, both balls are at value 2. Sell one, earning 2 coins. Orders left: 0.
6. Total coins earned: 5 + 4 + 3 + 2 = 14.

In the optimized approach, we would process the initial highest value (5) and calculate how many balls are at this value, then sell them down to the next value in bulk.

Time and Space Complexity

• Brute-force Approach:
  Each sale operation takes O(log n) time if using a heap, and we do this orders times.
  Time Complexity: O(orders * log n)
• Optimized Approach:
  We process in batches, reducing the number of iterations to at most the number of distinct values in inventory.
  Time Complexity: O(n log n) for initial heap/sort, plus O(n log n) for batch processing.
• Space Complexity: O(n) for the heap or sorted array.

Summary

The key insight is to always sell the most valuable balls first, but process them in batches using arithmetic sums to avoid unnecessary iterations. Using a max-heap or sorting, we efficiently track the highest values and update the inventory. This approach leverages mathematical patterns and data structures for optimal performance, making it both elegant and efficient for large inputs.