LeetCode 1093. Statistics from a Large Sample Solution in Java, C++, Python & More | Explanation + Code

Description

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.

Solutions

Solution 1

PythonJavaC++GoTypeScript

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](code-box)

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; } } } }(code-box)

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}; } };(code-box)

func sampleStats(count []int) []float64 { find := func(i int) int { for k, t := 0, 0; ; k++ { t += count[k] if t >= i { return k } } } mi, mx := 1<<30, -1 s, cnt, mode := 0, 0, 0 for k, x := range count { if x > 0 { mi = min(mi, k) mx = max(mx, k) s += k * x cnt += x if x > count[mode] { mode = k } } } var median float64 if cnt&1 == 1 { median = float64(find(cnt/2 + 1)) } else { median = float64(find(cnt/2)+find(cnt/2+1)) / 2 } return []float64{float64(mi), float64(mx), float64(s) / float64(cnt), median, float64(mode)} }(code-box)

function sampleStats(count: number[]): number[] { const find = (i: number): number => { for (let k = 0, t = 0; ; ++k) { t += count[k]; if (t >= i) { return k; } } }; let mi = 1 << 30; let mx = -1; let [s, cnt, mode] = [0, 0, 0]; for (let k = 0; k < count.length; ++k) { if (count[k] > 0) { mi = Math.min(mi, k); mx = Math.max(mx, k); s += k * count[k]; cnt += count[k]; if (count[k] > count[mode]) { mode = k; } } } const median = cnt % 2 === 1 ? find((cnt >> 1) + 1) : (find(cnt >> 1) + find((cnt >> 1) + 1)) / 2; return [mi, mx, s / cnt, median, mode]; }(code-box)