702663. Mean of range in array
Easy
Mean of Range in Array
Slug: mean-of-range-in-array2123
Difficulty: Easy
Id: 702663
Topic Tags: prefix-sum, Arrays, Data Structures, Algorithms
Company Tags: None
Summary
The problem is to find the mean (average) of the range of each subarray in a given array. The range of an array is calculated as the maximum value minus the minimum value.
Detailed Explanation
To solve this problem, we can use the concept of prefix sum and the idea that the sum of all elements in an array from index i to j is equal to the sum of all elements from index 0 to i-1 plus the element at index i. We first calculate the prefix sum for the given array, then for each subarray (from index i to j), we subtract the prefix sum up to i-1 and add the prefix sum up to j, which gives us the sum of the elements in that subarray. Finally, we divide this sum by the length of the subarray to get its mean.
Here is a step-by-step breakdown of the solution:
- Calculate the prefix sum for the given array.
- Initialize a variable to store the total range and another to store the count of subarrays.
- Iterate over each subarray (from index i to j):
- Subtract the prefix sum up to i-1 from the current prefix sum, which gives us the sum of elements in the current subarray.
- Add the prefix sum up to j to get the total sum of elements in all subarrays ending at j.
- Calculate the range of this subarray as the difference between the maximum and minimum values.
- Divide the range by the length of the subarray (j-i+1) to get its mean.
- Add the mean to the total range and increment the count.
- Return the average of all means calculated.
Optimized Solutions
Java
public class MeanOfRangeInArray {
public static double findMean(int[] arr) {
int n = arr.length;
long[] prefixSum = new long[n+1];
for (int i = 0; i < n; i++) {
prefixSum[i+1] = prefixSum[i] + arr[i];
}
double totalRange = 0, count = 0;
for (int i = 0; i < n; i++) {
int leftMax = arr[i], rightMin = arr[i];
for (int j = i; j < n; j++) {
leftMax = Math.max(leftMax, arr[j]);
rightMin = Math.min(rightMin, arr[j]);
double range = (leftMax - rightMin);
totalRange += range;
count++;
}
}
return totalRange / count;
}
}