Statistics from a Large Sample

Med

#1036Time: O(L + N), where L is the length of `count` (256) and N is the total number of elements in the sample (`sum(count)`). Since N can be up to 10^9, the complexity is dominated by O(N).Space: O(N) to store the reconstructed `sample` array. This is the main drawback, as it can require gigabytes of memory.

Patterns

Math Probability and Statistics

Data structures

Array

Prompt

You are given a large sample of integers in the range [0, 255]. Since the sample is so large, it is represented by an array count where count[k] is the number of times that k appears in the sample.

Calculate the following statistics:

minimum: The minimum element in the sample.
maximum: The maximum element in the sample.
mean: The average of the sample, calculated as the total sum of all elements divided by the total number of elements.
median:
- If the sample has an odd number of elements, then the median is the middle element once the sample is sorted.
- If the sample has an even number of elements, then the median is the average of the two middle elements once the sample is sorted.
mode: The number that appears the most in the sample. It is guaranteed to be unique.

Return the statistics of the sample as an array of floating-point numbers [minimum, maximum, mean, median, mode]. Answers within 10^-5 of the actual answer will be accepted.

Example 1:

Input: count = [0,1,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: [1.00000,3.00000,2.37500,2.50000,3.00000]
Explanation: The sample represented by count is [1,2,2,2,3,3,3,3].
The minimum and maximum are 1 and 3 respectively.
The mean is (1+2+2+2+3+3+3+3) / 8 = 19 / 8 = 2.375.
Since the size of the sample is even, the median is the average of the two middle elements 2 and 3, which is 2.5.
The mode is 3 as it appears the most in the sample.

Example 2:

Input: count = [0,4,3,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: [1.00000,4.00000,2.18182,2.00000,1.00000]
Explanation: The sample represented by count is [1,1,1,1,2,2,2,3,3,4,4].
The minimum and maximum are 1 and 4 respectively.
The mean is (1+1+1+1+2+2+2+3+3+4+4) / 11 = 24 / 11 = 2.18181818... (for display purposes, the output shows the rounded number 2.18182).
Since the size of the sample is odd, the median is the middle element 2.
The mode is 1 as it appears the most in the sample.

Constraints:

count.length == 256
0 <= count[i] <= 10⁹
1 <= sum(count) <= 10⁹
The mode of the sample that count represents is unique.

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward but highly inefficient approach is to first reconstruct the full, sorted sample array from the given count frequency array. Once the full sample is available in memory, standard methods can be used to calculate the statistics.

Algorithm

Calculate the total number of elements, N, by summing up all values in the count array.
Create a new array, sample, of size N.
Populate the sample array by iterating from i = 0 to 255. For each i, add the number i to the sample array count[i] times. This automatically results in a sorted sample array.
Calculate the statistics from the sample array:
- Minimum: sample[0]
- Maximum: sample[N-1]
- Mean: The sum of all elements in sample divided by N.
- Median: If N is odd, sample[N/2]. If N is even, the average of sample[N/2 - 1] and sample[N/2].
- Mode: Iterate through the sorted sample array, keeping track of the longest sequence of identical numbers to find the most frequent one.

Walkthrough

This method is conceptually simple because it transforms the problem into a more familiar form—a simple list of numbers. However, the problem constraints on the total number of elements (sum(count) can be up to 10^9) make this approach impractical due to excessive memory and time usage. It would likely result in an OutOfMemoryError.

Below is a conceptual code snippet. Note that this will not run for large inputs.

1// NOTE: This approach is not feasible for the given constraints and will likely fail.2public double[] sampleStats_bruteForce(int[] count) {3    long n_long = 0;4    for (int c : count) {5        n_long += c;6    }7    // This check highlights the impracticality.8    if (n_long > Integer.MAX_VALUE || n_long > 200_000_000) { // A practical memory limit9        System.err.println("Sample size too large to reconstruct in memory.");10        // This approach fails here. We would return an empty/error result.11        return new double[5];12    }13    int n = (int) n_long;14    if (n == 0) return new double[]{0,0,0,0,0};15 16    int[] sample = new int[n];17    int index = 0;18    for (int i = 0; i < 256; i++) {19        for (int j = 0; j < count[i]; j++) {20            sample[index++] = i;21        }22    }23 24    double minimum = sample[0];25    double maximum = sample[n - 1];26 27    long sum = 0;28    for (int val : sample) {29        sum += val;30    }31    double mean = (double) sum / n;32 33    double median;34    if (n % 2 == 1) {35        median = sample[n / 2];36    } else {37        median = (sample[n / 2 - 1] + sample[n / 2]) / 2.0;38    }39 40    // Mode calculation from sorted array41    int mode = 0;42    int maxFreq = 0;43    if (n > 0) {44        int currentFreq = 1;45        mode = sample[0];46        maxFreq = 1;47        for (int i = 1; i < n; i++) {48            if (sample[i] == sample[i-1]) {49                currentFreq++;50            } else {51                currentFreq = 1;52            }53            if (currentFreq > maxFreq) {54                maxFreq = currentFreq;55                mode = sample[i];56            }57        }58    }59 60    return new double[]{minimum, maximum, mean, median, mode};61}

Complexity

Time

O(L + N), where L is the length of `count` (256) and N is the total number of elements in the sample (`sum(count)`). Since N can be up to 10^9, the complexity is dominated by O(N).

Space

O(N) to store the reconstructed `sample` array. This is the main drawback, as it can require gigabytes of memory.

Trade-offs

Pros

Conceptually simple and easy to implement if memory were not a concern.

Cons

Extremely high memory usage, leading to OutOfMemoryError for large samples.
Inefficient time complexity, as it needs to process up to 10^9 elements.
Impractical for the constraints given in the problem.

This optimal approach avoids reconstructing the large sample array. Instead, it computes all the required statistics by iterating directly over the count frequency array. Since the size of count is fixed at 256, this method is extremely fast and memory-efficient, regardless of the total number of elements in the sample.

Algorithm

First, iterate through the count array to compute the total_count of elements in the sample.
Initialize variables for minimum, maximum, total_sum, mode, and max_frequency.
Calculate the 0-indexed positions of the median element(s): median_idx1 = (total_count - 1) / 2 and median_idx2 = total_count / 2.
Perform a second iteration from i = 0 to 255 over the count array, maintaining a current_count of elements seen so far.
In the loop, for each number i with count[i] > 0:
- Update minimum with the first such i found.
- Continuously update maximum with the current i.
- Add i * count[i] to total_sum.
- Update mode if count[i] is greater than the current max_frequency.
- Check if median_idx1 or median_idx2 fall within the current range of elements ([current_count, current_count + count[i])). If so, store i as the corresponding median value.
After the loop, calculate the mean as total_sum / total_count.
Calculate the median as the average of the two median values found. (If the total count is odd, these two values will be the same).
Return the five calculated statistics.

Walkthrough

The core idea is to leverage the pre-aggregated nature of the count array. The numbers 0-255 are already 'sorted' by their index. We can process these numbers and their frequencies in a couple of passes to derive all statistics.

Here is the implementation in Java:

1class Solution {2    public double[] sampleStats(int[] count) {3        long total_count = 0;4        for (int c : count) {5            total_count += c;6        }7 8        if (total_count == 0) {9            return new double[]{0.0, 0.0, 0.0, 0.0, 0.0};10        }11 12        double minimum = -1.0;13        double maximum = 0.0;14        long total_sum = 0L;15        int max_freq = 0;16        double mode = 0.0;17 18        long median_idx1 = (total_count - 1) / 2;19        long median_idx2 = total_count / 2;20        int median1_val = -1;21        int median2_val = -1;22 23        long current_elements = 0;24        for (int i = 0; i < 256; i++) {25            if (count[i] > 0) {26                // Minimum27                if (minimum == -1.0) {28                    minimum = i;29                }30                // Maximum31                maximum = i;32                // Sum for Mean33                total_sum += (long)i * count[i];34                // Mode35                if (count[i] > max_freq) {36                    max_freq = count[i];37                    mode = i;38                }39 40                // Median41                long next_elements = current_elements + count[i];42                if (median1_val == -1 && current_elements <= median_idx1 && median_idx1 < next_elements) {43                    median1_val = i;44                }45                if (median2_val == -1 && current_elements <= median_idx2 && median_idx2 < next_elements) {46                    median2_val = i;47                }48                current_elements = next_elements;49            }50        }51 52        double mean = (double)total_sum / total_count;53        double median = (median1_val + median2_val) / 2.0;54 55        return new double[]{minimum, maximum, mean, median, mode};56    }57}

Complexity

Time

O(L), where L is the length of the `count` array (256). Since L is a constant, the time complexity is effectively O(1).

Space

O(1), as we only use a constant number of variables to store intermediate and final results.

Trade-offs

Pros

Extremely efficient in time and space.
Handles very large sample sizes without memory issues.
The optimal solution for this problem representation.

Cons

The logic for finding the median is slightly more involved than working with a simple flat array.

Solutions

Solution

1class Solution {2private3  int[] count;4public5  double[] sampleStats(int[] count) {6    this.count = count;7    int mi = 1 << 30, mx = -1;8    long s = 0;9    int cnt = 0;10    int mode = 0;11    for (int k = 0; k < count.length; ++k) {12      if (count[k] > 0) {13        mi = Math.min(mi, k);14        mx = Math.max(mx, k);15        s += 1L * k * count[k];16        cnt += count[k];17        if (count[k] > count[mode]) {18          mode = k;19        }20      }21    }22    double median = cnt % 2 == 1 ? find(cnt / 2 + 1)23                                 : (find(cnt / 2) + find(cnt / 2 + 1)) / 2.0;24    return new double[]{mi, mx, s * 1.0 / cnt, median, mode};25  }26private27  int find(int i) {28    for (int k = 0, t = 0;; ++k) {29      t += count[k];30      if (t >= i) {31        return k;32      }33    }34  }35}

1class Solution {2public:3  vector<double> sampleStats(vector<int> &count) {4    auto find = [&](int i) -> int {5      for (int k = 0, t = 0;; ++k) {6        t += count[k];7        if (t >= i) {8          return k;9        }10      }11    };12    int mi = 1 << 30, mx = -1;13    long long s = 0;14    int cnt = 0, mode = 0;15    for (int k = 0; k < count.size(); ++k) {16      if (count[k]) {17        mi = min(mi, k);18        mx = max(mx, k);19        s += 1LL * k * count[k];20        cnt += count[k];21        if (count[k] > count[mode]) {22          mode = k;23        }24      }25    }26    double median = cnt % 2 == 1 ? find(cnt / 2 + 1)27                                 : (find(cnt / 2) + find(cnt / 2 + 1)) / 2.0;28    return vector<double>{(double)mi, (double)mx, s * 1.0 / cnt, median,29                          (double)mode};30  }31};

1class Solution:2    def sampleStats(self, count: List[int]) -> List[float]: def find(i: int) -> int: t = 0 for k, x in enumerate(count): t += x if t >= i: return k mi, mx = inf, - 1 s = cnt = 0 mode = 0 for k, x in enumerate(count): if x: mi = min(mi, k) mx = max(mx, k) s += k * x cnt += x if x > count[mode]: mode = k median = (find(cnt // 2 + 1) if cnt & 1 else (find(cnt // 2) + find(cnt // 2 + 1)) / 2) return [mi, mx, s / cnt, median, mode]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem