Orders With Maximum Quantity Above Average

This challenge asks you to analyze a dataset of orders and identify those with the maximum quantity ordered that are also above the average quantity across all orders. This is a common data analysis task, useful for identifying high-value or popular items, or for targeted marketing campaigns. You'll need to calculate averages, find maximums, and filter data based on these calculations.

Problem Description

You are given a list of orders, where each order is represented as a pair: [order_id, quantity]. Your task is to find the order(s) with the maximum quantity ordered, but only among those orders whose quantity is strictly greater than the average quantity of all orders. If multiple orders share the maximum quantity above the average, return all of them.

What needs to be achieved:

1. Calculate the average quantity across all orders.
2. Identify orders with a quantity greater than the calculated average.
3. Determine the maximum quantity among the orders identified in step 2.
4. Return the order IDs of all orders that have the maximum quantity found in step 3, and that also satisfy the condition in step 2 (quantity > average).

Key Requirements:

• The input is a list of lists, where each inner list contains two elements: the order ID (an integer) and the quantity ordered (an integer).
• The output should be a list of order IDs (integers) representing the orders that meet the specified criteria.
• The order IDs in the output list should be sorted in ascending order.
• If no orders meet the criteria (e.g., all orders have quantities less than or equal to the average), return an empty list.

Expected Behavior:

The function should correctly calculate the average, filter orders, find the maximum quantity among the filtered orders, and return the corresponding order IDs in sorted order.

Edge Cases to Consider:

• Empty input list: Should return an empty list.
• All orders have the same quantity: The average will be that quantity. Orders with quantity greater than the average will be returned if the quantity is strictly greater.
• Orders with negative quantities: The problem statement doesn't explicitly forbid negative quantities, so handle them appropriately in the average calculation and filtering.
• Large datasets: Consider potential performance implications if the input list is very large.

Examples

Example 1:

Input: [[1, 10], [2, 20], [3, 30], [4, 40], [5, 50]]
Output: [5]
Explanation: The average quantity is (10 + 20 + 30 + 40 + 50) / 5 = 30.  The orders with quantity > 30 are [3, 30], [4, 40], and [5, 50]. The maximum quantity among these is 50, so the output is [5].

Example 2:

Input: [[1, 5], [2, 5], [3, 5], [4, 5], [5, 5]]
Output: []
Explanation: The average quantity is 5. No orders have a quantity *greater than* 5, so the output is an empty list.

Example 3:

Input: [[1, 10], [2, 20], [3, 30], [4, 40], [5, 20]]
Output: [4]
Explanation: The average quantity is (10 + 20 + 30 + 40 + 20) / 5 = 24. The orders with quantity > 24 are [2, 20], [3, 30], [4, 40]. The maximum quantity among these is 40, so the output is [4].

Example 4:

Input: [[1, -10], [2, 20], [3, 30], [4, 40], [5, 50]]
Output: [5]
Explanation: The average quantity is (-10 + 20 + 30 + 40 + 50) / 5 = 22. The orders with quantity > 22 are [2, 20], [3, 30], [4, 40], and [5, 50]. The maximum quantity among these is 50, so the output is [5].

Constraints

• The number of orders in the input list will be between 0 and 1000, inclusive.
• Each order ID will be an integer between 1 and 1000, inclusive.
• Each quantity will be an integer between -1000 and 1000, inclusive.
• The solution should have a time complexity of O(n), where n is the number of orders.

Notes

• Consider using a single pass through the data to calculate the average and identify potential candidates.
• Sorting the output list is a required step.
• Pay close attention to the "strictly greater than" condition when filtering orders. Using > instead of >= is crucial.
• Think about how to handle the case where multiple orders share the maximum quantity above the average. You need to return all of them.
• The average should be a floating-point number to handle cases where the sum of quantities is not evenly divisible by the number of orders.