K-Radius Moving Average

XXX. K-Radius Moving Average

Array

Sliding Window

Problem Statement:

You are given a 0-indexed array nums of size n and an integer k. For each index i where k ≤ i < n-k, calculate the average of elements in range [i-k, i+k] inclusive. Return an array of all averages, setting values to -1 for indices that don't have k elements on both sides.

• The range for each index i must include k elements on both left and right
• Window size is 2k + 1 elements
• Return -1 for positions that don't have enough elements on either side

Algorithm:

1. **Initial Setup**:
   • Create result array filled with -1
   • Handle edge cases: k=0 and window size > array length
   • Calculate window size as 2k + 1
2. **First Window**:
   • Calculate sum of first complete window
   • Store average at center position (k)
3. **Sliding Window**:
   • Remove leftmost element of previous window
   • Add rightmost element of new window
   • Calculate and store new average

Complexity:

Time Complexity: O(n), where n is the length of input array
Space Complexity: O(1) excluding output array

Implementation:

Java Solution:

public int[] getAverages(int[] nums, int k) {
    if (k == 0) return nums;                        // Single element case
    
    int windowSize = 2 * k + 1;
    int n = nums.length;
    int[] averages = new int[n];
    Arrays.fill(averages, -1);                      // Fill with -1 as default
    
    if (windowSize > n) return averages;            // Window larger than array
    
    long windowSum = 0;                             // Use long to prevent overflow
    for (int i = 0; i < windowSize; ++i)           // Calculate first window sum
        windowSum += nums[i];
    
    averages[k] = (int)(windowSum / windowSize);    // Store first window's average
    
    for (int i = windowSize; i < n; ++i) {
        windowSum = windowSum - nums[i - windowSize] + nums[i];  // Slide window
        averages[i - k] = (int)(windowSum / windowSize);        // Store average
    }
    
    return averages;
}
                

Python Solution:

def getAverages(self, nums: List[int], k: int) -> List[int]:
    if k == 0: return nums                          # Single element case
    
    n = len(nums)
    window_size = 2 * k + 1
    averages = [-1] * n                            # Initialize with -1
    
    if window_size > n: return averages            # Window larger than array
    
    window_sum = sum(nums[:window_size])           # Calculate first window sum
    averages[k] = window_sum // window_size        # Store first window's average
    
    for i in range(window_size, n):
        window_sum = window_sum - nums[i - window_size] + nums[i]  # Slide window
        averages[i - k] = window_sum // window_size               # Store average
    
    return averages
                

C++ Solution:

vector getAverages(vector& nums, int k) {
    if (k == 0) return nums;                       // Single element case
    
    int n = nums.size();
    int windowSize = 2 * k + 1;
    vector averages(n, -1);                   // Initialize with -1
    
    if (windowSize > n) return averages;           // Window larger than array
    
    long long windowSum = 0;                       // Use long long to prevent overflow
    for (int i = 0; i < windowSize; ++i)          // Calculate first window sum
        windowSum += nums[i];
    
    averages[k] = windowSum / windowSize;          // Store first window's average
    
    for (int i = windowSize; i < n; ++i) {
        windowSum = windowSum - nums[i - windowSize] + nums[i];  // Slide window
        averages[i - k] = windowSum / windowSize;               // Store average
    }
    
    return averages;
}
                

Explanation:

• **Edge Cases**:
  • k = 0: Return original array
  • Window size > array length: Return all -1s
• **Window Sum**:
  • Use long/long long to prevent integer overflow
  • Maintain running sum while sliding window
• **Sliding Process**:
  • Remove leftmost element (i - windowSize)
  • Add rightmost element (i)
  • Calculate average for center position (i - k)