Problem Description

You are given an array count of length 256 where count[k] represents how many times the integer k appears in a large sample of integers. All integers in the sample are in the range [0, 255].

Your task is to calculate five statistical measures from this sample:

1. Minimum: The smallest value that appears in the sample (has count > 0)
2. Maximum: The largest value that appears in the sample (has count > 0)
3. Mean: The average value, calculated as the sum of all elements divided by the total number of elements
4. Median:
   • If the total number of elements is odd, the median is the middle element when all elements are sorted
   • If the total number of elements is even, the median is the average of the two middle elements when sorted
5. Mode: The value that appears most frequently in the sample (guaranteed to be unique)

Return these five statistics as an array of floating-point numbers: [minimum, maximum, mean, median, mode].

For example, if count = [0, 1, 3, 4, 0, 0, ...], this means:

• Value 0 appears 0 times
• Value 1 appears 1 time
• Value 2 appears 3 times
• Value 3 appears 4 times
• And so on...

The actual sample would be [1, 2, 2, 2, 3, 3, 3, 3] with 8 total elements.

Answers within 10^-5 of the actual answer will be accepted.

Intuition

Since we're working with a frequency array rather than the actual sample, we need to think about how to extract statistics without reconstructing the entire sample.

For minimum and maximum, we simply need to find the first and last indices where count[k] > 0. As we iterate through the count array, we can track these values.

For mean, we don't need to reconstruct the sample. We can calculate the sum directly by multiplying each value k by its frequency count[k]. The total sum would be 0 * count[0] + 1 * count[1] + 2 * count[2] + .... We also accumulate the total count of elements. The mean is then total_sum / total_count.

For mode, we need to find the index with the highest count. As we iterate through the array, we can keep track of which index has the maximum frequency seen so far.

The median is the trickiest part. If we were to reconstruct the sorted sample, it would look like [0, 0, ..., 1, 1, ..., 2, 2, ...] where each value k appears count[k] times. To find the median:

