Skip to main content

Binary Search

Sell Diminishing-Valued Colored Balls Solution in C++/Java/Python/JS

Sell Diminishing-Valued Colored Balls-problem-description
Sell Diminishing-Valued Colored Balls-problem-description

Sell Diminishing-Valued Colored Balls Problem Description:

You have an inventory of different colored balls, and there is a customer that wants to order 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 10⁹ + 7.

Examples:

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.

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

Brute Force Approach

In this problem, we are given colored balls with different counts, and we want to sell orders number of balls while maximizing profit. The key observation is that the value of each ball decreases as we sell more of that color. Our goal is to always sell the most valuable ball first to maximize profit.

Imagine you have different colored balls in your inventory, and a customer wants to buy a certain number of them. The catch is that the price of a ball depends on how many of that color are left. For example, if you have 5 balls of a certain color, the first one sells for 5 coins, the next for 4 coins, then 3 coins, and so on.

Naturally, if we want to maximize profit, we should always sell the most valuable ball first. This means that at each step, we should pick the color that has the most balls left because it gives us the highest price.

A naive approach would be to sort all the balls and iterate through them one by one, but that would be slow when we have millions of balls. Instead, we need a smart way to quickly find the most valuable ball at each step.

Since we always want to sell the ball that has the highest value (i.e., the one with the most remaining stock), we need a way to keep track of the largest ball count available.

At each step, let’s say we have a color with 5 balls remaining (meaning its current price is 5). After selling one ball, its price drops to 4, then to 3, and so on.

Now, let’s assume we also have another color with 3 balls remaining. This means that once we sell down our first color to 3, the next highest price will be 3.

So, instead of selling one ball at a time, we can sell all the balls at the highest price down to the next highest price in one go. This way, we process batches of balls efficiently.

To do this, we need to keep track of:

  1. Top Frequency (top) - The highest ball count (most valuable).
  2. Next Top Frequency (nextTop) - The second highest ball count (next most valuable).

By looking at top and nextTop, we can immediately determine how many balls we can sell at the current highest price before reaching the next highest price.

Since we always need to extract the highest remaining ball count and update it as we sell, a max-heap (priority queue) is the perfect data structure.

A priority queue (max-heap):

  • Always keeps the largest element on top, allowing us to efficiently access the highest-priced ball.
  • Removes the highest element in O(log N) time.
  • Lets us push updated values back efficiently in O(log N) time.

