Description
You are given a 0-indexed array nums of n integers, and an integer k.
The k-radius average for a subarray of nums centered at some index i with the radius k is the average of all elements in nums between the indices i - k and i + k (inclusive). If there are less than k elements before or after the index i, then the k-radius average is -1.
Build and return an array avgs of length n where avgs[i] is the k-radius average for the subarray centered at index i.
The average of x elements is the sum of the x elements divided by x, using integer division. The integer division truncates toward zero, which means losing its fractional part.
For example, the average of four elements 2, 3, 1, and 5 is (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75, which truncates to 2.
Example 1:
Input: nums = [7,4,3,9,1,8,5,2,6], k = 3
Output: [-1,-1,-1,5,4,4,-1,-1,-1]
Explanation:
avg[0],avg[1], andavg[2]are-1because there are less than k elements before each index.- The sum of the subarray centered at index 3 with radius 3 is:
7 + 4 + 3 + 9 + 1 + 8 + 5 = 37. Using integer division,avg[3] = 37 / 7 = 5. - For the subarray centered at index 4,
avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4. - For the subarray centered at index 5,
avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4. avg[6],avg[7], andavg[8]are-1because there are less thankelements after each index.
Example 2:
Input: nums = [100000], k = 0
Output: [100000]
Explanation:
- The sum of the subarray centered at index 0 with radius 0 is: 100000.
avg[0] = 100000 / 1 = 100000.
Example 3:
Input: nums = [8], k = 100000
Output: [-1]
Explanation:
avg[0]is -1 because there are less thankelements before and after index 0.
Constraints:
n == nums.length1 <= n <= 10^50 <= nums[i],k <= 10^5
Solution
Using Prefix Sum (Preprocessing) technique
This is prefix sum problem because we are required to find the sum of subarrays multiple times.
In this case, if i - k < 0 then we have to add -1. Similarly, if i + k >= nums.length then also we have to add -1.
For numbers in between, these two range, we want to find below. One of the constraints is that the number can be upto 100000 and length of array can be 100000 as well. In this case, it may overflow Integer limits. So, we have to use Long data type for calculating sum of our window just in case the window is large enough to cross Integer boundaries. We will also have one more element in prefix sum to make it easier to calculate average in the middle.
The pseudocode would look like this.
1Define sum array with same size as nums + 1
2sum[0] = 0
3for i = 0; i < nums.length; i++
4 sum[i + 1] = sum[i] + nums[i];
5averages = new int[nums.length]
6for i = 0; i < nums.length; i++
7 if (i - k >= 0 AND i + k < nums.length)
8 averages[i] = int()((sum[i + k + 1] - sum[i - k]) / (2 * k + 1))
9return averages
The code for this logic looks like below.
1class Solution {
2 public int[] getAverages(int[] nums, int k) {
3 long[] sum = new long[nums.length + 1];
4 for (int i = 0; i < nums.length; ++i) {
5 sum[i + 1] = sum[i] + nums[i];
6 }
7 System.out.println(Arrays.toString(sum));
8 int[] averages = new int[nums.length];
9 Arrays.fill(averages, -1);
10 for (int i = 0; i < nums.length; ++i) {
11 if (i - k >= 0 && i + k < nums.length) {
12 averages[i] = (int) ((sum[i + k + 1] - sum[i - k]) / (2 * k + 1));
13 }
14 }
15 System.out.println(Arrays.toString(averages));
16 return averages;
17 }
18}
Using Sliding Window technique
Now, if we think of this problem from different perspective, it can also be solved using Sliding window where our window is valid as long as the number of elements are within i -k and i + k. So, we can use sliding window to calculate the sum of elements between those window and in next iteration calculate the average.
1class Solution {
2 public int[] getAveragesUsingSliding(int[] nums, int k) {
3 int left = 0, right = 0;
4 long currentSum = 0;
5 int i = 0;
6 long[] sum = new long[nums.length];
7 while (right < nums.length) {
8 currentSum += nums[right];
9 sum[right] = -1;
10 if (right - left == 2*k) {
11 sum[i + k] = currentSum;
12 i++;
13 currentSum -= nums[left];
14 left++;
15 }
16 right++;
17 }
18 right = 0;
19 int[] averages = new int[nums.length];
20 while (right < nums.length) {
21 if (sum[right] != -1) {
22 averages[right] = (int) (sum[right] / (2 * k + 1));
23 } else {
24 averages[right] = -1;
25 }
26 right++;
27 }
28 return averages;
29 }
30}
If we look at athese carefully, they are doing almost similar task except that in the first iteration we are calculating sum and in the next iteration we are calculating average. This reduces time to solution but time complexity still remains O(n). We can reduce space as well by removing unnecessary sum variable and directly calculate average. We can remove one of the iterations as well if we do both in single iteration. Again, ensure that currentSum variable is of type long and not int otherwise it may overflow.
1class Solution {
2 public int[] getAveragesUsingSliding(int[] nums, int k) {
3 int left = 0, right = 0;
4 long currentSum = 0;
5 int i = 0;
6 int[] averages = new int[nums.length];
7 while (right < nums.length) {
8 currentSum += nums[right];
9 averages[right] = -1;
10 if (right - left == 2 * k) {
11 averages[i + k] = (int) (currentSum / (2*k + 1));
12 i++;
13 currentSum -= nums[left];
14 left++;
15 }
16 right++;
17 }
18 System.out.println(Arrays.toString(averages));
19 return averages;
20 }
21}
We can still remove i variable because we are using that as an additional value to easily track where to insert new elements. We can do something like below to remove i.
1averages[k + left] = (int) (currentSum / (2*k + 1));
Comments