#1093 Leetcode Statistics from a Large Sample Solution in C, C++, Java, JavaScript, Python, C# Leetcode

Algorithm

Problem Name: 1093. Statistics from a Large Sample

Problem Link: https://leetcode.com/problems/statistics-from-a-large-sample/

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

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


class Solution {
    public double[] sampleStats(int[] num) {
        Map map = new HashMap<>();
        double sum = 0;
        int currMin = Integer.MAX_VALUE;
        int currMax = Integer.MIN_VALUE;
        int currMod = -1;
        int modCount = 0;
        int count = 0;
        
        for (int i = 0; i  <  num.length; i++) {
            sum += num[i] * i;
            if (num[i] > 0) {
                currMin = Math.min(currMin, i);
                currMax = Math.max(currMax, i);
                map.put(i, num[i]);
                if (map.get(i) > modCount) {
                    modCount = num[i];
                    currMod = i;
                }
                count += num[i];
            }
        }
        
        return new double[]{
            (double) currMin,
            (double) currMax,
            sum / count,
            count % 2 == 0 ? getEvenMedian(num, count) : getOddMedian(num, count),
            (double) currMod
        };
    }
    
    private double getEvenMedian(int[] num, int count) {
        int p1 = count/2;
        int p2 = count/2 + 1;
        double sum = 0;
        int currCount = 0;
        int i = 0;
        
        while (i  <  num.length) {
            if (num[i] != 0) {
                currCount += num[i];
                if (currCount >= p1 && currCount >= p2) {
                    return (double) i;
                }
                
                if (currCount >= p1 && currCount  <  p2) {
                    sum = i;
                    i++;
                    break;
                }
            }   
            
            i++;
        }        
        
        while (i  <  num.length) {
            if (num[i] != 0) {
                currCount += num[i];
                if (currCount >= p2) {
                    sum += i;
                    break;
                }
            }
            
            i++;
        }
        
        return sum / 2;
    }
    
    private double getOddMedian(int[] num, int count) {
        int p1 = count/2 + 1;
        int currCount = 0;
        for (int i = 0; i  <  num.length; i++) {
            if (num[i] != 0) {
                currCount += num[i];
                if (currCount >= p1) {
                    return (double) i;
                }
            }
        }
        
        return (double) 1;
    }
}

Copy The Code & Try With Live Editor

Input

–

cmd

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

–

cmd

[1.00000,3.00000,2.37500,2.50000,3.00000]

#2 Code Example with Javascript Programming

Code - Javascript Programming


const sampleStats = function(count) {
  const n = count.length
  let numElems = 0
  let sum = 0
  let min = n - 1
  let max = 0
  let modVal = 0
  let modIdx = 0
  for (let i = 0; i  <  n; i++) {
    if (count[i]) {
      min = Math.min(i, min)
      max = Math.max(i, max)
      if (count[i] > modVal) {
        modVal = count[i]
        modIdx = i
      }
      sum += i * count[i]
      numElems += count[i]
    }
  }
  const half = Math.floor(numElems / 2)
  let median
  for (let i = 0, c = 0, last = 0; i  <  n; i++) {
    if (count[i]) {
      c += count[i]
      if (c > half) {
        if (numElems % 2 === 0 && c - count[i] === half) {
          median = (i + last) / 2
        } else {
          median = i
        }
        break
      }
      last = i
    }
  }
  return [min, max, sum / numElems, median, modIdx]
}

Copy The Code & Try With Live Editor

Input

–

cmd

Output

–

cmd

[1.00000,3.00000,2.37500,2.50000,3.00000]

#3 Code Example with Python Programming

Code - Python Programming


class Solution:
    def sampleStats(self, count: List[int]) -> List[float]:
        arr = [(i, c * 1.0) for i, c in enumerate(count) if c]
        acc = list(itertools.accumulate(count, lambda x, y: x + y))
        mean = sum(i * c for i, c in arr) / acc[-1] 
        mode = max(arr, key = lambda x: x[1])[0] * 1.0
        m1 = bisect.bisect(acc, (acc[-1] - 1) // 2)
        m2 = bisect.bisect(acc, acc[-1] // 2)
        return [arr[0][0] * 1.0, arr[-1][0] * 1.0, mean, (m1 + m2) / 2.0, mode]

Copy The Code & Try With Live Editor

Input

–

cmd

Output

–

cmd

[1.00000,3.00000,2.37500,2.50000,3.00000]

Demonstration

Previous
#1092 Leetcode Shortest Common Supersequence Solution in C, C++, Java, JavaScript, Python, C# Leetcode

Next
#1094 Leetcode Car Pooling Solution in C, C++, Java, JavaScript, Python, C# Leetcode

Try With Live Editor

Category - Leetcode Online Judge Maniruzzaman Akash 1 year ago 697 0