# Sell Diminishing-Valued Colored Balls
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sell-diminishing-valued-colored-balls)
Canonical: https://scaleengineer.com/dsa/problems/sell-diminishing-valued-colored-balls
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [MathWorks](https://scaleengineer.com/companies/mathworks), [Groupon](https://scaleengineer.com/companies/groupon)
---
## Problem
You have an `inventory` of different colored balls, and there is a customer that wants `orders` balls of **any** color.

The customer weirdly values the colored balls. Each colored ball's value is the number of balls **of that color** you currently have in your `inventory`. For example, if you own `6` yellow balls, the customer would pay `6` for the first yellow ball. After the transaction, there are only `5` yellow balls left, so the next yellow ball is then valued at `5` (i.e., the value of the balls decreases as you sell more to the customer).

You are given an integer array, `inventory`, where `inventory[i]` represents the number of balls of the `ith` color that you initially own. You are also given an integer `orders`, which represents the total number of balls that the customer wants. You can sell the balls **in any order**.

Return _the **maximum** total value that you can attain after selling_ `orders` _colored balls_. As the answer may be too large, return it **modulo** `109 + 7`.

**Example 1:**

![](https://assets.glich.co/dsa/sell-diminishing-valued-colored-balls/image0.gif) 

**Input:** inventory = [2,5], orders = 4
**Output:** 14
**Explanation:** Sell the 1st color 1 time (2) and the 2nd color 3 times (5 + 4 + 3).
The maximum total value is 2 + 5 + 4 + 3 = 14.

**Example 2:**

**Input:** inventory = [3,5], orders = 6
**Output:** 19
**Explanation:** Sell the 1st color 2 times (3 + 2) and the 2nd color 4 times (5 + 4 + 3 + 2).
The maximum total value is 3 + 2 + 5 + 4 + 3 + 2 = 19.

**Constraints:**

* `1 <= inventory.length <= 105`
* `1 <= inventory[i] <= 109`
* `1 <= orders <= min(sum(inventory[i]), 109)`

# Approaches
## Brute-force Simulation with Max-Heap
This approach uses a greedy strategy. To maximize the total profit, we should always sell the most valuable ball available at any given moment. The value of a ball is equal to the number of balls of that color currently in the inventory. Therefore, the most valuable ball is always from the color with the highest count.

A max-heap (implemented as a `PriorityQueue` in Java) is the ideal data structure to efficiently find the color with the most balls. We can simulate the selling process by repeatedly taking the largest element from the heap, adding its value to our profit, and inserting the decremented value back into the heap. We repeat this process `orders` times.
**Time:** O(orders * log N), where N is `inventory.length`. Building the heap takes O(N). Each of the `orders` sales involves a heap pop (O(log N)) and potentially a heap push (O(log N)). Since `orders` can be very large, this approach is too slow. · **Space:** O(N), where N is the number of colors (`inventory.length`). This space is required to store the counts in the max-heap.
**Pros:** The logic is simple and directly follows the greedy intuition.; It's easy to implement and understand.
**Cons:** The time complexity is directly proportional to `orders`, which can be up to 10^9. This makes the approach too slow for the given constraints and will result in a Time Limit Exceeded (TLE) error on most platforms.
### Explanation
The core idea is that to maximize profit, we must always sell the most expensive ball available. The value of a ball is determined by the number of balls of its color, so we should always sell from the color that has the largest number of balls.

A max-heap is the perfect data structure for this task as it allows O(log N) retrieval of the maximum element.

The algorithm proceeds as follows:
1.  Initialize a max-heap and insert all the ball counts from the `inventory` array.
2.  Initialize a variable `totalProfit` to 0.
3.  Loop `orders` times:
    a. Extract the maximum value (`currentMax`) from the heap.
    b. Add `currentMax` to `totalProfit`. Remember to use modulo arithmetic to prevent overflow.
    c. If `currentMax - 1` is greater than 0, insert this new decremented value back into the heap.

This process perfectly simulates selling the most valuable ball for each of the `orders`, but does so one by one.

```java
import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public int maxProfit(int[] inventory, int orders) {
        long MOD = 1_000_000_007;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int count : inventory) {
            maxHeap.add(count);
        }

        long totalProfit = 0;
        for (int i = 0; i < orders; i++) {
            if (maxHeap.isEmpty()) {
                break;
            }
            int currentMax = maxHeap.poll();
            totalProfit = (totalProfit + currentMax) % MOD;
            if (currentMax - 1 > 0) {
                maxHeap.add(currentMax - 1);
            }
        }
        return (int) totalProfit;
    }
}
```
### Algorithm
- Create a max-heap (Priority Queue in Java) and populate it with all the counts from the `inventory` array.
- Initialize a variable `totalProfit` to 0.
- Loop `orders` times:
  - Extract the maximum value (`currentMax`) from the heap.
  - Add `currentMax` to `totalProfit`, applying modulo arithmetic at each step.
  - If `currentMax - 1` is greater than 0, insert this new decremented value back into the heap.
- After the loop finishes, return the `totalProfit`.

## Optimized Greedy with Binary Search
This approach improves upon the simulation by not selling balls one by one. Instead of iterating `orders` times, we can determine the final state of the inventory more directly. The core idea is to find a "cutoff" value `k`. We will sell all balls that have a value greater than `k`, and then some balls with the value `k` until `orders` are fulfilled. This cutoff value `k` (the minimum price of a ball we sell) can be found efficiently using binary search, as the number of balls available to sell is a monotonic function of this minimum price.
**Time:** O(N * log M), where N is `inventory.length` and M is the maximum possible value in `inventory` (up to 10^9). The binary search takes `log M` steps, and each step requires iterating through the `N` items in the inventory. · **Space:** O(1) extra space.
**Pros:** Significantly more efficient than the simulation approach, avoiding TLE.; Does not require modifying the input array or using complex data structures besides basic variables.
**Cons:** The logic is more complex than the simulation approach.; For the given constraints, it can be slightly slower than the sorting approach because `log(max_inventory_value)` can be larger than `log(N)`.
### Explanation
We can observe that the number of balls we can sell is a monotonically decreasing function of the minimum price we are willing to accept. This property is key to using binary search.

We binary search for the minimum value `k` that any sold ball will have. The search space for `k` is from 1 to `max(inventory)`.

1.  **Binary Search:** Find the largest value `k` (let's call it `minPrice`) such that if we sell all balls with value `>= k`, the total number of balls sold is at least `orders`.
2.  **Calculate Profit:** Once we find this `minPrice`, we can calculate the total profit in two parts:
    a. **Profit from balls > minPrice:** Iterate through the inventory. For each color `i` where `inventory[i] > minPrice`, we sell `inventory[i] - minPrice` balls. The profit from this is the sum of an arithmetic series from `minPrice + 1` to `inventory[i]`. We sum this up for all applicable colors and count the number of balls sold.
    b. **Profit from balls == minPrice:** After the first step, we calculate how many more balls we need to sell to reach `orders`. These remaining balls are all sold at the price of `minPrice`.

The sum of an arithmetic series from `a` to `b` can be calculated efficiently. All calculations must use `long` to avoid overflow and handle modulo arithmetic correctly.

```java
class Solution {
    long MOD = 1_000_000_007;

    public int maxProfit(int[] inventory, int orders) {
        long low = 0, high = 1_000_000_001;
        long minPrice = 0;

        // Binary search for the minimum price 'k' of a sold ball
        while (low < high) {
            long mid = high - (high - low) / 2;
            if (canSell(inventory, orders, mid)) {
                minPrice = mid;
                low = mid;
            } else {
                high = mid - 1;
            }
        }

        // Calculate profit from balls with price > minPrice
        long profit = 0;
        long ordersSold = 0;
        for (long count : inventory) {
            if (count > minPrice) {
                ordersSold += (count - minPrice);
                profit = (profit + sumFrom(minPrice + 1, count)) % MOD;
            }
        }

        // Calculate profit from remaining balls sold at minPrice
        long remainingOrders = orders - ordersSold;
        profit = (profit + remainingOrders * minPrice) % MOD;

        return (int) profit;
    }

    // Checks if we can sell 'orders' balls if the minimum price is 'price'
    private boolean canSell(int[] inventory, int orders, long price) {
        if (price == 0) return true;
        long count = 0;
        for (long inv : inventory) {
            count += Math.max(0, inv - (price - 1));
        }
        return count >= orders;
    }

    // Calculates sum of arithmetic series from 'a' to 'b'
    private long sumFrom(long a, long b) {
        long count = b - a + 1;
        long term1 = a + b;
        long term2 = count;
        if (term1 % 2 == 0) {
            term1 /= 2;
        } else {
            term2 /= 2;
        }
        term1 %= MOD;
        term2 %= MOD;
        return (term1 * term2) % MOD;
    }
}
```
### Algorithm
- Define a helper function `canSell(price)` that calculates the total number of balls that can be sold if we only sell balls with a value of at least `price`. This is `sum(max(0, inv - (price-1)))` for all `inv` in `inventory`.
- The number of balls we can sell is a monotonically decreasing function of `price`. This allows us to use binary search.
- Binary search for the largest price `p` (let's call it `min_price`) for which `canSell(p)` returns true (i.e., we can sell at least `orders` balls).
- Once `min_price` is found, calculate the total profit in two parts:
  1. For every `inv > min_price`, we sell `inv - min_price` balls. Calculate the profit using the formula for an arithmetic series sum and add it to the total.
  2. Calculate how many orders remain. Sell these remaining balls at the price of `min_price`.
- Return the total profit modulo 10^9 + 7.

## Optimized Greedy with Sorting and Batching
This is a highly efficient greedy approach that processes sales in large batches or "layers". By sorting the inventory, we can easily identify the piles with the most balls. The core insight is that we will always sell balls from the current tallest piles until their height matches the next tallest pile. We can calculate the profit from selling this entire layer of balls in one go using an arithmetic series sum formula. This avoids the one-by-one simulation and the repeated scanning of the binary search approach.
**Time:** O(N log N), dominated by the initial sort of the inventory. The subsequent loop runs at most N times. · **Space:** O(1) or O(log N) depending on the space used by the in-place sorting algorithm.
**Pros:** Generally the most efficient solution for the given constraints.; Processes sales in large, aggregated batches, making it very fast.; The number of iterations is at most N, regardless of the size of `orders`.
**Cons:** The logic for handling layers and partial layers can be tricky to implement correctly, especially with the modulo arithmetic.; Requires sorting the input, which modifies the array or requires extra space for a copy.
### Explanation
This approach refines the greedy strategy by processing sales in groups. After sorting the inventory in descending order, we can think of the ball counts as bars in a histogram.

1.  **Sort:** Sort the `inventory` array. It's often easier to sort ascending and iterate from the end.
2.  **Process in Layers:** We iterate through the sorted array, grouping identical-sized inventories. Let's say we have `width` piles of size `current_val`, and the next largest size is `next_val`.
3.  **Calculate Batch Sale:** We can sell `diff = current_val - next_val` balls from each of the `width` piles before they all become size `next_val`. The total number of balls in this batch is `width * diff`.
4.  **Two Scenarios:**
    a. If we have enough `orders` to sell this entire batch, we calculate the profit using the arithmetic sum formula for `width` piles, update `orders`, and move to the next level. The `width` will increase as the piles of size `next_val` now join the top group.
    b. If `orders` is smaller than the batch size, we know the process ends here. We only need to sell the remaining `orders`. These are distributed as evenly as possible: we sell `orders / width` full layers from each of the `width` piles, and then `orders % width` individual balls from the top-most remaining layer. We calculate the profit for this final partial sale and we're done.

This method is very fast because it processes potentially huge numbers of sales in a few arithmetic operations.

```java
import java.util.Arrays;

class Solution {
    public int maxProfit(int[] inventory, int orders) {
        long MOD = 1_000_000_007;
        Arrays.sort(inventory);
        int n = inventory.length;
        long totalProfit = 0;
        long currentOrders = orders;
        long width = 0;

        for (int i = n - 1; i >= 0; i--) {
            width++;
            long currentVal = inventory[i];
            long nextVal = (i > 0) ? inventory[i - 1] : 0;
            long diff = currentVal - nextVal;

            if (diff == 0) {
                continue;
            }

            long ballsToSell = width * diff;

            if (currentOrders >= ballsToSell) {
                // Sell all balls in this layer
                long profit = sumFrom(nextVal + 1, currentVal);
                totalProfit = (totalProfit + width * profit) % MOD;
                currentOrders -= ballsToSell;
            } else {
                // Sell a partial layer
                long numFullLevels = currentOrders / width;
                long finalVal = currentVal - numFullLevels;
                long profit = sumFrom(finalVal + 1, currentVal);
                totalProfit = (totalProfit + width * profit) % MOD;

                long remainingBalls = currentOrders % width;
                totalProfit = (totalProfit + remainingBalls * finalVal) % MOD;
                
                currentOrders = 0; // All orders fulfilled
            }

            if (currentOrders == 0) {
                break;
            }
        }

        return (int) totalProfit;
    }

    // Calculates sum of arithmetic series from 'a' to 'b'
    private long sumFrom(long a, long b) {
        long count = b - a + 1;
        // sum = (a + b) * count / 2
        long term1 = a + b;
        long term2 = count;
        if (term1 % 2 == 0) {
            term1 /= 2;
        } else {
            term2 /= 2;
        }
        term1 %= MOD;
        term2 %= MOD;
        return (term1 * term2) % MOD;
    }
}
```
### Algorithm
- Sort the `inventory` array in ascending order.
- Append a conceptual 0 to the beginning of the array for easier boundary handling.
- Iterate from the largest element downwards. Keep track of `width`, the number of piles with the same current maximum height.
- In each step, consider the `current_val` and the `next_val` (the next smaller unique value).
- The number of balls we can sell to make the `width` piles equal to `next_val` is `width * (current_val - next_val)`.
- **Case 1: `orders` is large enough.** If we can sell all these balls, calculate the profit for this "layer", subtract the count from `orders`, and continue. The `width` increases as the next pile joins the top level.
- **Case 2: `orders` is not large enough.** We can't clear the whole layer. The remaining `orders` are distributed among the `width` piles. Calculate profit from selling `orders / width` full levels from each pile, and then `orders % width` individual balls from the next level down. Then terminate.

# Solutions
### Java

```java
class Solution {
private
  static final int MOD = (int)1 e9 + 7;
public
  int maxProfit(int[] inventory, int orders) {
    Arrays.sort(inventory);
    int n = inventory.length;
    for (int i = 0, j = n - 1; i < j; ++i, --j) {
      int t = inventory[i];
      inventory[i] = inventory[j];
      inventory[j] = t;
    }
    long ans = 0;
    int i = 0;
    while (orders > 0) {
      while (i < n && inventory[i] >= inventory[0]) {
        ++i;
      }
      int nxt = i < n ? inventory[i] : 0;
      int cnt = i;
      long x = inventory[0] - nxt;
      long tot = cnt * x;
      if (tot > orders) {
        int decr = orders / cnt;
        long a1 = inventory[0] - decr + 1, an = inventory[0];
        ans += (a1 + an) * decr / 2 * cnt;
        ans += (a1 - 1) * (orders % cnt);
      } else {
        long a1 = nxt + 1, an = inventory[0];
        ans += (a1 + an) * x / 2 * cnt;
        inventory[0] = nxt;
      }
      orders -= tot;
      ans %= MOD;
    }
    return (int)ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxProfit(vector<int> &inventory, int orders) {
    long ans = 0, mod = 1e9 + 7;
    int i = 0, n = inventory.size();
    sort(inventory.rbegin(), inventory.rend());
    while (orders > 0) {
      while (i < n && inventory[i] >= inventory[0]) {
        ++i;
      }
      int nxt = i < n ? inventory[i] : 0;
      int cnt = i;
      long x = inventory[0] - nxt;
      long tot = cnt * x;
      if (tot > orders) {
        int decr = orders / cnt;
        long a1 = inventory[0] - decr + 1, an = inventory[0];
        ans += (a1 + an) * decr / 2 * cnt;
        ans += (a1 - 1) * (orders % cnt);
      } else {
        long a1 = nxt + 1, an = inventory[0];
        ans += (a1 + an) * x / 2 * cnt;
        inventory[0] = nxt;
      }
      orders -= tot;
      ans %= mod;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxProfit(self, inventory: List[int], orders: int) -> int: inventory . sort(reverse=True) mod = 10 ** 9 + 7 ans = i = 0 n = len(inventory) while orders > 0: while i < n and inventory[i] >= inventory[0]: i += 1 nxt = 0 if i < n: nxt = inventory[i] cnt = i x = inventory[0] - nxt tot = cnt * x if tot > orders: decr = orders // cnt a1, an = inventory[0] - decr + 1, inventory[0] ans += (a1 + an) * decr // 2 * cnt ans += (inventory[0] - decr) * (orders % cnt) else: a1, an = nxt + 1, inventory[0] ans += (a1 + an) * x // 2 * cnt inventory[0] = nxt orders -= tot ans %= mod return ans

```