3.40 Count Elements Greater Than Previous Average

3.40.1 Problem Metadata

3.40.2 Description

Given an array of positive integers, return the number of elements that are strictly greater than the average of all previous elements in the array.

Important: Skip the first element since there are no previous elements to calculate an average from.

3.40.3 Examples

Example 1:

Input: arr = [1, 2, 3, 4]
Output: 3
Explanation:
- Skip arr[0] = 1 (first element)
- arr[1] = 2, avg([1]) = 1.0, 2 > 1.0 → count
- arr[2] = 3, avg([1,2]) = 1.5, 3 > 1.5 → count
- arr[3] = 4, avg([1,2,3]) = 2.0, 4 > 2.0 → count
Total: 3

Example 2:

Input: arr = [5, 1, 2, 1]
Output: 0
Explanation:
- Skip arr[0] = 5
- arr[1] = 1, avg([5]) = 5.0, 1 is not > 5.0
- arr[2] = 2, avg([5,1]) = 3.0, 2 is not > 3.0
- arr[3] = 1, avg([5,1,2]) = 2.67, 1 is not > 2.67
Total: 0

3.40.4 Constraints

  • \(1 \le\) arr.length \(\le 10^5\)
  • \(1 \le\) arr[i] \(\le 10^9\)

3.40.5 Solution - Running Sum with Floating Point Average

3.40.5.1 Walkthrough

Maintain a running prefix sum (or average) of the elements processed so far. For each element arr[i], compare it against the average of the previous i elements. If arr[i] is strictly greater than this average, increment the count. Note that the problem asks to skip the first element as there are no previous elements to average.

3.40.5.2 Analysis

  • Time Complexity: O(n) - We iterate through the array once.
  • Space Complexity: O(n) - We store the prefix averages in an array (could be optimized to O(1) by tracking running sum).

3.40.5.3 Implementation Steps

  1. Initialize a prefixAvg array to store the running average up to each index.
  2. Iterate through the responseTimes list.
  3. For each element, calculate the new average including it.
  4. If the current element is greater than the previous average (and it’s not the first element), increment the result counter.
  5. Update the prefixAvg array for future comparisons.
  6. Return the result.

3.40.5.4 Code - Java

class Result {
    /*
     * Complete the 'countResponseTimeRegressions' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts INTEGER_ARRAY responseTimes as parameter.
     */
    public static int countResponseTimeRegressions(List<Integer> responseTimes) {
        double[] prefixAvg = new double[responseTimes.size()];
        
        int result = 0;
        
        for(int i = 0; i < responseTimes.size(); i++) {
            int respTime = responseTimes.get(i);
            double newAvg = calPrefixAverage(prefixAvg, i, respTime);
            
            if(i > 0 && respTime > newAvg) {
                result++;
            }
        }
        
        return result;
    }
    
    private static double calPrefixAverage(double[] prefixAvgRespTimes, int index, int resp) {
        double avg = 0;
        
        if(index == 0) {
            avg = resp;
        } else {
            avg = ((prefixAvgRespTimes[index - 1] * index + resp)) / (index + 1);
        }
        prefixAvgRespTimes[index] = avg;
        
        
        return avg;
    }
}