1648. Sell Diminishing-Valued Colored Balls

MediumGreedyArrayMathBinary SearchSortingHeap (Priority Queue)
Leetcode Link

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:

  1. Sort the inventory in descending order so that we can process the most valuable balls first.
  2. 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.
  3. 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.
  4. 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 of orders left. We use the full tier decrement sales along with the remainder that cannot form a full tier.
  5. Update the remaining orders and continue the process until we sell all orders balls.
  6. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

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, and i to keep count of the number of different ball colors processed in each tier.

  • A mod variable is defined with the value 10**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 and cnt 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 the orders 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 (if tot > 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 selling decr 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 full x amount.

  • After each sale, orders is decremented by the number sold (orders -= tot), and ans is updated with the revenue obtained from the last tier sold, modulo mod.

  • Finally, after the loop ends with no more orders to process, return ans gives us the maximum total value that can be attained from selling orders 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Example 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:

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

  2. Initialize ans = 0, as we haven't sold any balls yet. We also have our mod = 10^9 + 7 for later modulo operations.

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

  4. 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 selling count = 2 balls of this color (as selling count = 2 for each of the 5 balls would amount to 10, exceeding the 7 orders we have).

  5. The total revenue for selling these balls would be (5 + 4) * 2 / 2 = 9. We add this to ans, accounting for our modulo: ans = (ans + 9) % mod.

  6. We update our orders to orders -= count, which is now orders = 7 - 2 = 5. The inventory updates to [3, 4, 3], as we've sold 2 balls from the first color.

  7. 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 exceeding orders = 5.

  8. We calculate the profit by selling these 2 balls with the value of 4, so we make (4 + 3) * 2 / 2 = 7. Again adjust ans and orders. ans = (ans + 7) % mod and orders = 5 - 2 = 3.

  9. Now our inventory is [3, 3, 3] and orders = 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.

  10. 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
Not Sure What to Study? Take the 2-min Quiz：

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Time and Space Complexity

Time Complexity

The time complexity of the provided code can be analyzed in the following parts:

  1. Sorting the inventory: The sort operation in Python uses the Timsort algorithm, which has a time complexity of O(n log n), where n is the length of the inventory list.
  2. The main while loop: This loop continues until the number of orders orders reaches 0. In the worst case, the loop will iterate k times where k is the number of different values in the sorted inventory. Within the loop, there is a nested while loop that could technically iterate up to n times, but only does so once just after the inventory is sorted to find the count cnt of the highest-value balls that can be sold. Post the first iteration, i will be at least 1 and further iterations of the outer loop will only involve constant time checks, without further linear passes.
  3. Calculation and summation steps within the loop: These involve constant time arithmetic operations, depending on the values of inventory[0] and nxt.

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:

  1. The sorted inventory list: In-place sorting is used, hence no additional space complexity is added by the sort itself.
  2. Variables for intermediate calculations: mod, ans, i, n, nxt, cnt, x, tot, decr, a1, and an 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.

Fast Track Your Learning with Our Quick Skills Quiz:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 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 When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Math Basics

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

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 Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