1648. Sell Diminishing-Valued Colored Balls
Problem Description
In this LeetCode problem, we are given an inventory of colored balls represented by an integer array where inventory[i]
is the number of balls of the i-th
color. A customer is interested in purchasing a total of orders
balls, which could be of any color.
The customer's payment is equal to the current quantity of the balls of that color in the inventory at the time of sale, which means the price for each ball decreases by one after each sale. The goal is to maximize the total earnings from selling exactly orders
balls. After selling the balls, if the total earnings are very large, we only need to return the result modulo 10^9 + 7
.
The main challenge of this problem is to determine in which order we should sell the balls to maximize the total value received, knowing that the value drops as we sell more balls of the same color.
Intuition
For maximizing the profit, we should start selling the balls with the highest count first because they are the most valuable. In other words, we sell the balls from the highest value and move towards the lower ones, as selling higher count balls will yield a higher profit per ball, and the value drops with each sale.
The solution uses a greedy approach combined with sorting. Here is the intuition:
- Sort the inventory in descending order so that we can process the most valuable balls first.
- Process the inventory in groups. If multiple colors have the same count, they form one group. The value decreases by the number of colors that were processed together because they all drop to the next lower value, creating a 'tier' system.
- Calculate the sales in tiers. If we can sell all the balls to reach the next lower tier without exceeding
orders
, we do so and calculate the profit for these balls using the arithmetic series formula. - In case selling all the balls in the current tier would exceed
orders
, we calculate how many times we can decrease the entire tier to sell the exact number oforders
left. We use the full tier decrement sales along with the remainder that cannot form a full tier. - Update the remaining
orders
and continue the process until we sell allorders
balls. - Since the result could become quite large, we take the modulo of the total profit after each addition with
10^9 + 7
to keep the number within the integer range. This approach ensures that we always have a valid integer profit value during the calculations.
This greedy approach works optimally since we are always choosing the highest value option available at each step, ensuring that the sum of the values we choose is maximal in the end.
Learn more about Greedy, Math, Binary Search, Sorting and Heap (Priority Queue) patterns.
Solution Approach
Given the intuition behind the problem, the solution code can be broken down to highlight the use of algorithms, data structures, and programming patterns that contribute to the solution. Let's step through each part of the code to understand its functionality in the context of the solution:
-
First, the inventory is sorted in descending order using
inventory.sort(reverse=True)
. This is done so that we can access the most valuable balls first. -
Two variables are initialized:
ans
to keep track of the total value obtained from selling the balls, andi
to keep count of the number of different ball colors processed in each tier. -
A
mod
variable is defined with the value10**9 + 7
for taking the modulo of the result, which is a common step in algorithm problems to prevent integer overflow issues. -
A while loop begins, which continues until the number of orders drops to 0. The orders represent the total number of balls the customer wants to purchase, which decrement as we process the sales.
-
Inside the loop, a nested loop counts how many ball colors are in the current tier (
while i < n and inventory[i] >= inventory[0]:
). That is, it identifies how many different colors have the same number of balls as the first (currently most) count. -
nxt
andcnt
are then set to find the next lower tier count (nxt = inventory[i]
) if there is any, and the count of colors in the current tier (cnt = i
). -
We then calculate how many full tiers (
x = inventory[0] - nxt
) we can sell without exceeding theorders
and the total count of balls that selling the full tiers would account for (tot = cnt * x
). -
The if-else block serves to check whether we can sell entire tiers (if
tot <= orders
) or if we have to calculate the remaining orders for a partial tier (iftot > orders
). -
If
tot > orders
, we calculate the decrements needed to fulfill the orders (decr = orders // cnt
) and use the formula for the sum of an arithmetic series ((a1 + an) * decr // 2 * cnt
) to calculate the revenue for sellingdecr
amount of balls for each color, plus any remaining ((inventory[0] - decr) * (orders % cnt)
). -
If
tot <= orders
, the revenue is similarly added using the arithmetic series sum formula, but for the fullx
amount. -
After each sale,
orders
is decremented by the number sold (orders -= tot
), andans
is updated with the revenue obtained from the last tier sold, modulomod
. -
Finally, after the loop ends with no more orders to process,
return ans
gives us the maximum total value that can be attained from sellingorders
colored balls.
The use of sorting, greedy approach, arithmetic series sum calculation, and modulo for handling large numbers are key components of the solution. Together, they provide an efficient and optimized way to obtain the maximum profit from the sale of colored balls.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example. Suppose we have an inventory of colored balls represented by the array inventory = [5, 4, 3]
, and we have a customer who wants to purchase orders = 7
balls.
Here's the walkthrough:
-
The inventory array is
[5, 4, 3]
. We sort it in descending order (but it's already sorted in this example), and it doesn't change:sorted_inventory = [5, 4, 3]
. -
Initialize
ans = 0
, as we haven't sold any balls yet. We also have ourmod = 10^9 + 7
for later modulo operations. -
Now we sell the balls in tiers, starting with the largest number of balls. Our first group is just the first color since 5 is the highest and unique count.
-
We can't decrease the entire tier from 5 to 4 by selling all
orders
because we only have 7 orders, and there are 5 balls in the first color. We calculate how many balls we can sell from this tier. We can decrease the number from 5 to 3 by sellingcount = 2
balls of this color (as sellingcount = 2
for each of the 5 balls would amount to 10, exceeding the 7 orders we have). -
The total revenue for selling these balls would be
(5 + 4) * 2 / 2 = 9
. We add this toans
, accounting for our modulo:ans = (ans + 9) % mod
. -
We update our orders to
orders -= count
, which is noworders = 7 - 2 = 5
. The inventory updates to[3, 4, 3]
, as we've sold 2 balls from the first color. -
We then proceed to the next tier. Now we have 2 groups of balls, both with the count of 4 (second and third color). We check if we can sell all balls from the highest count to reach the next lower count without exceeding the remaining orders. Since we have 2 colors with 4 balls, we could sell
2 * (4 - 3) = 2
balls to get down to the next tier without exceedingorders = 5
. -
We calculate the profit by selling these 2 balls with the value of 4, so we make
(4 + 3) * 2 / 2 = 7
. Again adjustans
andorders
.ans = (ans + 7) % mod
andorders = 5 - 2 = 3
. -
Now our inventory is
[3, 3, 3]
andorders = 3
. We proceed with selling the remaining 3 balls from one of the tiers valued at 3, since all counts are equal and we can choose any. We make(3 + 3 + 3) = 9
in revenue. -
Finally,
ans = (ans + 9) % mod
with no orders left.
In conclusion, the maximum total value attained from selling orders = 7
balls from the inventory [5, 4, 3]
is ans
, which is the sum of the revenues from each sale: 25
, given the modulo (10^9 + 7)
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def maxProfit(self, inventory: List[int], orders: int) -> int:
5 # Sort inventory in non-increasing order
6 inventory.sort(reverse=True)
7
8 # Define the modulo for result to avoid large numbers
9 mod = 10**9 + 7
10
11 # Initialize variables for profit and index
12 profit = 0
13 index = 0
14
15 # Length of inventory list
16 num_items = len(inventory)
17
18 # Continue until all orders are fulfilled
19 while orders > 0:
20 # Find a batch of same-valued items at the front of the sorted inventory
21 while index < num_items and inventory[index] == inventory[0]:
22 index += 1
23
24 # Find next distinct value in inventory after the batch or zero if at the end
25 next_value = inventory[index] if index < num_items else 0
26
27 # Number of items having the same value as the front of inventory
28 batch_size = index
29
30 # How many steps we can take till next distinct value (or to 0 if at the end)
31 steps_to_next_value = inventory[0] - next_value
32
33 # Total number of items we can potentially sell in this step
34 total_items_sellable = batch_size * steps_to_next_value
35
36 # If we can't fulfill all the remaining orders in this step
37 if total_items_sellable > orders:
38 # Calculate the number of full batches we can sell
39 full_batch_count = orders // batch_size
40
41 # Profit calculation for the full batches
42 first_item_price = inventory[0] - full_batch_count + 1
43 last_item_price = inventory[0]
44 profit += (first_item_price + last_item_price) * full_batch_count // 2 * batch_size
45
46 # Profit calculation for the remaining items in the last batch
47 profit += (inventory[0] - full_batch_count) * (orders % batch_size)
48 else:
49 # Profit calculation when we can sell all items in this step
50 first_item_price = next_value + 1
51 last_item_price = inventory[0]
52 profit += (first_item_price + last_item_price) * steps_to_next_value // 2 * batch_size
53
54 # Update the value of the first item in inventory
55 inventory[0] = next_value
56
57 # Deduct the number of orders fulfilled in this step
58 orders -= total_items_sellable
59
60 # Ensure the profit is within the modulo result
61 profit %= mod
62
63 # Return the total profit after processing all orders
64 return profit
65
1class Solution {
2
3 // Define the modulo constant as per the problem statement
4 private static final int MOD = (int) 1e9 + 7;
5
6 // Calculate the maximum profit given inventory levels and number of orders
7 public int maxProfit(int[] inventory, int orders) {
8 // Sort the inventory in ascending order
9 Arrays.sort(inventory);
10 int n = inventory.length;
11
12 // Reverse the array to have it in descending order
13 for (int i = 0, j = n - 1; i < j; ++i, --j) {
14 int temp = inventory[i];
15 inventory[i] = inventory[j];
16 inventory[j] = temp;
17 }
18
19 long totalProfit = 0; // The total profit accumulated
20 int i = 0; // Index to track current position in inventory array
21 while (orders > 0) {
22 while (i < n && inventory[i] >= inventory[0]) {
23 ++i;
24 }
25 int nextHighest = i < n ? inventory[i] : 0;
26 int count = i; // Number of items at the current price to sell
27
28 // Calculate the difference between the current and next item price levels
29 long stepsToNext = inventory[0] - nextHighest;
30 long potentialOrders = count * stepsToNext; // Potential number of orders to fulfill
31
32 if (potentialOrders > orders) {
33 // Calculate number of full price levels we can sell
34 int decrement = orders / count;
35 // Calculate the first and last term of the arithmetic series
36 long firstTerm = inventory[0] - decrement + 1;
37 long lastTerm = inventory[0];
38 // Add the contribution of full price levels to total profit
39 totalProfit += (firstTerm + lastTerm) * decrement / 2 * count;
40 // Add the remainder at the next price level
41 totalProfit += (firstTerm - 1) * (orders % count);
42 } else {
43 // Sell all items down to the next price level
44 long firstTerm = nextHighest + 1;
45 long lastTerm = inventory[0];
46 // Add the profit from selling down to the next level
47 totalProfit += (firstTerm + lastTerm) * stepsToNext / 2 * count;
48 inventory[0] = nextHighest;
49 }
50 // Remove the processed orders
51 orders -= potentialOrders;
52 // Ensure the profit is within the bounds of the modulo
53 totalProfit %= MOD;
54 }
55 // Return the total profit modulo the defined constant
56 return (int) totalProfit;
57 }
58}
59
1class Solution {
2public:
3 int maxProfit(vector<int>& inventory, int orders) {
4 // Initialize variables
5 long long totalProfit = 0; // Use long long for larger range
6 const int MOD = 1e9 + 7;
7 int currentMaxIndex = 0; // Tracks index of current maximum balls
8 int inventorySize = inventory.size();
9
10 // Sort the inventory in descending order to use a greedy approach
11 sort(inventory.rbegin(), inventory.rend());
12
13 // Continue until all orders are filled
14 while (orders > 0) {
15 // Find the index up to which the balls have the same number as the first element
16 while (currentMaxIndex < inventorySize &&
17 inventory[currentMaxIndex] >= inventory[0]) {
18 ++currentMaxIndex;
19 }
20
21 // Determine the next value (nxt) after the current maximum group of balls, or default to zero
22 int nextValue = currentMaxIndex < inventorySize ? inventory[currentMaxIndex] : 0;
23 int count = currentMaxIndex; // The number of balls with the current maximum number
24 long long step = inventory[0] - nextValue; // Number of steps to equalize the next value
25 long long totalSteps = count * step; // Total operations to perform
26
27 if (totalSteps > orders) {
28 // If the total steps exceed the number of orders, calculate and update profit
29 long long decreaseQuantity = orders / count;
30 long long firstTerm = inventory[0] - decreaseQuantity + 1;
31 long long lastTerm = inventory[0];
32 totalProfit += (firstTerm + lastTerm) * decreaseQuantity / 2 * count;
33 totalProfit += (firstTerm - 1) * (orders % count); // Add the rest of the balls
34 } else {
35 // Otherwise, update the profit and adjust the max value in inventory
36 long long firstTerm = nextValue + 1;
37 long long lastTerm = inventory[0];
38 totalProfit += (firstTerm + lastTerm) * step / 2 * count; // Full layer profit
39 inventory[0] = nextValue;
40 }
41
42 // Decrease the number of orders left and keep total profit within MOD
43 orders -= totalSteps;
44 totalProfit %= MOD;
45 }
46
47 // Return the result as an integer with applied modulo
48 return static_cast<int>(totalProfit);
49 }
50};
51
1const MOD: number = 1e9 + 7;
2
3// Utility function to sort an array in descending order.
4function sortDescending(arr: number[]): void {
5 arr.sort((a, b) => b - a);
6}
7
8// This function calculates the maximum profit that can be made by selling 'orders'.
9function maxProfit(inventory: number[], orders: number): number {
10 let totalProfit: bigint = BigInt(0); // Use bigint for larger range
11 let currentMaxIndex: number = 0; // Tracks index of current maximum balls
12 let inventorySize: number = inventory.length;
13
14 // Sort the inventory in descending order to use a greedy approach
15 sortDescending(inventory);
16
17 // Continue until all orders are filled
18 while (orders > 0) {
19 // Find the index up to which the balls have the same number as the first element
20 while (currentMaxIndex < inventorySize &&
21 inventory[currentMaxIndex] >= inventory[0]) {
22 currentMaxIndex++;
23 }
24
25 // Determine the next value after the current maximum group of balls, or default to zero
26 let nextValue: number = currentMaxIndex < inventorySize ? inventory[currentMaxIndex] : 0;
27 let count: number = currentMaxIndex; // The number of balls with the current maximum number
28 let step: bigint = BigInt(inventory[0] - nextValue); // Number of steps to equalize the next value
29 let totalSteps: bigint = BigInt(count) * step; // Total operations to perform
30
31 if (totalSteps > BigInt(orders)) {
32 // If the total steps exceed the number of orders, calculate and update profit
33 let decreaseQuantity: bigint = BigInt(orders / count);
34 let firstTerm: bigint = BigInt(inventory[0]) - decreaseQuantity + BigInt(1);
35 let lastTerm: bigint = BigInt(inventory[0]);
36 totalProfit += (firstTerm + lastTerm) * decreaseQuantity / BigInt(2) * BigInt(count);
37 totalProfit += (firstTerm - BigInt(1)) * BigInt(orders % count); // Add the rest of the balls
38 orders = 0; // All orders are fulfilled
39 } else {
40 // Otherwise, update the profit and adjust the max value in inventory
41 let firstTerm: bigint = BigInt(nextValue + 1);
42 let lastTerm: bigint = BigInt(inventory[0]);
43 totalProfit += (firstTerm + lastTerm) * step / BigInt(2) * BigInt(count); // Full layer profit
44 inventory[0] = nextValue;
45 orders -= Number(totalSteps);
46 }
47
48 // Keep total profit within MOD
49 totalProfit %= BigInt(MOD);
50 }
51
52 // Return the result as an integer with applied modulo
53 return Number(totalProfit % BigInt(MOD));
54}
55
Time and Space Complexity
Time Complexity
The time complexity of the provided code can be analyzed in the following parts:
- Sorting the inventory: The sort operation in Python uses the Timsort algorithm, which has a time complexity of
O(n log n)
, wheren
is the length of the inventory list. - The main
while
loop: This loop continues until the number of ordersorders
reaches 0. In the worst case, the loop will iteratek
times wherek
is the number of different values in the sorted inventory. Within the loop, there is a nestedwhile
loop that could technically iterate up ton
times, but only does so once just after the inventory is sorted to find the countcnt
of the highest-value balls that can be sold. Post the first iteration,i
will be at least1
and further iterations of the outer loop will only involve constant time checks, without further linear passes. - Calculation and summation steps within the loop: These involve constant time arithmetic operations, depending on the values of
inventory[0]
andnxt
.
Considering the while
loop iterates at most k
times without further nested linear passes after the initial sort, the time complexity of this part is nearly O(k)
(assuming the inner loop contributes constant time per outer iteration after the first).
Putting it together, the overall time complexity of the algorithm is O(n log n + k)
, bearing in mind that k <= n
.
Space Complexity
The space complexity of the code includes the following:
- The sorted inventory list: In-place sorting is used, hence no additional space complexity is added by the sort itself.
- Variables for intermediate calculations:
mod
,ans
,i
,n
,nxt
,cnt
,x
,tot
,decr
,a1
, andan
are all constant-sized integers, and their space requirements do not scale with the input size.
Therefore, the overall space complexity is O(1)
, which stands for constant space complexity aside from the input.
Learn more about how to find time and space complexity quickly using problem constraints.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.