# Statistics from a Large Sample
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/statistics-from-a-large-sample)
Canonical: https://scaleengineer.com/dsa/problems/statistics-from-a-large-sample
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Probability and Statistics](https://scaleengineer.com/dsa/patterns/probability-and-statistics)
**Data structures:** Array
---
## Problem
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] <= 109`
* `1 <= sum(count) <= 109`
* The mode of the sample that `count` represents is **unique**.

# Approaches
## Brute Force by Reconstructing the Sample
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.
**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.
**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.
### Explanation
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.
```java
// NOTE: This approach is not feasible for the given constraints and will likely fail.
public double[] sampleStats_bruteForce(int[] count) {
    long n_long = 0;
    for (int c : count) {
        n_long += c;
    }
    // This check highlights the impracticality.
    if (n_long > Integer.MAX_VALUE || n_long > 200_000_000) { // A practical memory limit
        System.err.println("Sample size too large to reconstruct in memory.");
        // This approach fails here. We would return an empty/error result.
        return new double[5];
    }
    int n = (int) n_long;
    if (n == 0) return new double[]{0,0,0,0,0};

    int[] sample = new int[n];
    int index = 0;
    for (int i = 0; i < 256; i++) {
        for (int j = 0; j < count[i]; j++) {
            sample[index++] = i;
        }
    }

    double minimum = sample[0];
    double maximum = sample[n - 1];

    long sum = 0;
    for (int val : sample) {
        sum += val;
    }
    double mean = (double) sum / n;

    double median;
    if (n % 2 == 1) {
        median = sample[n / 2];
    } else {
        median = (sample[n / 2 - 1] + sample[n / 2]) / 2.0;
    }

    // Mode calculation from sorted array
    int mode = 0;
    int maxFreq = 0;
    if (n > 0) {
        int currentFreq = 1;
        mode = sample[0];
        maxFreq = 1;
        for (int i = 1; i < n; i++) {
            if (sample[i] == sample[i-1]) {
                currentFreq++;
            } else {
                currentFreq = 1;
            }
            if (currentFreq > maxFreq) {
                maxFreq = currentFreq;
                mode = sample[i];
            }
        }
    }

    return new double[]{minimum, maximum, mean, median, mode};
}
```
### 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.

## Efficient Single-Pass Calculation
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.
**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.
**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.
### Explanation
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:
```java
class Solution {
    public double[] sampleStats(int[] count) {
        long total_count = 0;
        for (int c : count) {
            total_count += c;
        }

        if (total_count == 0) {
            return new double[]{0.0, 0.0, 0.0, 0.0, 0.0};
        }

        double minimum = -1.0;
        double maximum = 0.0;
        long total_sum = 0L;
        int max_freq = 0;
        double mode = 0.0;

        long median_idx1 = (total_count - 1) / 2;
        long median_idx2 = total_count / 2;
        int median1_val = -1;
        int median2_val = -1;

        long current_elements = 0;
        for (int i = 0; i < 256; i++) {
            if (count[i] > 0) {
                // Minimum
                if (minimum == -1.0) {
                    minimum = i;
                }
                // Maximum
                maximum = i;
                // Sum for Mean
                total_sum += (long)i * count[i];
                // Mode
                if (count[i] > max_freq) {
                    max_freq = count[i];
                    mode = i;
                }

                // Median
                long next_elements = current_elements + count[i];
                if (median1_val == -1 && current_elements <= median_idx1 && median_idx1 < next_elements) {
                    median1_val = i;
                }
                if (median2_val == -1 && current_elements <= median_idx2 && median_idx2 < next_elements) {
                    median2_val = i;
                }
                current_elements = next_elements;
            }
        }

        double mean = (double)total_sum / total_count;
        double median = (median1_val + median2_val) / 2.0;

        return new double[]{minimum, maximum, mean, median, mode};
    }
}
```
### 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.

# Solutions
### Java

```java
class Solution {
private
  int[] count;
public
  double[] sampleStats(int[] count) {
    this.count = count;
    int mi = 1 << 30, mx = -1;
    long s = 0;
    int cnt = 0;
    int mode = 0;
    for (int k = 0; k < count.length; ++k) {
      if (count[k] > 0) {
        mi = Math.min(mi, k);
        mx = Math.max(mx, k);
        s += 1L * k * count[k];
        cnt += count[k];
        if (count[k] > count[mode]) {
          mode = k;
        }
      }
    }
    double median = cnt % 2 == 1 ? find(cnt / 2 + 1)
                                 : (find(cnt / 2) + find(cnt / 2 + 1)) / 2.0;
    return new double[]{mi, mx, s * 1.0 / cnt, median, mode};
  }
private
  int find(int i) {
    for (int k = 0, t = 0;; ++k) {
      t += count[k];
      if (t >= i) {
        return k;
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<double> sampleStats(vector<int> &count) {
    auto find = [&](int i) -> int {
      for (int k = 0, t = 0;; ++k) {
        t += count[k];
        if (t >= i) {
          return k;
        }
      }
    };
    int mi = 1 << 30, mx = -1;
    long long s = 0;
    int cnt = 0, mode = 0;
    for (int k = 0; k < count.size(); ++k) {
      if (count[k]) {
        mi = min(mi, k);
        mx = max(mx, k);
        s += 1LL * k * count[k];
        cnt += count[k];
        if (count[k] > count[mode]) {
          mode = k;
        }
      }
    }
    double median = cnt % 2 == 1 ? find(cnt / 2 + 1)
                                 : (find(cnt / 2) + find(cnt / 2 + 1)) / 2.0;
    return vector<double>{(double)mi, (double)mx, s * 1.0 / cnt, median,
                          (double)mode};
  }
};

```

### Python

```python
class Solution:
    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]

```