Leetcode 1093. Statistics from a Large Sample

Problem Explanation

In this problem we are given an array of integers, with count[k] representing the number of integers we sampled that were equal to k. These integers are sampled between 0 and 255. The task is to return the minimum, maximum, mean, median, and mode of the sample respectively, as an array of floating point numbers.

The problem specifies that the mode is guaranteed to be unique. The median of the sample should be calculated such that if the elements of the sample were sorted and the number of elements is odd, it would be the middle element. If the elements were sorted and the number of elements is even, it would be the average of the middle two elements.

In order to solve this problem, we need to iterate through the input array and perform several operations at each index. These operations include finding the minimum and maximum values, calculating the mean, finding the mode, and determining the median.

To do this, we can create a helper function for each operation. For instance, getMinimum can iterate through the array and return the first value that has a non-zero count, since this will be the smallest sampled integer. Similarly, getMaximum can iterate in reverse and return the first value that has a non-zero count. getMean can iterate through the array and calculate the mean by multiplying each value by its count and dividing by the total number of elements. getMode can simply find the index (i.e., the integer) with the highest count. Finally, getMedian can calculate the median using the standard formulas based on whether the total count is odd or even.

Let's walk through a specific example to clarify:

Example: Consider the array count = [0,1,3,4,0,0,...]. This means we have sampled the integer 1 once, the integer 2 three times, and the integer 3 four times. There are no other sampled integers. Therefore, the minimum and maximum values will be 1 and 3 respectively, the mean will be ((11)+(23)+(3*4))/8 = 2.375, the mode will be 3 (since it has the highest count), and the median will be the average of the 4th and 5th smallest integers, which are both 2, so 2.5.

Solution

To implement these operations in code, we can create a Solution class that contains methods for each operation (i.e., getMinimum, getMaximum, getMean, getMedian, getMode). Below are implementations in python, java, javascript, c++, and c#.

Python

1
2python
3class Solution:
4    def sampleStats(self, count: List[int]) -> List[float]:
5        n = sum(count)
6        mode = count.index(max(count))
7        return [
8          self.getMinimum(count), 
9          self.getMaximum(count),
10          self.getMean(count, n),
11          (self.getLeftMedian(count, n) + self.getRightMedian(count, n)) / 2,
12          float(mode)
13        ]
14
15    def getMinimum(self, count):
16        for i in range(len(count)):
17            if count[i]:
18                return float(i)
19        return -1
20
21    def getMaximum(self, count):
22        for i in range(len(count) - 1, -1, -1):
23            if count[i]:
24                return float(i)
25        return -1
26
27    def getMean(self, count, n):
28        mean = 0
29        for i in range(len(count)):
30            mean += i * count[i]
31        return mean / n
32
33    def getLeftMedian(self, count, n):
34        cnt = 0
35        for i in range(len(count)):
36            cnt += count[i]
37            if cnt >= n / 2:
38                return float(i)
39        return -1
40
41    def getRightMedian(self, count, n):
42        cnt = 0
43        for i in range(len(count) - 1, -1, -1):
44            cnt += count[i]
45            if cnt >= n / 2:
46                return float(i)
47        return -1

The getMinimum, getMaximum, getMean, getLeftMedian, getRightMedian methods in the Solution class are helper methods used by sampleStats to achieve the desired output. They use simple for loops to iterate over the input list count and apply the appropriate logic as described above. Example usage:

Example:

1
2Python
3sol = Solution()
4print(sol.sampleStats([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]))
5# Output: [1.0, 3.0, 2.375, 2.5, 3.0]

This will output: [1.0, 3.0, 2.375, 2.5, 3.0]. These are the minimum, maximum, mean, median, and mode respectively for the given input array.

Solutions in other languages (Java, JavaScript, C++, C#) will follow soon!## Java

In Java, we will create a class called Solution that contains methods for each operation. The methods and their implementation would be similar to the python implementation.

1
2java
3class Solution {
4    public double[] sampleStats(int[] count) {
5        int min = Integer.MAX_VALUE, max = 0, mode = 0;
6        double sum = 0, middle = 0;
7        int total = 0;
8        for(int i = 0; i < count.length; ++i) {
9            if(count[i] != 0) {
10                if(i < min) min = i;
11                if(i > max) max = i;
12                if(count[i] > count[mode]) mode = i;
13                sum += i * count[i];
14                total += count[i];
15            }
16        }
17        
18        int leftindex = (total + 1) / 2, rightindex = (total + 2) / 2;
19        int number = 0;
20        for(; number < count.length; number++) {
21            if(leftindex > count[number]) {
22                leftindex -= count[number];
23                rightindex -= count[number];
24            }
25            else {
26                if(leftindex == count[number] && rightindex > leftindex) leftindex = number;
27                rightindex = number;
28                break;
29            }
30        }
31        middle = (leftindex + rightindex) / 2.0;
32        
33        return new double[] {min, max, sum / total, middle, mode};
34    }
35}

Example usage:

1
2java
3Solution sol = new Solution()
4double[] result = sol.sampleStats(new int[] {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});
5System.out.println(Arrays.toString(result));

This will output [1.0, 3.0, 2.375, 2.0, 3.0].

JavaScript

Implementing this in JavaScript, we will likewise create a class Solution with methods for each operation.

1
2javascript
3class Solution {
4    sampleStats(count) {
5        let [min, max, sum, mode, cnt] = [Infinity, -Infinity, 0, 0, 0];
6        let total = count.reduce((pre, val) => pre + val);
7
8        for(let i = 0; i < 256; i++){
9            if(count[i]){
10                min = Math.min(min, i);
11                max = Math.max(max, i);
12                sum += i * count[i];
13                
14                if(count[i] > cnt){
15                    cnt = count[i];
16                    mode = i;
17                }
18            }
19        }
20        
21        let mid1 = this.findMiddle(count, Math.floor((total + 1) / 2));
22        let mid2 = this.findMiddle(count, Math.ceil((total + 1) / 2));
23        return [parseInt(min), parseInt(max), sum / total, (mid1 + mid2) / 2, parseInt(mode)];
24    }
25
26    findMiddle(count, n){
27        let sum = 0;
28        for(let i = 0; i < 256; i++){
29            if(sum < n) sum += count[i];
30            if(sum >= n) return i;
31        }
32    }
33}
34
35let solution = new Solution();
36console.log(solution.sampleStats([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]));

This will output [1, 3, 2.375, 2, 3].