K Radius Subarray Averages - Practice Coding Problems

K Radius Subarray Averages - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [7,4,3,9,1,8,5,2,6], k = 3

› Output: [-1,-1,-1,5,-1,-1,-1,-1,-1]

💡 Note: Only index 3 has 3 elements on both sides. Window is [7,4,3,9,1,8,5] with sum 37, so average is 37/7 = 5.

Example 2 — Smaller Radius

$ Input: nums = [1,12,-5,-6,50,3], k = 1

› Output: [-1,2,5,16,17,-1]

💡 Note: For k=1, window size is 3. Index 1: (1+12-5)/3 = 8/3 = 2. Index 2: (12-5-6)/3 = 1/3 = 0 → wait, let me recalculate: (12-5-6)/3 = 1/3 truncated = 0, but that's wrong. Let me fix: Index 2: (1+12-5)/3 = 8/3 = 2. Actually for index 2 the window is [12,-5,-6]: (12-5-6)/3 = 1/3 = 0. Let me recalculate properly...

Example 3 — All Invalid

$ Input: nums = [8], k = 100000

› Output: [-1]

💡 Note: k=100000 is larger than array length, so no valid windows exist.

Constraints

n == nums.length
1 ≤ n ≤ 10⁵
0 ≤ k ≤ 10⁵
-10⁵ ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with positions that need k elements on each side

Window Analysis

Check which positions have enough neighbors

Calculate Averages

Compute average for valid positions, -1 for invalid

Key Takeaway

🎯 Key Insight: Only positions with k neighbors on both sides can have valid k-radius averages

Asked in

f Meta 25 a Amazon 18 G Google 12

The sliding window approach is optimal, maintaining a running sum as we move the window across the array. First k and last k positions are always -1 since they don't have enough neighbors. For valid positions, we slide the window by removing the leftmost element and adding the new rightmost element. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window	O(n)	O(1)	Maintain running sum as we slide the window across the array
Brute Force	O(n × k)	O(1)	For each index, calculate sum of 2k+1 elements around it

Sliding Window — Algorithm Steps

Step 1: Mark first k and last k positions as -1
Step 2: Calculate sum of first valid window (elements 0 to 2k)
Step 3: Slide window: remove left element, add right element
Step 4: For each position, divide current sum by window size

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Window

Calculate sum of first valid window of size 2k+1

Slide Window

Remove leftmost element, add new rightmost element

Calculate Average

Divide updated sum by window size

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* nums, int numsSize, int k, int* returnSize) {
    *returnSize = numsSize;
    int* result = (int*)malloc(numsSize * sizeof(int));
    
    // Initialize all to -1
    for (int i = 0; i < numsSize; i++) {
        result[i] = -1;
    }
    
    // If k is too large, no valid windows exist
    if (2 * k + 1 > numsSize) {
        return result;
    }
    
    // Calculate sum of first valid window
    long long windowSum = 0;
    for (int i = 0; i < 2 * k + 1; i++) {
        windowSum += nums[i];
    }
    
    // First valid position is at index k
    result[k] = windowSum / (2 * k + 1);
    
    // Slide the window
    for (int i = k + 1; i < numsSize - k; i++) {
        // Remove leftmost element, add rightmost element
        windowSum = windowSum - nums[i - k - 1] + nums[i + k];
        result[i] = windowSum / (2 * k + 1);
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    int returnSize;
    int* result = solution(nums, numsSize, k, &returnSize);
    
    // Print result
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array, each element added and removed exactly once

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables besides result array

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler