Sell Diminishing-Valued Colored Balls

Med

#1513Time: 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.2 companies

Patterns

Math Greedy

Algorithms

Binary Search Sorting

Data structures

Array Heap (Priority Queue)

Companies

MathWorks Groupon

Prompt

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 i^th 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 10⁹+ 7.

Example 1:

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 <= 10⁵
1 <= inventory[i] <= 10⁹
1 <= orders <= min(sum(inventory[i]), 10⁹)

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

Initialize a max-heap and insert all the ball counts from the inventory array.
Initialize a variable totalProfit to 0.
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.

1import java.util.Collections;2import java.util.PriorityQueue;3 4class Solution {5    public int maxProfit(int[] inventory, int orders) {6        long MOD = 1_000_000_007;7        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());8        for (int count : inventory) {9            maxHeap.add(count);10        }11 12        long totalProfit = 0;13        for (int i = 0; i < orders; i++) {14            if (maxHeap.isEmpty()) {15                break;16            }17            int currentMax = maxHeap.poll();18            totalProfit = (totalProfit + currentMax) % MOD;19            if (currentMax - 1 > 0) {20                maxHeap.add(currentMax - 1);21            }22        }23        return (int) totalProfit;24    }25}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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).

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.
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.

1class Solution {2    long MOD = 1_000_000_007;3 4    public int maxProfit(int[] inventory, int orders) {5        long low = 0, high = 1_000_000_001;6        long minPrice = 0;7 8        // Binary search for the minimum price 'k' of a sold ball9        while (low < high) {10            long mid = high - (high - low) / 2;11            if (canSell(inventory, orders, mid)) {12                minPrice = mid;13                low = mid;14            } else {15                high = mid - 1;16            }17        }18 19        // Calculate profit from balls with price > minPrice20        long profit = 0;21        long ordersSold = 0;22        for (long count : inventory) {23            if (count > minPrice) {24                ordersSold += (count - minPrice);25                profit = (profit + sumFrom(minPrice + 1, count)) % MOD;26            }27        }28 29        // Calculate profit from remaining balls sold at minPrice30        long remainingOrders = orders - ordersSold;31        profit = (profit + remainingOrders * minPrice) % MOD;32 33        return (int) profit;34    }35 36    // Checks if we can sell 'orders' balls if the minimum price is 'price'37    private boolean canSell(int[] inventory, int orders, long price) {38        if (price == 0) return true;39        long count = 0;40        for (long inv : inventory) {41            count += Math.max(0, inv - (price - 1));42        }43        return count >= orders;44    }45 46    // Calculates sum of arithmetic series from 'a' to 'b'47    private long sumFrom(long a, long b) {48        long count = b - a + 1;49        long term1 = a + b;50        long term2 = count;51        if (term1 % 2 == 0) {52            term1 /= 2;53        } else {54            term2 /= 2;55        }56        term1 %= MOD;57        term2 %= MOD;58        return (term1 * term2) % MOD;59    }60}

Complexity

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.

Trade-offs

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).

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.

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.

Walkthrough

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.

Sort: Sort the inventory array. It's often easier to sort ascending and iterate from the end.
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.
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.
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.

1import java.util.Arrays;2 3class Solution {4    public int maxProfit(int[] inventory, int orders) {5        long MOD = 1_000_000_007;6        Arrays.sort(inventory);7        int n = inventory.length;8        long totalProfit = 0;9        long currentOrders = orders;10        long width = 0;11 12        for (int i = n - 1; i >= 0; i--) {13            width++;14            long currentVal = inventory[i];15            long nextVal = (i > 0) ? inventory[i - 1] : 0;16            long diff = currentVal - nextVal;17 18            if (diff == 0) {19                continue;20            }21 22            long ballsToSell = width * diff;23 24            if (currentOrders >= ballsToSell) {25                // Sell all balls in this layer26                long profit = sumFrom(nextVal + 1, currentVal);27                totalProfit = (totalProfit + width * profit) % MOD;28                currentOrders -= ballsToSell;29            } else {30                // Sell a partial layer31                long numFullLevels = currentOrders / width;32                long finalVal = currentVal - numFullLevels;33                long profit = sumFrom(finalVal + 1, currentVal);34                totalProfit = (totalProfit + width * profit) % MOD;35 36                long remainingBalls = currentOrders % width;37                totalProfit = (totalProfit + remainingBalls * finalVal) % MOD;38                39                currentOrders = 0; // All orders fulfilled40            }41 42            if (currentOrders == 0) {43                break;44            }45        }46 47        return (int) totalProfit;48    }49 50    // Calculates sum of arithmetic series from 'a' to 'b'51    private long sumFrom(long a, long b) {52        long count = b - a + 1;53        // sum = (a + b) * count / 254        long term1 = a + b;55        long term2 = count;56        if (term1 % 2 == 0) {57            term1 /= 2;58        } else {59            term2 /= 2;60        }61        term1 %= MOD;62        term2 %= MOD;63        return (term1 * term2) % MOD;64    }65}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2private3  static final int MOD = (int)1 e9 + 7;4public5  int maxProfit(int[] inventory, int orders) {6    Arrays.sort(inventory);7    int n = inventory.length;8    for (int i = 0, j = n - 1; i < j; ++i, --j) {9      int t = inventory[i];10      inventory[i] = inventory[j];11      inventory[j] = t;12    }13    long ans = 0;14    int i = 0;15    while (orders > 0) {16      while (i < n && inventory[i] >= inventory[0]) {17        ++i;18      }19      int nxt = i < n ? inventory[i] : 0;20      int cnt = i;21      long x = inventory[0] - nxt;22      long tot = cnt * x;23      if (tot > orders) {24        int decr = orders / cnt;25        long a1 = inventory[0] - decr + 1, an = inventory[0];26        ans += (a1 + an) * decr / 2 * cnt;27        ans += (a1 - 1) * (orders % cnt);28      } else {29        long a1 = nxt + 1, an = inventory[0];30        ans += (a1 + an) * x / 2 * cnt;31        inventory[0] = nxt;32      }33      orders -= tot;34      ans %= MOD;35    }36    return (int)ans;37  }38}

1class Solution {2public:3  int maxProfit(vector<int> &inventory, int orders) {4    long ans = 0, mod = 1e9 + 7;5    int i = 0, n = inventory.size();6    sort(inventory.rbegin(), inventory.rend());7    while (orders > 0) {8      while (i < n && inventory[i] >= inventory[0]) {9        ++i;10      }11      int nxt = i < n ? inventory[i] : 0;12      int cnt = i;13      long x = inventory[0] - nxt;14      long tot = cnt * x;15      if (tot > orders) {16        int decr = orders / cnt;17        long a1 = inventory[0] - decr + 1, an = inventory[0];18        ans += (a1 + an) * decr / 2 * cnt;19        ans += (a1 - 1) * (orders % cnt);20      } else {21        long a1 = nxt + 1, an = inventory[0];22        ans += (a1 + an) * x / 2 * cnt;23        inventory[0] = nxt;24      }25      orders -= tot;26      ans %= mod;27    }28    return ans;29  }30};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2private3  static final int MOD = (int)1 e9 + 7;4public5  int maxProfit(int[] inventory, int orders) {6    Arrays.sort(inventory);7    int n = inventory.length;8    for (int i = 0, j = n - 1; i < j; ++i, --j) {9      int t = inventory[i];10      inventory[i] = inventory[j];11      inventory[j] = t;12    }13    long ans = 0;14    int i = 0;15    while (orders > 0) {16      while (i < n && inventory[i] >= inventory[0]) {17        ++i;18      }19      int nxt = i < n ? inventory[i] : 0;20      int cnt = i;21      long x = inventory[0] - nxt;22      long tot = cnt * x;23      if (tot > orders) {24        int decr = orders / cnt;25        long a1 = inventory[0] - decr + 1, an = inventory[0];26        ans += (a1 + an) * decr / 2 * cnt;27        ans += (a1 - 1) * (orders % cnt);28      } else {29        long a1 = nxt + 1, an = inventory[0];30        ans += (a1 + an) * x / 2 * cnt;31        inventory[0] = nxt;32      }33      orders -= tot;34      ans %= MOD;35    }36    return (int)ans;37  }38}

1class Solution {2public:3  int maxProfit(vector<int> &inventory, int orders) {4    long ans = 0, mod = 1e9 + 7;5    int i = 0, n = inventory.size();6    sort(inventory.rbegin(), inventory.rend());7    while (orders > 0) {8      while (i < n && inventory[i] >= inventory[0]) {9        ++i;10      }11      int nxt = i < n ? inventory[i] : 0;12      int cnt = i;13      long x = inventory[0] - nxt;14      long tot = cnt * x;15      if (tot > orders) {16        int decr = orders / cnt;17        long a1 = inventory[0] - decr + 1, an = inventory[0];18        ans += (a1 + an) * decr / 2 * cnt;19        ans += (a1 - 1) * (orders % cnt);20      } else {21        long a1 = nxt + 1, an = inventory[0];22        ans += (a1 + an) * x / 2 * cnt;23        inventory[0] = nxt;24      }25      orders -= tot;26      ans %= mod;27    }28    return ans;29  }30};

1class Solution:2    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

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.