Statistics from a Large Sample

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 within10-5 of the actual answer will be accepted.

Examples

Example 1

1
2
3
4
5
6
7


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

1
2
3
4
5
6
7


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^9
1 <= sum(count) <= 10^9
The mode of the sample that count represents is unique.

Solution

Method 1 -

Method 1 – Prefix Sums and Counting

Intuition

Since the sample is represented by a frequency array, we can efficiently compute statistics by scanning through the array and using prefix sums to find the mean, median, and mode. The median can be found by walking through the counts and tracking the cumulative frequency.

Approach

Initialize variables for minimum, maximum, total sum, total count, and mode.
Iterate through the count array:
- For each value, if its count is nonzero, update minimum and maximum.
- Add to the total sum and total count.
- Track the mode by keeping the value with the highest count.
Compute the mean as total sum divided by total count.
To find the median:
- Walk through the count array, accumulating frequencies.
- For odd total count, find the middle value.
- For even total count, find the two middle values and average them.
Return the statistics as a float array: [minimum, maximum, mean, median, mode].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


class Solution {
    public double[] sampleStats(int[] count) {
        double[] ans = new double[5];
        int n = count.length;
        int min = -1, max = -1, mode = 0, modeCount = 0;
        long total = 0, totalCount = 0;
        for (int i = 0; i < n; i++) {
            if (count[i] > 0) {
                if (min == -1) min = i;
                max = i;
                total += (long) i * count[i];
                totalCount += count[i];
                if (count[i] > modeCount) {
                    modeCount = count[i];
                    mode = i;
                }
            }
        }
        ans[0] = min;
        ans[1] = max;
        ans[2] = (double) total / totalCount;
        // Median
        int left = 0, right = n - 1;
        int lCount = 0, rCount = 0;
        int lVal = min, rVal = max;
        long mid1 = (totalCount + 1) / 2, mid2 = (totalCount + 2) / 2;
        long cnt = 0;
        double median = 0;
        for (int i = 0; i < n; i++) {
            if (count[i] > 0) {
                cnt += count[i];
                if (cnt >= mid1 && median == 0) {
                    median += i;
                }
                if (cnt >= mid2) {
                    median += i;
                    break;
                }
            }
        }
        ans[3] = median / 2.0;
        ans[4] = mode;
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


from typing import List

class Solution:
    def sampleStats(self, count: List[int]) -> List[float]:
        n = len(count)
        total = 0
        total_count = 0
        min_val = None
        max_val = None
        mode = 0
        mode_count = 0
        for i, c in enumerate(count):
            if c > 0:
                if min_val is None:
                    min_val = float(i)
                max_val = float(i)
                total += i * c
                total_count += c
                if c > mode_count:
                    mode_count = c
                    mode = float(i)
        mean = total / total_count
        # Median
        mid1 = (total_count + 1) // 2
        mid2 = (total_count + 2) // 2
        cnt = 0
        median = 0.0
        for i, c in enumerate(count):
            if c > 0:
                cnt += c
                if cnt >= mid1 and median == 0.0:
                    median += i
                if cnt >= mid2:
                    median += i
                    break
        median /= 2.0
        return [min_val, max_val, mean, median, mode]

Complexity

⏰ Time complexity: O(256) — We scan the count array a constant number of times.
🧺 Space complexity: O(1) — Only a fixed number of variables are used for statistics.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 -#

Method 1 – Prefix Sums and Counting#

Intuition#

Approach#

Code#

Complexity#