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 _themaximum total value that you can attain after selling _orders colored balls. As the answer may be too large, return it modulo109 + 7.

Examples

Example 1

1
2
3
4
5
6
7


![](https://assets.leetcode.com/uploads/2020/11/05/jj.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

1
2
3
4

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^5
  • 1 <= inventory[i] <= 10^9
  • 1 <= orders <= min(sum(inventory[i]), 109)

Solution

Method 1 - Greedy with Sorting or Heap

Intuition

To maximize the total value, always sell the highest-valued balls first. As you sell a ball of a color, its value decreases by 1. This is a greedy problem: always pick the color with the most balls left. We can use a max-heap or sort the inventory and process in batches.

Approach

  1. Sort the inventory in descending order and append a zero at the end for easier processing.
  2. For each unique value, process all colors at that value down to the next lower value, or until orders run out.
  3. For each batch, calculate the sum using the arithmetic progression formula.
  4. Use modulo 1e9+7 for the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int maxProfit(vector<int>& inventory, int orders) {
        const int MOD = 1e9+7;
        sort(inventory.rbegin(), inventory.rend());
        inventory.push_back(0);
        long res = 0;
        int n = inventory.size();
        for (int i = 0, k = 1; orders > 0 && i < n-1; ++i, ++k) {
            if (inventory[i] > inventory[i+1]) {
                long cnt = (long)(inventory[i] - inventory[i+1]) * k;
                long take = min((long)orders, cnt);
                long full = take / k, rem = take % k;
                res = (res + k * (inventory[i] + inventory[i] - full + 1) * full / 2) % MOD;
                res = (res + rem * (inventory[i] - full)) % MOD;
                orders -= take;
            }
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

import "sort"
func maxProfit(inventory []int, orders int) int {
    const MOD = 1_000_000_007
    sort.Sort(sort.Reverse(sort.IntSlice(inventory)))
    inventory = append(inventory, 0)
    res := 0
    k := 1
    for i := 0; orders > 0 && i < len(inventory)-1; i, k = i+1, k+1 {
        if inventory[i] > inventory[i+1] {
            cnt := (inventory[i] - inventory[i+1]) * k
            take := min(orders, cnt)
            full, rem := take/k, take%k
            res = (res + k*(sumAP(inventory[i], inventory[i]-full+1, full))%MOD) % MOD
            res = (res + rem*(inventory[i]-full)%MOD) % MOD
            orders -= take
        }
    }
    return res
}
func sumAP(a, b, n int) int { return (a + b) * n / 2 }
func min(a, b int) int { if a < b { return a } else { return b } }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.*;
class Solution {
    public int maxProfit(int[] inventory, int orders) {
        final int MOD = 1_000_000_007;
        Arrays.sort(inventory);
        int n = inventory.length;
        long res = 0;
        int k = 1;
        for (int i = n-1; orders > 0; --i, ++k) {
            int cur = inventory[i], next = i > 0 ? inventory[i-1] : 0;
            if (cur > next) {
                long cnt = (long)(cur - next) * k;
                long take = Math.min(orders, (int)cnt);
                long full = take / k, rem = take % k;
                res = (res + k * (cur + cur - full + 1) * full / 2) % MOD;
                res = (res + rem * (cur - full)) % MOD;
                orders -= take;
            }
        }
        return (int)res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    fun maxProfit(inventory: IntArray, orders: Int): Int {
        val MOD = 1_000_000_007
        inventory.sortDescending()
        val inv = inventory + 0
        var res = 0L
        var k = 1
        var o = orders
        for (i in 0 until inv.size-1) {
            if (inv[i] > inv[i+1]) {
                val cnt = (inv[i] - inv[i+1]) * k
                val take = minOf(o, cnt)
                val full = take / k
                val rem = take % k
                res = (res + k * (inv[i] + inv[i] - full + 1) * full / 2) % MOD
                res = (res + rem * (inv[i] - full)) % MOD
                o -= take
            }
            k++
            if (o == 0) break
        }
        return res.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def maxProfit(inventory, orders):
    MOD = 10**9 + 7
    inventory.sort(reverse=True)
    inventory.append(0)
    res = 0
    k = 1
    for i in range(len(inventory)-1):
        if inventory[i] > inventory[i+1]:
            cnt = (inventory[i] - inventory[i+1]) * k
            take = min(orders, cnt)
            full, rem = divmod(take, k)
            res = (res + k * (inventory[i] + inventory[i] - full + 1) * full // 2) % MOD
            res = (res + rem * (inventory[i] - full)) % MOD
            orders -= take
            if orders == 0:
                break
        k += 1
    return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

pub fn max_profit(mut inventory: Vec<i32>, mut orders: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    inventory.sort_unstable_by(|a, b| b.cmp(a));
    inventory.push(0);
    let mut res = 0i64;
    let mut k = 1;
    for i in 0..inventory.len()-1 {
        if inventory[i] > inventory[i+1] {
            let cnt = (inventory[i] - inventory[i+1]) as i64 * k;
            let take = (orders as i64).min(cnt);
            let full = take / k;
            let rem = take % k;
            res = (res + k * (inventory[i] as i64 + inventory[i] as i64 - full + 1) * full / 2) % MOD;
            res = (res + rem * (inventory[i] as i64 - full)) % MOD;
            orders -= take as i32;
            if orders == 0 { break; }
        }
        k += 1;
    }
    res as i32
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

function maxProfit(inventory: number[], orders: number): number {
    const MOD = 1e9 + 7;
    inventory.sort((a, b) => b - a);
    inventory.push(0);
    let res = 0;
    let k = 1;
    for (let i = 0; i < inventory.length-1 && orders > 0; ++i, ++k) {
        if (inventory[i] > inventory[i+1]) {
            let cnt = (inventory[i] - inventory[i+1]) * k;
            let take = Math.min(orders, cnt);
            let full = Math.floor(take / k), rem = take % k;
            res = (res + k * (inventory[i] + inventory[i] - full + 1) * full / 2) % MOD;
            res = (res + rem * (inventory[i] - full)) % MOD;
            orders -= take;
        }
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(n log n) (for sorting, n = inventory.length)
  • 🧺 Space complexity: O(1) (in-place, except for the sort)