Statistics from a Large Sample - Practice Coding Problems

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

Input & Output

Example 1 — Basic Case

$ Input: count = [0,1,3,4]

› Output: [1.0,3.0,2.25,2.5,3.0]

💡 Note: Sample represents: value 1 appears 1 time, value 2 appears 3 times, value 3 appears 4 times. Min=1, Max=3, Mean=(1×1+2×3+3×4)/8=18/8=2.25, Median of [1,2,2,2,3,3,3,3] is (2+3)/2=2.5, Mode=3 (appears 4 times)

Example 2 — Single Value

$ Input: count = [0,4,0,0,0,0]

› Output: [1.0,1.0,1.0,1.0,1.0]

💡 Note: Only value 1 appears 4 times. All statistics equal 1.0: min=1, max=1, mean=1, median=1, mode=1

Example 3 — Wider Range

$ Input: count = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,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,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,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: [100.0,140.0,123.33333333333333,110.0,140.0]

💡 Note: Values 100 (freq 1), 110 (freq 2), 140 (freq 3). Sample: [100,110,110,140,140,140]. Min=100, Max=140, Mean=(100+110+110+140+140+140)/6=740/6≈123.33, Median=(110+140)/2=125, Mode=140

Constraints

count.length == 256
0 ≤ count[i] ≤ 10⁹
1 ≤ sum(count) ≤ 10⁹
The mode is guaranteed to be unique

Visualization

Tap to expand

Understanding the Visualization

Input

Frequency array where count[i] = occurrences of value i

Process

Calculate statistics without reconstructing full array

Output

Return [min, max, mean, median, mode] as floats

Key Takeaway

🎯 Key Insight: Process frequency counts directly instead of reconstructing the massive original array - achieves O(1) space complexity!

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Facebook 18

The key insight is to process frequency counts directly without reconstructing the original array. We can calculate all statistics in O(1) space by scanning the fixed-size frequency array: find min/max at boundaries, compute mean using weighted sums, find median with cumulative frequencies, and identify mode as the index with maximum frequency. Best approach is Direct Frequency Processing with Time: O(1), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Direct Frequency Processing	O(1)	O(1)	Calculate statistics directly from frequency counts without reconstructing the array
Reconstruct Full Array	O(n log n)	O(n)	Recreate the original array from frequency counts, then calculate statistics

Direct Frequency Processing — Algorithm Steps

Step 1: Find min/max by scanning frequency array boundaries
Step 2: Calculate mean using weighted sum of frequencies
Step 3: Find median using cumulative frequency counting
Step 4: Find mode as index with maximum frequency

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Boundaries

Find min/max by checking first/last non-zero frequencies

Weighted Sum

Calculate mean using value × frequency for each element

Cumulative Count

Find median using cumulative frequency without sorting

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void solution(int* count, int countSize, double* result) {
    // Find total count
    int total = 0;
    for (int i = 0; i < 256; i++) {
        total += count[i];
    }
    if (total == 0) {
        result[0] = result[1] = result[2] = result[3] = result[4] = 0.0;
        return;
    }
    
    // Find minimum
    int minimum = -1;
    for (int i = 0; i < 256; i++) {
        if (count[i] > 0) {
            minimum = i;
            break;
        }
    }
    
    // Find maximum
    int maximum = -1;
    for (int i = 255; i >= 0; i--) {
        if (count[i] > 0) {
            maximum = i;
            break;
        }
    }
    
    // Calculate mean using weighted sum
    long long weightedSum = 0;
    for (int i = 0; i < 256; i++) {
        weightedSum += (long long) i * count[i];
    }
    double mean = (double) weightedSum / total;
    
    // Find median using cumulative frequency
    int medianPos1 = (total - 1) / 2;
    int medianPos2 = total / 2;
    
    int cumulative = 0;
    int median1 = -1, median2 = -1;
    
    for (int i = 0; i < 256; i++) {
        cumulative += count[i];
        if (median1 == -1 && cumulative > medianPos1) {
            median1 = i;
        }
        if (median2 == -1 && cumulative > medianPos2) {
            median2 = i;
        }
        if (median1 != -1 && median2 != -1) {
            break;
        }
    }
    
    double median = (median1 + median2) / 2.0;
    
    // Find mode
    int mode = 0;
    int maxCount = count[0];
    for (int i = 1; i < 256; i++) {
        if (count[i] > maxCount) {
            maxCount = count[i];
            mode = i;
        }
    }
    
    result[0] = minimum;
    result[1] = maximum;
    result[2] = mean;
    result[3] = median;
    result[4] = mode;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int count[256] = {0};
    int idx = 0;
    char* token = strtok(line + 1, ",]");
    
    while (token != NULL && idx < 256) {
        count[idx++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    double result[5];
    solution(count, 256, result);
    
    printf("[%g,%g,%g,%g,%g]\n", result[0], result[1], result[2], result[3], result[4]);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Single pass through fixed-size array of 256 elements regardless of sample size

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables, no additional data structures

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

1.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Direct Frequency Processing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler