Return Elements Greater Than the Overall Average

Problem Statement

Given an array of integers, return a new list containing only the elements that are strictly greater than the arithmetic mean of all elements in the input list.

Your implementation should:

1. Maintain the relative order of the original elements.
2. Include duplicates if they satisfy the condition.
3. Not modify the input array.
4. Handle negative numbers correctly.

Function Signature

def get_elements_above_average(nums: List[int]) -> List[int]:

Constraints

• n (length of nums) is in the range [0, 10^6].
• Each element nums[i] is between -10^9 and 10^9.
• You should aim for O(n) time complexity and avoid unnecessary memory overhead.

Examples

Example 1: Input: nums = [1, 2, 3, 4, 5] Average: 3.0 Output: [4, 5] Explanation: Only 4 and 5 are strictly greater than 3.

Example 2: Input: nums = [10, -10, 5, 5] Average: 2.5 Output: [10, 5, 5] Explanation: 10, 5, and 5 are greater than 2.5.

Edge Cases

• What should the function return if the list is empty? (Return an empty list)
• What happens if all elements are equal? (The average equals the elements, so return an empty list)
• Ensure you handle potential integer overflow during the summation process if using lower-level languages.