So, the idea is:

  1. Insert all ball counts into a max-heap (so that the largest count is always on top).
  2. Extract the top element (which is the most valuable ball).
  3. Find the next highest frequency (`nextTop).
  4. Sell all the balls from top down to nextTop .
  5. Update remaining orders and push back any leftover stock.
  6. Repeat until we’ve sold all orders.

How Do We Calculate Profit Efficiently?

At every step, we sell as many balls as possible at the current highest price before reaching the next highest price. Instead of processing each sale one by one, we use arithmetic sum formulas to compute profit in constant time.

Finding How Many Balls to Sell at a Time:

If our current highest frequency is top and the next highest frequency is nextTop, then the number of balls we can sell at this level is:

sellCount = min⁡(orders , top − nextTop + 1)

This tells us that we can sell all the balls from top down to nextTop before reaching the next lower value.

Computing the Profit Using Arithmetic Sum Formula:

When selling multiple balls at the same price level, the total profit is the sum of an arithmetic series:

∑ = n + (n−1) + (n−2) +⋯+ (n−k+1)

The formula for summing the first k terms of an arithmetic sequence is:

∑ = k × (top + (top − k + 1)) / 2

where:

  • top is the starting price.
  • k is the number of balls we are selling.
  • (top - k + 1) is the last ball’s price.

Using this formula, we efficiently calculate profit in O(1) time instead of looping through each sale.

💡
Try it Yourself!

Let's understand with an example:

Sell Diminishing-Valued Colored Balls Example:

Input: inventory = [2,5], orders = 4

We need to sell 4 balls while maximizing profit.

Step 1: Initialize the Max-Heap

Push all inventory values into a max-heap (priority queue).
pq = [5, 2] (largest on top)

Step 2: Start Processing Orders

  1. First Iteration
  • top = 5 (highest count)
  • nextTop = 2 (next highest count)
  • sellCount = min(4, (5 - 2 + 1)) = min(4, 4) = 4
  • Profit Calculation: sum = 4 × ( 5 + (5 − 4 + 1)) / 2 = 4 × (5 + 2) / 2 = 4 × 7/2 = 14
  • Add 14 to profit.
  • Orders left: 4 - 4 = 0
  • No need to push anything back into pq (all 5s are sold).

Final Answer:

Max Profit = 14

Steps to Implement the Solution:

  • Use a Max-Heap (Priority Queue)
    • This ensures we always sell balls from the highest inventory first.
  • Push All Inventory Counts into the Heap
    • Insert all elements of inventory into a max-heap.
  • Iterate Until Orders Are Fulfilled
    • Extract the highest inventory count (top).
    • Check the next highest count (nextTop) to determine how many balls can be sold at this price level.
  • Calculate Profit Efficiently
    • Use the arithmetic sum formula to compute profit from top down to top - sellCount + 1.
  • Update Remaining Orders
    • Deduct the sold balls from orders.
  • Push Remaining Inventory Back
    • If top - sellCount > 0, push the remaining count back into the heap.
  • Return the Total Profit
    • Apply modulo to prevent overflow and return the final computed profit.

Sell Diminishing-Valued Colored Balls Leetcode Solution

Sell Diminishing-Valued Colored Balls solution / Code Implementation
1. Sell Diminishing-Valued Colored Balls solution in C++ Try on Compiler 
class Solution {
public:
    int maxProfit(vector<int>& inventory, int orders) {
        // Max-heap (priority queue) to always fetch the highest inventory count first
        priority_queue<int> pq;
        
        // Modulo for large numbers and to prevent overflow
        long long mod = 1e9 + 7;
        
        // Variable to store the total profit
        long long profit = 0;
        
        // Push all inventory counts into the max-heap
        for (int count : inventory) {
            pq.push(count);
        }

        // Continue selling balls until all orders are fulfilled
        while (orders > 0) {
            // Get the highest available inventory count
            int top = pq.top();
            
            // Remove it from the heap since we are processing it
            pq.pop();
            
            // Get the next highest inventory count (or 0 if none left)
            int nextTop = pq.empty() ? 0 : pq.top();
            
            // Determine how many balls we can sell at the current price before reaching nextTop
            int sellCount = min(orders, top - nextTop + 1);

            // Compute the profit from selling balls from 'top' down to 'top - sellCount + 1'
            long long sum = (long long)(top + (top - sellCount + 1)) * sellCount / 2;
            
            // Add the computed profit to the total, applying modulo to prevent overflow
            profit = (profit + sum) % mod;

            // Reduce the number of remaining orders
            orders -= sellCount;

            // If there are remaining balls of this color, push the reduced count back into the heap
            if (top - sellCount > 0) {
                pq.push(top - sellCount);
            }
        }

        // Return the final computed profit
        return profit;
    }
};

2. Sell Diminishing-Valued Colored Balls solution in Java Try on Compiler 
import java.util.PriorityQueue;

class Solution {
    public int maxProfit(int[] inventory, int orders) {
        // Max-heap to always access the highest inventory count first
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        
        // Modulo for large numbers
        long mod = 1_000_000_007;
        
        // Variable to store total profit
        long profit = 0;
        
        // Add all inventory counts to the max-heap
        for (int count : inventory) {
            pq.add(count);
        }

        // Process orders until we run out
        while (orders > 0) {
            // Get the highest available inventory count
            int top = pq.poll();
            
            // Get the next highest inventory count or 0 if none left
            int nextTop = pq.isEmpty() ? 0 : pq.peek();
            
            // Determine how many balls we can sell at this price before reaching nextTop
            int sellCount = Math.min(orders, top - nextTop + 1);

            // Compute profit using arithmetic series sum formula
            long sum = (long) (top + (top - sellCount + 1)) * sellCount / 2;
            
            // Add computed profit, applying modulo to prevent overflow
            profit = (profit + sum) % mod;

            // Reduce remaining orders
            orders -= sellCount;

            // If there are remaining balls, push the reduced count back into the heap
            if (top - sellCount > 0) {
                pq.add(top - sellCount);
            }
        }

        // Return the final computed profit
        return (int) profit;
    }
}

3. Sell Diminishing-Valued Colored Balls solution in Python Try on Compiler 
import heapq

class Solution:
    def maxProfit(self, inventory, orders):
        
        # Max-heap (Python uses min-heap, so negate values to simulate max-heap)
        pq = [-count for count in inventory]
        heapq.heapify(pq)

        # Modulo for large numbers
        mod = 10**9 + 7
        
        # Variable to store total profit
        profit = 0

        # Process orders until fulfilled
        while orders > 0:
            # Get the highest available inventory count
            top = -heapq.heappop(pq)
            
            # Get the next highest inventory count (or 0 if none left)
            nextTop = -pq[0] if pq else 0
            
            # Determine how many balls we can sell at this price before reaching nextTop
            sellCount = min(orders, top - nextTop + 1)

            # Compute profit using arithmetic series sum formula
            sum_profit = (top + (top - sellCount + 1)) * sellCount // 2
            
            # Add computed profit, applying modulo to prevent overflow
            profit = (profit + sum_profit) % mod

            # Reduce remaining orders
            orders -= sellCount

            # If there are remaining balls, push the reduced count back into the heap
            if top - sellCount > 0:
                heapq.heappush(pq, -(top - sellCount))

        # Return the final computed profit
        return profit

4. Sell Diminishing-Valued Colored Balls solution in Javascript Try on Compiler 
var maxProfit = function(inventory, orders) {
    // Implement a max heap for JavaScript (since it's not built-in like in C++)
    class MaxHeap {
        constructor() {
            this.heap = [];
        }
        
        size() {
            return this.heap.length;
        }
        
        empty() {
            return this.size() === 0;
        }
        
        push(val) {
            this.heap.push(val);
            this._siftUp(this.size() - 1);
        }
        
        top() {
            return this.empty() ? 0 : this.heap[0];
        }
        
        pop() {
            if (this.empty()) return 0;
            const max = this.heap[0];
            const last = this.heap.pop();
            if (this.size() > 0) {
                this.heap[0] = last;
                this._siftDown(0);
            }
            return max;
        }
        
        _siftUp(idx) {
            while (idx > 0) {
                const parentIdx = Math.floor((idx - 1) / 2);
                if (this.heap[parentIdx] >= this.heap[idx]) break;
                [this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]];
                idx = parentIdx;
            }
        }
        
        _siftDown(idx) {
            const size = this.size();
            while (true) {
                let largestIdx = idx;
                const leftIdx = 2 * idx + 1;
                const rightIdx = 2 * idx + 2;
                
                if (leftIdx < size && this.heap[leftIdx] > this.heap[largestIdx]) {
                    largestIdx = leftIdx;
                }
                
                if (rightIdx < size && this.heap[rightIdx] > this.heap[largestIdx]) {
                    largestIdx = rightIdx;
                }
                
                if (largestIdx === idx) break;
                
                [this.heap[idx], this.heap[largestIdx]] = [this.heap[largestIdx], this.heap[idx]];
                idx = largestIdx;
            }
        }
    }
    
    // Create a max heap
    const pq = new MaxHeap();
    
    // Modulo for large numbers and to prevent overflow
    const mod = 1e9 + 7;
    
    // Variable to store the total profit
    let profit = 0;
    
    // Push all inventory counts into the max-heap
    for (let count of inventory) {
        pq.push(count);
    }
    
    // Continue selling balls until all orders are fulfilled
    while (orders > 0 && !pq.empty()) {
        // Get the highest available inventory count
        let top = pq.top();
        
        // Remove it from the heap since we are processing it
        pq.pop();
        
        // Get the next highest inventory count (or 0 if none left)
        let nextTop = pq.empty() ? 0 : pq.top();
        
        // Determine how many balls we can sell at the current price before reaching nextTop
        let sellCount = Math.min(orders, top - nextTop + 1);
        
        // Compute the profit from selling balls from 'top' down to 'top - sellCount + 1'
        // Use BigInt for large number calculations to avoid overflow
        let sum = BigInt(top + (top - sellCount + 1)) * BigInt(sellCount) / BigInt(2);
        
        // Add the computed profit to the total, applying modulo to prevent overflow
        profit = (profit + Number(sum % BigInt(mod))) % mod;
        
        // Reduce the number of remaining orders
        orders -= sellCount;
        
        // If there are remaining balls of this color, push the reduced count back into the heap
        if (top - sellCount > 0) {
            pq.push(top - sellCount);
        }
    }
    
    // Return the final computed profit
    return profit;
};

Sell Diminishing-Valued Colored Balls Complexity Analysis(brute force)

Time Complexity: O((n + orders) log n)

Let n be the number of different colors of balls (i.e., the size of the inventory array) and orders be the total number of orders.

1. Inserting Elements into the Max-Heap (Priority Queue)

  • We push all n elements into the max-heap.
  • Time Complexity: O(n log n) (each insertion takes O(log n) and we do it for n elements).

2. Processing Orders

  • In each iteration, we extract the max element (top) from the heap, which takes O(log n).
  • We may also insert a new reduced value back into the heap, which takes another O(log n).
  • The number of iterations is at most O(n + orders/n) because:
    • We process at most n unique inventory levels (each distinct number in inventory).
    • In some cases, we might process extra iterations where we decrement the largest value in small steps, but these are limited.

3. Overall Complexity

Since heap operations (insert and remove) are O(log n), and we do these operations at most O(n + orders/n) times, the worst-case complexity is: O(n log ⁡n + orders * log ⁡n)

If orders ≫ n, then the dominant term is O(orders log n).
If orders ≤ n, then the dominant term is O(n log n).

Final Complexity: O((n + orders) log n)

Space Complexity: O(n)

  1. Auxiliary Space Complexity: O(n)
    The algorithm uses a priority queue (max-heap) to store up to n elements from inventory.
    Therefore, the auxiliary space complexity is O(n).
  2. Total Space Complexity: O(n)
    The input inventory array takes O(n) space.
    Therefore, the total space complexity is O(n).

Will Brute Force Work Against the Given Constraints? 

For the current solution, the time complexity is O((n + orders) log n), where n is the number of elements in the inventory (inventory.length), with an upper limit of 10⁵.

In the worst-case scenario, when n is at its maximum constraint (10⁵) and orders is also at its maximum (10⁹), the total number of operations would be approximately (10⁵ + 10⁹) log 10⁵. Since log 10⁵ ≈ 17, the total number of operations would be around (10⁹ + 10⁵) × 17, which is not feasible for large values of orders.

This time complexity becomes highly inefficient when orders approaches 10⁹, as it leads to billions of operations, making it impractical for large test cases. While it may work for smaller inputs, it is likely to result in Time Limit Exceeded (TLE) errors when orders is very large.

In competitive programming, the typical acceptable time complexity limit is around 10⁶ operations per test case. Since this solution may perform significantly more operations (10⁹ in the worst case), it is not scalable and requires further optimization to handle large inputs efficiently.

How to optimize it?

In this problem, we are given an array where each element represents the number of balls of a certain color. We need to sell orders number of balls, always selling the highest-priced balls first to maximize profit.

Our first instinct might be to use a max-heap (priority queue) since it helps us efficiently fetch the highest-priced ball each time.

However, this approach had a major inefficiency: Every time we sell some balls, we modify the heap, which requires log-time operations. Since we process orders one by one (or in small groups), the time complexity becomes O((n + orders) log n). This is infeasible when orders is large.

To solve the problem efficiently within the given constraints, we need to maintain a sorted order of the number of balls for each color so that we can always pick the one with the highest count first. However, there can be cases where multiple ball types have the same count. Instead of handling them separately, we can group these cases together, allowing us to calculate the result more efficiently.

Instead of a heap, we use a sorted map where:

  • The keys represent ball values.
  • The values represent the frequency (number of times this ball value appears).
  • The map is sorted in descending order.

Why Do We Need a Sorted Map?

  1. Since the map is sorted in descending order, we can easily access the highest ball values without needing a heap.
  2. Unlike a heap, the map directly maintains how many balls exist at each value, allowing fast frequency-based calculations.
  3. Instead of continuously modifying a heap, we efficiently update the frequency counts in the map.

By using this approach, we ensure that we process elements in sorted order without the overhead of frequent insertions and deletions in a heap.

Now that we have grouped ball types with the same frequency together in a sorted manner, let's make a few key observations to build our understanding further.

First, let's think about the minimum possible value of a ball for which we can sell all balls that have a higher value. The smallest such value can be 0 because, in the worst case, we might need to sell each ball individually, fulfilling every order with exactly one ball. This means that even if we are left with only one order to process, we should be able to pick a ball of the lowest possible value, ensuring that no orders remain unfulfilled.

Now, let's consider the maximum possible value for which we can sell all balls below that value. This will clearly be the maximum element in the inventory because we are allowed to pick the highest available balls first. If we were to process all orders using balls from the highest available value downward, we would keep decreasing the count of higher-value balls until we reach a threshold where orders are either completely fulfilled or we need to sell some balls from a lower frequency.

With these two boundary conditions established—0 as the minimum and the max element of inventory as the maximum—we now have a clear idea of the possible range of values where we can find the exact threshold at which all balls above that value are sold, and some (maybe 0) balls of that value are also sold. This threshold will help us determine the optimal point to maximize our profit while fulfilling the given number of orders efficiently.

Now that we understand the boundaries of our problem, let’s focus on the key idea:

There exists some price k such that:

  1. All balls priced greater than k are completely sold. This means that every ball with a value higher than k is used to fulfill orders.
  2. Some (maybe zero) of the balls priced exactly at k are sold. Once all higher-priced balls are exhausted, we might need to sell some balls at price k to complete the remaining orders.
  3. No balls priced less than k are touched. This ensures we are maximizing profit since we always prioritize selling higher-value balls first.

This means that our goal is to find this threshold price k, where all balls above k are sold, and some (or none) of the balls priced at k are also sold.

Now that we know the boundaries for our search space and have maintained a sorted order of inventory values, we can determine whether binary search is applicable.

Before applying binary search, we must ensure three conditions are met:

  1. The array (or in our case, the sorted map) is sorted.
    • We have already ensured this by sorting the inventory values in descending order.
  2. The search space is monotonic.
    • The number of orders that can be fulfilled decreases as the threshold price k increases.
    • If we choose a higher k, fewer balls will be sold, and if we lower k, more balls will be sold.
    • This monotonicity allows us to apply binary search effectively.
  3. The middle element helps in decision-making.
    • For a given mid (potential k), we can determine whether we can fulfill all orders by selling balls priced above or equal to mid.
    • If we can, we might try increasing mid (to maximize profit).
    • If we can't, we reduce mid (to ensure orders are fulfilled).

Since all three conditions hold, we can now confidently apply binary search to find k efficiently.

💡
How binary search works?

Our search space is [0, max(inventory)], and we perform binary search within this range to find the threshold price k.

Sell Diminishing-Valued Colored Balls Algorithm

Determining Whether a Given k is Valid:

Now that we are applying binary search to find the threshold price k, let's break down how we determine whether a given mid = k can fulfill all orders.

Step 1: Go Through the Sorted Inventory Map

Since we have stored our inventory in a sorted map (in descending order), we can efficiently check how many balls we can sell that have a value greater than k.

For each unique ball value ball in the inventory:

  • If ball > k, then we know we will completely sell all balls of this type.
  • If ball ≤ k, we stop because we are only interested in balls with a value greater than k.

Since multiple ball types can have the same frequency, our sorted map naturally groups them together, allowing us to process them efficiently.

Step 2: Count the Number of Balls We Can Sell from Values Greater than k

For every ball type with ball > k, we compute how many balls we can sell:

  • The number of balls of this type is given by cnt (count of balls at this price).
  • The difference (ball - k) gives the number of balls per color that we can sell.
  • The total contribution from this type is cnt * (ball - k).
  • We keep subtracting from orders until either orders become 0 or we run out of higher-value balls.

Step 3: Adjust the Search Range Based on Orders Fulfillment

After iterating through the map:

  • If we were able to fulfill all orders, this means k can be increased to get a better profit. So, we set low = mid + 1.
  • If we could not fulfill all orders, it means our chosen k is too high, and we need to decrease k by setting high = mid - 1.

We continue this process until low and high converge, meaning we have found the optimal value of k that allows us to fulfill all orders while maximizing profit.

This ensures that we are optimally distributing the orders while maintaining efficiency with O(log n) binary search instead of iterating over all possible prices.

Now that we have determined the threshold price k, the next step is to compute the total profit efficiently. Instead of iterating over each ball one by one, we use mathematical formulas to sum up contributions quickly.

Calculating the Final Profit

Step 1: Sell All Balls Priced Greater than k

We know that all balls priced above k are completely sold out.
For each of these prices:

  • The price of the ball starts from ball (the highest value) and decreases until k + 1.
  • The number of balls of this type is cnt.
  • Instead of iterating through each ball, we use the formula for the sum of an arithmetic sequence:
    sum = (ball + (k + 1)) × (ball − k) / 2

    This formula efficiently computes the total revenue from selling balls at prices from ball down to k + 1.
  • Since there are cnt such balls, we multiply:
    profit += ((ball + k + 1)×(ball − k) / 2 × cnt) % mod % mod

    We use modulo 1e9+7 to prevent overflow.
  • We subtract the sold balls from orders.

Step 2: Sell Some Balls at Price k (if needed)

Once we have sold all balls above k, there might still be some remaining orders left.
These remaining orders are fulfilled by selling some (or all) of the balls priced exactly at k.

  • We simply add:
    profit += (k × orders) % mod % mod
    This accounts for the last few balls sold at price k.

By using mathematical formulas instead of loops, we maximize profit efficiently while keeping the solution optimal in terms of time complexity.
This ensures that the approach runs efficiently even for large inputs.

Let us understand this with a video.

0:00
/1:27

Sell Diminishing-Valued Colored Balls-optimal-approach-animation

💡
Try it Yourself!

Let's understand with an example:

Sell Diminishing-Valued Colored Balls Example:

Input: inventory = [2,5], orders = 4

  1. Initialize:
    • n = 2
    • low = 0
    • high = 5 (max element in inventory)
    • ans = 0
    • mp = {5: 1, 2: 1} (frequency map sorted in descending order)
  3. Binary search to find the threshold value:
    • First iteration: mid = (0+5)/2 = 2
      • check(mp, 2, 4):
        • For ball=5: orders -= 1*(5-2) = 4-3 = 1
        • For ball=2: break (since 2 ≤ 2)
        • Return false (orders=1 > 0)
      • high = mid-1 = 1
    • Second iteration: mid = (0+1)/2 = 0
      • check(mp, 0, 4):
        • For ball=5: orders -= 1*(5-0) = 4-5 = -1
        • Return true (orders=-1 ≤ 0)
      • low = mid+1 = 1
    • Third iteration: mid = (1+1)/2 = 1
      • check(mp, 1, 4):
        • For ball=5: orders -= 1*(5-1) = 4-4 = 0
        • Return true (orders=0 ≤ 0)
      • low = mid+1 = 2
    • Fourth iteration: low=2, high=1, exit loop
  5. Calculate profit:
    • low = 2
    • For ball=5:
      • orders -= 1*(5-2) = 4-3 = 1
      • ans += ((5+2+1)*(5-2)/2 % mod)1 % mod = (83/2)*1 = 12
    • For ball=2: break (since 2 ≤ 2)
    • orders = 1 > 0, so add: ans += (2*1) % mod = 2
    • Total ans = (12 + 2) % mod = 14
  7. Return ans = 14

Therefore, the maximum profit for this example is 14.

How to code it up:

  • Store Inventory Frequencies
    • Use a sorted data structure (e.g., map in C++/Java ) to store inventory counts in descending order.
    • Group items with the same count for efficient processing.
  • Apply Binary Search to Find Threshold k
    • Define low = 0 and high = max(inventory).
    • Use binary search to find the price k such that:
      • All balls priced above k are fully sold.
      • Some (maybe 0) of the balls priced at k are sold.
      • No balls priced below k are touched.
  • Determine if a Given k is Valid
    • Traverse the sorted inventory.
    • Count the number of balls that can be sold from values greater than k.
    • If we can fulfill all orders, increase k. Otherwise, decrease k.
  • Compute Maximum Profit Efficiently
    • Sell all balls priced above k and compute their contribution using summation formula.
    • Sell remaining balls priced at k to complete the orders.
    • Use modulo arithmetic to handle large numbers.
  • Return the Final Computed Profit
    • The result is the maximum profit achieved by following the above steps.

Sell Diminishing-Valued Colored Balls leetcode solution

Sell Diminishing-Valued Colored Balls solution / Code Implementation
1. Sell Diminishing-Valued Colored Balls solution in C++ Try on Compiler 
class Solution {
    // Modulo to handle large numbers and prevent overflow
    const int mod = 1e9+7;

    // Function to check if we can sell `orders` balls with a minimum value of `mid`
    bool check(map<int, int, greater<>> &mp, long long mid, int orders) {
        
        // Iterate through the map of inventory counts in descending order
        for(auto &[ball, cnt] : mp) {
            // If the current ball value is already ≤ mid, stop checking
            if(ball <= mid)
                break;
            
            // Reduce orders by selling all balls from `ball` down to `mid`
            orders -= cnt * (ball - mid);
            
            // If we can fulfill all orders, return true
            if(orders <= 0)
                return true;
        }

        // Return whether all orders can be fulfilled
        return orders <= 0;
    }

public:
    // Function to calculate the maximum profit while selling `orders` balls
    int maxProfit(vector<int>& inventory, int orders) {
        // Get the number of elements in inventory
        int n = inventory.size();
        
        // Initialize binary search range
        long long low = 0;
        long long high = *max_element(inventory.begin(), inventory.end());
        
        // Variable to store the final maximum profit
        long long ans = 0;

        // Store frequency of each inventory count in descending order using a sorted map
        map<int, int, greater<>> mp;
        for(auto &ball: inventory) {
            mp[ball]++;
        }

        // Perform binary search to determine the threshold value `k`
        while(low <= high) {
            long long mid = (low + high) / 2;

            // If it's possible to fulfill all orders at `mid`, move `low` higher
            if(check(mp, mid, orders))
                low = mid + 1;
            else
                high = mid - 1;
        }

        // Sell all balls above `low` and compute profit efficiently
        for(auto &[ball, cnt] : mp) {
            // Stop when reaching the threshold `low`
            if(ball <= low)
                break;
            
            // Sell balls from `ball` down to `low`
            orders -= cnt * (ball - low);
            
            // Calculate profit using sum of arithmetic series formula
            ans = (ans + ((ball + low + 1) * (ball - low) / 2 % mod) * cnt % mod) % mod;
        }

        // Sell remaining balls at price `low` if there are leftover orders
        if(orders > 0)
            ans = (ans + (low * orders) % mod) % mod;
        
        // Return the maximum profit
        return ans;
    }
};

2. Sell Diminishing-Valued Colored Balls solution in Java Try on Compiler 
import java.util.*;

class Solution {
    // Modulo to prevent overflow
    private static final int MOD = 1_000_000_007;

    // Function to check if we can sell `orders` balls with a minimum value of `mid`
    private boolean check(TreeMap<Integer, Integer> inventoryMap, long mid, int orders) {

        // Iterate through inventory map in descending order
        for (Map.Entry<Integer, Integer> entry : inventoryMap.entrySet()) {
            int ball = entry.getKey();
            int count = entry.getValue();
            
            // If the current ball value is already ≤ mid, stop checking
            if (ball <= mid)
                break;

            // Reduce orders by selling all balls from `ball` down to `mid`
            orders -= count * (ball - mid);
            
            // If we can fulfill all orders, return true
            if (orders <= 0)
                return true;
        }

        // Return whether all orders can be fulfilled
        return orders <= 0;
    }

    // Function to calculate the maximum profit while selling `orders` balls
    public int maxProfit(int[] inventory, int orders) {
        
        // Store frequency of each inventory count in descending order
        TreeMap<Integer, Integer> inventoryMap = new TreeMap<>(Collections.reverseOrder());
        
        // Populate the map with counts of each inventory value
        for (int ball : inventory) {
            inventoryMap.put(ball, inventoryMap.getOrDefault(ball, 0) + 1);
        }

        // Initialize binary search range
        long low = 0, high = Arrays.stream(inventory).max().getAsInt();
        long ans = 0;

        // Perform binary search to determine the threshold `k`
        while (low <= high) {
            long mid = (low + high) / 2;

            // If possible to fulfill all orders at `mid`, move `low` higher
            if (check(inventoryMap, mid, orders))
                low = mid + 1;
            else
                high = mid - 1;
        }

        // Sell all balls above `low` and compute profit efficiently
        for (Map.Entry<Integer, Integer> entry : inventoryMap.entrySet()) {
            int ball = entry.getKey();
            int count = entry.getValue();

            // Stop when reaching the threshold `low`
            if (ball <= low)
                break;

            // Sell balls from `ball` down to `low`
            orders -= count * (ball - low);

            // Calculate profit using sum of arithmetic series formula
            ans = (ans + ((ball + low + 1) * (ball - low) / 2 % MOD) * count % MOD) % MOD;
        }

        // Sell remaining balls at price `low` if there are leftover orders
        if (orders > 0)
            ans = (ans + (low * orders) % MOD) % MOD;

        // Return the maximum profit
        return (int) ans;
    }
}

3. Sell Diminishing-Valued Colored Balls solution in Python Try on Compiler 
from collections import Counter
from math import ceil

class Solution:
    def maxProfit(self, inventory, orders):
        mod = 10**9 + 7
        
        # Create frequency map in descending order of values
        counts = Counter(inventory)
        values = sorted(counts.keys(), reverse=True)
        
        def check(mid, orders):
            remaining_orders = orders
            for val in values:
                if val <= mid:
                    break
                remaining_orders -= counts[val] * (val - mid)
                if remaining_orders <= 0:
                    return True
            return remaining_orders <= 0
        
        # Binary search for threshold value
        low, high = 0, max(inventory)
        while low <= high:
            mid = (low + high) // 2
            if check(mid, orders):
                low = mid + 1
            else:
                high = mid - 1
        
        # Calculate profit
        ans = 0
        for val in values:
            if val <= low:
                break
            
            balls_to_sell = counts[val] * (val - low)
            orders -= balls_to_sell
            
            # Sum of arithmetic sequence: (first + last) * count / 2
            profit = ((val + low + 1) * (val - low) // 2) * counts[val]
            ans = (ans + profit) % mod
        
        # Handle remaining orders at threshold value
        if orders > 0:
            ans = (ans + low * orders) % mod
            
        return ans

4. Sell Diminishing-Valued Colored Balls solution in Javascript Try on Compiler 
var maxProfit = function(inventory, orders) {
    // Modulo to handle large numbers and prevent overflow
    const MOD = 1e9 + 7;

    // Store frequency of each inventory count in descending order using a Map
    let inventoryMap = new Map();
    for (let ball of inventory) {
        inventoryMap.set(ball, (inventoryMap.get(ball) || 0) + 1);
    }

    // Convert the Map to an array and sort it in descending order based on keys
    let sortedInventory = [...inventoryMap.entries()].sort((a, b) => b[0] - a[0]);

    // Binary search range
    let low = 0, high = Math.max(...inventory);
    
    // Function to check if we can fulfill all orders at `mid`
    function canFulfill(mid) {
        let remainingOrders = orders;
        for (let [ball, count] of sortedInventory) {
            if (ball <= mid) break;
            remainingOrders -= count * (ball - mid);
            if (remainingOrders <= 0) return true;
        }
        return remainingOrders <= 0;
    }

    // Perform binary search to determine threshold `k`
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (canFulfill(mid)) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    let ans = 0;

    // Sell all balls above `low` and compute profit efficiently
    for (let [ball, count] of sortedInventory) {
        if (ball <= low) break;
        orders -= count * (ball - low);
        ans = (ans + (((ball + low + 1) * (ball - low) / 2) % MOD) * count % MOD) % MOD;
    }

    // Sell remaining balls at price `low` if there are leftover orders
    if (orders > 0) {
        ans = (ans + (low * orders) % MOD) % MOD;
    }

    // Return the maximum profit
    return ans;
};

Time Complexity: O((n + orders) log n)

Let n be the length of the inventory array and orders be the number of balls to sell.

Step 1: Storing Inventory Frequencies - O(n log n)

  • We use a map (C++/Java) / Object (JS) to store inventory counts in descending order.
  • Sorting the inventory takes O(n log n) in worst case.

Step 2: Binary Search to Find Threshold k - O(log n)

  • The search space for k ranges from 0 to max(inventory).
  • Since the range is bounded (1 to 10⁹), the number of iterations in binary search is at most O(log max(inventory)) = O(log 10⁹) ≈ O(30).
  • However, each iteration processes n elements in the worst case, so the total time is O(n log n).

Step 3: Validating k (Checking Orders) - O(n) per Iteration

  • In each binary search iteration, we traverse the map (worst case O(n)) to count sellable balls.
  • Since binary search runs O(log n) times, this contributes O(n log n) in the worst case.

Step 4: Computing Final Profit - O(n)

  • After determining k, we traverse the inventory map once to compute the total profit.
  • This step runs in O(n).

Overall Complexity:

  • Sorting: O(n log n)
  • Binary Search: O(n log n)
  • Final Computation: O(n)
    Total Complexity: O((n + orders) log n)

Since orders ≤ sum(inventory) ≤ 10⁹, this ensures our solution is highly efficient for large constraints.

Space Complexity: O(n)

  1. Auxiliary Space Complexity: O(n)
    The algorithm uses a few integer variables. The extra space used is O(n) for storing the frequency map.
    Therefore, the auxiliary space complexity is O(n).
  2. Total Space Complexity: O(n)
    The input inventory array requires O(n) space.
    Therefore, the total space complexity is O(n).

Can it be solved greedily?

Imagine you are running a store with different types of balls, each type having a certain number of balls. You want to sell exactly orders number of balls in a way that maximizes the total profit. The price of a ball is equal to its current stock level, so the highest-numbered balls sell for the most money.

So, what’s the best way to maximize profit?
We should always sell the highest-valued balls first.

Let’s take a real-world example:

  • If you have 5 balls priced at 10 each and 4 balls priced at 9,
  • It is better to sell from the 10-valued balls first to maximize earnings.

This means we need an organized way to always access the highest-value balls first.

The first thing we do is sort the inventory in ascending order. Why?

  • Sorting helps us process the highest-value balls first.
  • Instead of checking all values randomly, we can systematically process them from highest to lowest.
  • It also allows us to efficiently track groups of balls at the same level.

Now, after sorting, we will process the inventory from right to left (from the highest stock value to the lowest).

Now that we have sorted the inventory, we want to figure out:

  1. How many orders can be fulfilled at the current highest stock level?
  2. How far can we reduce the stock before we reach the next lower level?

At each step, we compare the current inventory level with the previous level in the sorted order.

If we are currently at inventory[i] and the previous stock level is inventory[i-1], the difference between them tells us how many levels we can decrease before reaching the next stock level:

difference = inventory[i] − inventory[i−1]

Each time we lower the stock level by 1, we are removing balls from all the stacks at that level. The number of such stacks is:

count = (n−i)

where:

  • n is the total number of inventory items.
  • i is the current position (from right to left).
  • (n - i) tells us how many stacks of balls are currently at this level.

So, the total number of balls we can sell from this level before reaching the next lower level is:

difference × (n−i)

However, we can only fulfill a maximum of orders, so the actual number of balls we sell here is:

currOrders = min⁡(orders , difference × (n−i))

If currOrders == orders, it means we have sold all the balls needed, and we stop here.

At this step, we have determined that we can fulfill currOrders orders from the current inventory level.

Now, we define two values:

  1. High (high) → The current inventory level before selling.
  2. Low (low) → The new level after fulfilling currOrders orders.

low = high − (currOrders / (n−i))

This means that we are reducing all the stacks at the current level down to the lowest possible level while fulfilling as many orders as we can.

Now comes the most important part—calculating the total profit from the balls we have sold.

We need to sum up all the values of the balls we sold, but doing this one by one would be very slow. Instead, we use mathematical formulas to efficiently compute the sum in constant time.

Deriving the Formula for Profit Calculation

We sold all balls from high down to low+1.

The sum of first m natural numbers is:

S(m) = m × (m + 1) / 2

So, the profit gained from selling all balls from low+1 to high is:

S(high)−S(low)

high × (high+1) / 2 − low × (low + 1) / 2

Since there are (n - i) such stacks, we multiply the result by (n - i).

(high × (high + 1) / 2 − low × (low + 1) / 2) × (n−i)

There is one small issue:

  • Sometimes, the currOrders do not divide evenly among (n - i).
  • This means some stacks will sell one extra ball beyond the low level.
  • The number of such extra balls is:

currOrders %  (n−i)

These extra balls are sold at the low price, so their profit contribution is:

low × (currOrders %  (n−i))

Finally, we update the remaining orders:

orders −= currOrders

And continue to the next lower inventory level.

To summarize the steps:

Sell Diminishing-Valued Colored Balls Algorithm

  1. Sort the inventory in ascending order.
  2. Process from right to left (from highest stock level to lowest).
  3. For each level, calculate how many orders can be fulfilled before reaching the next lower level.
  4. Compute the profit efficiently using sum formulas instead of looping over individual values.
  5. Handle remaining orders carefully if they do not divide evenly.
  6. Keep updating the total profit and reduce the number of orders until all are fulfilled.

This ensures we maximize the profit while fulfilling the given orders optimally.

💡
Try it Yourself!

Let's understand with an example:

Sell Diminishing-Valued Colored Balls Example:

Dry Run for Input: inventory = [2,5], orders = 4

Step 1: Sort the Inventory

Sorted inventory: [2, 5]

Step 2: Process from Right to Left

First Iteration (i = 1, inventory[i] = 5, prev = 2, n = 2):

  • Difference between current and previous level = 5 - 2 = 3
  • Max orders that can be fulfilled = min(4, 3 × (2 - 1)) = min(4, 3 × 1) = 3
  • High = 5, Low = 5 - 3/1 = 2
  • Profit from selling [5, 4, 3]:
    • (5 × (5 + 1)/2) - (2 × (2 + 1)/2) = (15 - 3) = 12
  • Remaining orders = 4 - 3 = 1

Second Iteration (i = 0, inventory[i] = 2, prev = 0):

  • Only 1 order left, sell 1 ball at price 2
  • Profit = 2 × 1 = 2

Final Profit

Total Profit = 12 + 2 = 14

Steps to Implement the Solution:

  • Initialize Variables
    • Define mod = 1e9+7 to handle large numbers.
    • Store the number of colors (n = inventory.size()).
    • Initialize ans = 0 to store the total profit.
  • Sort the Inventory
    • Sort inventory in ascending order to process from the largest to the smallest.
  • Traverse from Right to Left (Largest to Smallest Stock)
    • Iterate from the last element to the first (highest inventory to lowest).
  • Calculate Orders That Can Be Fulfilled at Each Level
    • Compute prev = inventory[i-1] (previous inventory level, or 0 if it's the first element).
    • Compute difference = inventory[i] - prev (how many extra balls are at this level).
    • Compute currOrders = min(orders, difference * (n - i)) (how many orders can be fulfilled).
  • Compute Profit Efficiently
    • Set high = inventory[i] and low = high - currOrders / (n - i).
    • Use sum of arithmetic series formula to calculate profit contribution efficiently:
      • profit = ((high * (high + 1) / 2) - (low * (low + 1) / 2)) * (n - i).
    • Handle leftover orders: ans += low * (currOrders % (n - i)).
  • Update Remaining Orders
    • Subtract currOrders from orders.
  • Return Final Computed Profit
    • Return ans % mod.

Sell Diminishing-Valued Colored Balls leetcode solution

Sell Diminishing-Valued Colored Balls solution / Code Implementation
1. Sell Diminishing-Valued Colored Balls solution in c++ Try on Compiler 
class Solution {

    // Define the modulo to prevent integer overflow
    const int mod = 1e9+7;

public:
    int maxProfit(vector<int>& inventory, int orders) {
        
        // Get the number of different ball colors
        int n = inventory.size();

        // Variable to store the final computed profit
        long long ans = 0;

        // Sort the inventory in ascending order
        sort(inventory.begin(), inventory.end());

        // Traverse from the highest inventory downwards
        for(int i = n - 1; i >= 0; i--) {
            
            // Get the previous inventory level (or 0 if at the lowest level)
            int prev = (i > 0 ? inventory[i - 1] : 0);
            
            // Calculate the difference between current and previous level
            long long difference = inventory[i] - prev;

            // Calculate the maximum number of orders we can fulfill at this level
            long long currOrders = min((long long)orders, difference * (n - i));

            // Define high as the current inventory level
            long long high = inventory[i];

            // Define low as the level where currOrders can be satisfied
            long long low = high - currOrders / (n - i);

            // Compute the profit using the formula for sum of arithmetic series
            ans += ((high * (high + 1) / 2) - (low * (low + 1) / 2)) * (n - i);
            ans %= mod;
            
            // Add remaining orders that do not completely fill a level
            ans += low * (currOrders % (n - i));
            ans %= mod;

            // Reduce the remaining orders to be fulfilled
            orders -= currOrders;
        }

        // Return the computed maximum profit
        return ans;
    }
};

2. Sell Diminishing-Valued Colored Balls solution in Java Try on Compiler 
import java.util.Arrays;

class Solution {
    // Define the modulo to prevent integer overflow
    private static final int MOD = 1_000_000_007;

    public int maxProfit(int[] inventory, int orders) {
        // Get the number of different ball colors
        int n = inventory.length;

        // Variable to store the final computed profit
        long ans = 0;

        // Sort the inventory in ascending order
        Arrays.sort(inventory);

        // Traverse from the highest inventory downwards
        for (int i = n - 1; i >= 0; i--) {

            // Get the previous inventory level (or 0 if at the lowest level)
            int prev = (i > 0) ? inventory[i - 1] : 0;

            // Calculate the difference between current and previous level
            long difference = inventory[i] - prev;

            // Calculate the maximum number of orders we can fulfill at this level
            long currOrders = Math.min(orders, difference * (n - i));

            // Define high as the current inventory level
            long high = inventory[i];

            // Define low as the level where currOrders can be satisfied
            long low = high - currOrders / (n - i);

            // Compute the profit using the formula for sum of arithmetic series
            ans += ((high * (high + 1) / 2) - (low * (low + 1) / 2)) * (n - i);
            ans %= MOD;

            // Add remaining orders that do not completely fill a level
            ans += low * (currOrders % (n - i));
            ans %= MOD;

            // Reduce the remaining orders to be fulfilled
            orders -= currOrders;
        }

        // Return the computed maximum profit
        return (int) ans;
    }
}

3. Sell Diminishing-Valued Colored Balls solution in Python Try on Compiler 
class Solution:
    
    # Define the modulo to prevent integer overflow
    MOD = 10**9 + 7

    def maxProfit(self, inventory, orders):
        # Get the number of different ball colors
        n = len(inventory)

        # Variable to store the final computed profit
        ans = 0

        # Sort the inventory in ascending order
        inventory.sort()

        # Traverse from the highest inventory downwards
        for i in range(n - 1, -1, -1):

            # Get the previous inventory level (or 0 if at the lowest level)
            prev = inventory[i - 1] if i > 0 else 0

            # Calculate the difference between current and previous level
            difference = inventory[i] - prev

            # Calculate the maximum number of orders we can fulfill at this level
            currOrders = min(orders, difference * (n - i))

            # Define high as the current inventory level
            high = inventory[i]

            # Define low as the level where currOrders can be satisfied
            low = high - currOrders // (n - i)

            # Compute the profit using the formula for sum of arithmetic series
            ans += ((high * (high + 1) // 2) - (low * (low + 1) // 2)) * (n - i)
            ans %= self.MOD

            # Add remaining orders that do not completely fill a level
            ans += low * (currOrders % (n - i))
            ans %= self.MOD

            # Reduce the remaining orders to be fulfilled
            orders -= currOrders

        # Return the computed maximum profit
        return ans

4. Sell Diminishing-Valued Colored Balls solution in Javascript Try on Compiler 
/**
 * @param {number[]} inventory
 * @param {number} orders
 * @return {number}
 */

var maxProfit = function (inventory, orders) {

    // Define the modulo to prevent integer overflow
    const MOD = 1e9 + 7;

    // Get the number of different ball colors
    let n = inventory.length;

    // Variable to store the final computed profit
    let ans = 0;

    // Sort the inventory in ascending order
    inventory.sort((a, b) => a - b);

    // Traverse from the highest inventory downwards
    for (let i = n - 1; i >= 0; i--) {

        // Get the previous inventory level (or 0 if at the lowest level)
        let prev = i > 0 ? inventory[i - 1] : 0;

        // Calculate the difference between current and previous level
        let difference = inventory[i] - prev;

        // Calculate the maximum number of orders we can fulfill at this level
        let currOrders = Math.min(orders, difference * (n - i));

        // Define high as the current inventory level
        let high = inventory[i];

        // Define low as the level where currOrders can be satisfied
        let low = high - Math.floor(currOrders / (n - i));

        // Compute the profit using the formula for sum of arithmetic series
        ans += ((high * (high + 1) / 2) - (low * (low + 1) / 2)) * (n - i);

        // Add remaining orders that do not completely fill a level
        ans += low * (currOrders % (n - i));
        ans %= MOD;

        // Reduce the remaining orders to be fulfilled
        orders -= currOrders;
    }

    // Return the computed maximum profit
    return ans;
};

Sell Diminishing-Valued Colored Balls Complexity Analysis(Two Pointers)

Time Complexity: O(n log n)

  1. Sorting the Inventory
  • The algorithm starts by sorting the inventory array.
  • Sorting an array of size n using std::sort() takes O(n log n) time.
  1. Iterating Over the Inventory
  • The algorithm then loops through the inventory array in reverse order.
  • The loop runs O(n) times, where n is the number of different colors of balls.
  • Inside the loop, only constant-time operations (basic arithmetic and modulo operations) are performed.

3. Computing Profit Efficiently

  • The sum of arithmetic series is computed using a formula, which takes O(1) time.
  • Without the formula, iterating over each ball would have taken O(orders) time in the worst case.

Final Complexity Calculation

  • Sorting: O(n log n)
  • Processing the inventory: O(n)
  • Using formula-based calculations instead of iterating over each ball keeps it efficient.

Overall Time Complexity

O(n log n) + O(n) ≈ O(n log n)

Space Complexity: O(n)

  1. Auxiliary Space Complexity: O(n)
    The algorithm uses a few integer variables. The extra space used is O(n) for storing the sorted inventory array..
    Therefore, the auxiliary space complexity is O(n).
  2. Total Space Complexity: O(n)
    The total space complexity is O(n) due to storing the inventory array as input.
    Therefore, the total space complexity is O(n).

Similar Problems

Many array problems on Leetcode require a mix of techniques like Math, Binary Search, Greedy, Sorting, and Heap (Priority Queue) to find optimal solutions efficiently. Sorting is often a useful preprocessing step that helps structure the data for easier manipulation. In optimization problems, a Greedy approach is frequently applied to make the best local choices, ultimately leading to a globally optimal solution. Binary Search helps in narrowing down the search space when dealing with threshold-based problems. Meanwhile, Heap (Priority Queue) is a powerful data structure for efficiently retrieving the smallest or largest elements, making it useful in scheduling or k-th element problems. By combining these techniques strategically, we can tackle a wide range of array challenges with improved efficiency.

Now we have successfully tackled this problem, let's try these similar problems.

1. Maximum Running Time of N Computers

You have n computers. You are given the integer n and a 0-indexed integer array batteries where the ith battery can run a computer for batteries[i] minutes. You are interested in running all n computers simultaneously using the given batteries.

Initially, you can insert at most one battery into each computer. After that and at any integer time moment, you can remove a battery from a computer and insert another battery any number of times. The inserted battery can be a totally new battery or a battery from another computer. You may assume that the removing and inserting processes take no time.

Note that the batteries cannot be recharged.

Return the maximum number of minutes you can run all the n computers simultaneously.

2. Successful Pairs of Spells and Potions

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.

3. Maximum Matching of Players With Trainers

You are given a 0-indexed integer array players, where players[i] represents the ability of the ith player. You are also given a 0-indexed integer array trainers, where trainers[j] represents the training capacity of the jth trainer.

The ith player can match with the jth trainer if the player's ability is less than or equal to the trainer's training capacity. Additionally, the ith player can be matched with at most one trainer, and the jth trainer can be matched with at most one player.

Return the maximum number of matchings between players and trainers that satisfy these conditions

💡
Showcase your skills by joining LearnYard Technologies FZ-LLC as a Technical Content Writer. Apply now and inspire the next generation of learners—fill out the form: https://forms.gle/CGDsbGkcapSfvXKM8