Sponsored
Sponsored
This approach involves iterating over each element in the array and calculating the subarray sum for each index considering the radius. If there is an insufficient number of elements, return -1 for that index. The average is computed using integer division.
Time Complexity: O(n*k), where n is the size of the array.
Space Complexity: O(n), for the output array.
1#include <stdio.h>
2#include <stdlib.h>
3
4int* getAverages(int* nums, int numsSize, int k, int* returnSize) {
5 *returnSize = numsSize;
6 int* avgs = (int*)malloc(numsSize * sizeof(int));
7 int subArraySize = 2 * k + 1;
8
9 for (int i = 0; i < numsSize; ++i) {
10 if (i < k || i >= numsSize - k) {
11 avgs[i] = -1;
12 } else {
13 long sum = 0;
14 for (int j = i - k; j <= i + k; ++j) {
15 sum += nums[j];
16 }
17 avgs[i] = sum / subArraySize;
18 }
19 }
20
21 return avgs;
22}
23
24int main() {
25 int nums[] = {7, 4, 3, 9, 1, 8, 5, 2, 6};
26 int numsSize = sizeof(nums) / sizeof(nums[0]);
27 int k = 3;
28 int returnSize;
29 int* averages = getAverages(nums, numsSize, k, &returnSize);
30
31 for (int i = 0; i < returnSize; ++i) {
32 printf("%d ", averages[i]);
33 }
34
35 free(averages);
36 return 0;
37}This C code implements the brute force approach where for each index, we calculate the sum of its k-radius subarray. If the index doesn't have enough elements on either side, it sets the result for that position to -1.
The sliding window approach helps optimize the brute force method by avoiding redundant calculations when sums overlap, significantly reducing the time complexity.
Time Complexity: O(n), as each element is added and removed from the sum at most once.
Space Complexity: O(n), for storing the results.
1#include <vector>
#include <iostream>
std::vector<int> getAverages(std::vector<int>& nums, int k) {
int n = nums.size();
std::vector<int> avgs(n, -1);
int subArraySize = 2 * k + 1;
long long windowSum = 0;
for (int i = 0; i < n; ++i) {
windowSum += nums[i];
if (i >= subArraySize) {
windowSum -= nums[i - subArraySize];
}
if (i >= subArraySize - 1) {
avgs[i - k] = windowSum / subArraySize;
}
}
return avgs;
}
int main() {
std::vector<int> nums = {7, 4, 3, 9, 1, 8, 5, 2, 6};
int k = 3;
std::vector<int> averages = getAverages(nums, k);
for (auto avg : averages) {
std::cout << avg << " ";
}
return 0;
}The C++ implementation uses a sliding window technique, maintaining a running sum by adding the new element and subtracting the old one beyond the window size.