We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

K Radius Subarray Averages

Number: 2211

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Adobe, Duolingo

Problem Description

Given a 0-indexed integer array nums and an integer k, compute the k-radius average for each index i. The k-radius average is the integer division average of all elements in the subarray spanning indices i - k to i + k (inclusive). If there are fewer than k elements before or after i, the value is set to -1.

Key Insights

  • Use a sliding window of size (2k + 1) to efficiently compute subarray sums.
  • Only update the window sum by subtracting the element that falls out and adding the new element that enters.
  • For positions where a full window cannot be formed (i.e. indices < k or >= n - k), mark the output as -1.
  • Handle special case k = 0 by returning the original array.

Space and Time Complexity

Time Complexity: O(n) – Each element is processed at most once during the window slide. Space Complexity: O(n) – Output array storing averages for each element.

Solution

We first create a result array initialized with -1. If k equals 0, we simply return the original array as each average is the element itself. For k > 0, we calculate the initial window sum for the first (2k + 1) elements. Starting at index k, we assign the integer division of this sum to the corresponding average. Then we slide the window one position at a time by subtracting the element that slides out from the left and adding the new element from the right. This approach ensures that we maintain the running sum in O(1) per step and compute all required averages efficiently.

Code Solutions

# Python solution
def getAverages(nums, k):
    n = len(nums)
    avgs = [-1] * n  # initialize result with -1
    if k == 0:
        return nums  # each avg is the element itself
    
    window_size = 2 * k + 1
    if n < window_size:
        return avgs  # not enough elements for one full window
    
    # Compute the sum of the first window
    window_sum = sum(nums[:window_size])
    avgs[k] = window_sum // window_size
    
    # Slide the window from index k+1 to n-k-1
    for i in range(k + 1, n - k):
        window_sum = window_sum - nums[i - k - 1] + nums[i + k]
        avgs[i] = window_sum // window_size
    
    return avgs

# Example usage:
print(getAverages([7,4,3,9,1,8,5,2,6], 3))
← Back to All Questions