• If total count is odd, we need the element at position (total_count // 2) + 1
• If total count is even, we need elements at positions total_count // 2 and (total_count // 2) + 1, then average them

Instead of reconstructing the array, we can create a helper function that finds the k-th element in the sorted sample. This function accumulates counts until reaching the desired position. When the cumulative count reaches or exceeds our target position, we've found the value at that position.

By processing the count array in a single pass (except for median calculation), we can efficiently compute all statistics without explicitly creating the large sample array.

Learn more about Math patterns.

Solution Approach

The solution implements the intuition discussed above with a clean single-pass approach for most statistics and a helper function for finding the median.

Helper Function for Finding k-th Element:

def find(i: int) -> int:
    t = 0
    for k, x in enumerate(count):
        t += x
        if t >= i:
            return k

This function finds the value at the i-th position in the sorted sample. It accumulates counts until the cumulative total t reaches or exceeds position i, then returns the current index k.

Main Processing Loop:

mi, mx = inf, -1
s = cnt = 0
mode = 0
for k, x in enumerate(count):
    if x:  # Only process if count[k] > 0
        mi = min(mi, k)      # Update minimum
        mx = max(mx, k)      # Update maximum
        s += k * x           # Add to sum (value * frequency)
        cnt += x             # Add to total count
        if x > count[mode]:  # Update mode if current frequency is higher
            mode = k

The loop iterates through each index k and its count x:

• Minimum: Initialize to infinity, update to the smallest k where x > 0
• Maximum: Initialize to -1, update to the largest k where x > 0
• Sum: Accumulate k * x for calculating mean later
• Total Count: Accumulate all frequencies
• Mode: Track the index with the highest frequency

Median Calculation:

median = (
    find(cnt // 2 + 1) if cnt & 1 else (find(cnt // 2) + find(cnt // 2 + 1)) / 2
)

• If total count is odd (cnt & 1 checks the least significant bit), find the middle element at position cnt // 2 + 1
• If total count is even, find the two middle elements at positions cnt // 2 and cnt // 2 + 1, then average them

Final Return:

return [mi, mx, s / cnt, median, mode]

Returns the five statistics where mean is calculated as s / cnt.

The time complexity is O(n) for the main loop plus O(n) for each median lookup, where n = 256. The space complexity is O(1) as we only use a few variables.

Example Walkthrough

Let's walk through a small example with count = [0, 1, 3, 4, 0, 0, ...] (remaining values are 0).

This represents the sample: [1, 2, 2, 2, 3, 3, 3, 3] (1 appears once, 2 appears 3 times, 3 appears 4 times).

Step 1: Initialize variables

• mi = inf, mx = -1
• s = 0, cnt = 0
• mode = 0

Step 2: Process the count array

k = 0, x = 0: Skip (x = 0)

k = 1, x = 1: (x > 0, so process)

• mi = min(inf, 1) = 1
• mx = max(-1, 1) = 1
• s = 0 + 1*1 = 1
• cnt = 0 + 1 = 1
• count[mode] = 0 < 1, so mode = 1

k = 2, x = 3:

• mi = min(1, 2) = 1
• mx = max(1, 2) = 2
• s = 1 + 2*3 = 7
• cnt = 1 + 3 = 4
• count[mode] = 1 < 3, so mode = 2

k = 3, x = 4:

• mi = min(1, 3) = 1
• mx = max(2, 3) = 3
• s = 7 + 3*4 = 19
• cnt = 4 + 4 = 8
• count[mode] = 3 < 4, so mode = 3

k = 4 to 255: All have x = 0, so skip

Step 3: Calculate mean

• mean = s / cnt = 19 / 8 = 2.375

Step 4: Calculate median

• Total count is 8 (even), so we need positions 4 and 5
• find(4): Accumulate counts: 0→1→4. When we reach k=2, cumulative = 4, which equals our target, so return 2
• find(5): Accumulate counts: 0→1→4→8. When we reach k=3, cumulative = 8 ≥ 5, so return 3
• median = (2 + 3) / 2 = 2.5

Step 5: Return results [1, 3, 2.375, 2.5, 3]

This matches our expectations:

• Minimum: 1 (smallest value present)
• Maximum: 3 (largest value present)
• Mean: (1 + 2 + 2 + 2 + 3 + 3 + 3 + 3) / 8 = 2.375
• Median: Middle of sorted [1, 2, 2, 2, 3, 3, 3, 3] = average of 4th and 5th elements = (2 + 3) / 2 = 2.5
• Mode: 3 (appears 4 times, most frequent)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + k) where n is the length of the count array and k is the total number of elements (sum of all counts).

• The first loop iterates through the entire count array once to calculate minimum, maximum, sum, total count, and mode, which takes O(n) time.
• The find function is called at most 2 times for calculating the median. Each call to find iterates through the count array in the worst case, taking O(n) time per call.
• However, the total iterations across all find calls is bounded by the position we're looking for, which in the worst case is cnt // 2 + 1. Since we need to iterate through counts that sum up to at most cnt // 2 + 1 elements, this contributes O(n) time in the worst case.
• Overall time complexity: O(n) + O(n) = O(n)

Space Complexity: O(1)

• The algorithm uses only a constant amount of extra space for variables: mi, mx, s, cnt, mode, median, and t (inside the find function).
• The find function doesn't use any additional data structures that scale with input size.
• No recursive calls are made, so there's no additional stack space usage.
• The space used doesn't depend on the size of the input array or the values within it.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Median Calculation

Pitfall: A common mistake is using 0-indexed positioning when finding the median, leading to incorrect results. Since the sample is conceptually a sorted array with 1-based indexing for positions, using 0-based indexing would select wrong elements.

Example of Wrong Implementation:

# WRONG: Using 0-based indexing
if total_count & 1:
    median = find_kth_element(total_count // 2)  # Wrong!
else:
    median = (find_kth_element(total_count // 2 - 1) + 
              find_kth_element(total_count // 2)) / 2.0  # Wrong!

Correct Solution:

# CORRECT: Using 1-based indexing for positions
if total_count & 1:
    median = find_kth_element(total_count // 2 + 1)  # Middle element
else:
    median = (find_kth_element(total_count // 2) + 
              find_kth_element(total_count // 2 + 1)) / 2.0

2. Integer Division in Mean/Median Calculation

Pitfall: In Python 2 or when not careful with types, integer division might truncate decimal values, causing precision loss.

Example of Wrong Implementation:

# WRONG: May lose precision in some Python versions
mean = total_sum // total_count  # Integer division
median = (val1 + val2) // 2      # Integer division for even case

Correct Solution:

# CORRECT: Use float division
mean = total_sum / total_count           # Float division
median = (val1 + val2) / 2.0            # Explicitly use float division

3. Not Handling Empty Frequency Arrays Properly

Pitfall: While the problem guarantees at least one element, not checking for empty arrays in the find_kth_element function could cause it to return None or raise an error if called with invalid k values.

Example of Wrong Implementation:

def find_kth_element(k: int) -> int:
    cumulative_count = 0
    for value, frequency in enumerate(count):
        cumulative_count += frequency
        if cumulative_count >= k:
            return value
    # No return statement if k is invalid!

Correct Solution:

def find_kth_element(k: int) -> int:
    cumulative_count = 0
    for value, frequency in enumerate(count):
        cumulative_count += frequency
        if cumulative_count >= k:
            return value
    return -1  # Or raise an exception for invalid k

4. Mode Initialization Problem

Pitfall: Initializing mode_value = 0 assumes that index 0 has the highest frequency initially. If count[0] = 0 but there's a non-zero count elsewhere, the comparison if frequency > count[mode_value] would compare against 0, which works correctly. However, a more robust approach would handle edge cases explicitly.

Potential Issue:

# If all counts are 0 (empty sample), mode_value stays at 0
mode_value = 0
for value, frequency in enumerate(count):
    if frequency > count[mode_value]:
        mode_value = value

More Robust Solution:

mode_value = -1
max_frequency = 0
for value, frequency in enumerate(count):
    if frequency > 0 and frequency > max_frequency:
        max_frequency = frequency
        mode_value = value

5. Floating Point Precision

Pitfall: Not returning consistent float types might cause type mismatches in some test frameworks.

Example of Wrong Implementation:

# WRONG: Mixed types
return [minimum_value, maximum_value, mean, median, mode_value]  # mode_value is int

Correct Solution:

# CORRECT: All values as floats
return [float(minimum_value), float(maximum_value), mean, median, float(mode_value)]