LeetCode 2090 - K Radius Subarray Averages

The problem asks us to compute a special average for every index in the array. For each position i, we want to look at a subarray centered at i with radius k. That means we include all elements from index i - k through i + k, inclusive.

leetcodemediumarraysliding-window

LeetCode Problem 2090

Difficulty: 🟡 Medium
Topics: Array, Sliding Window

Solution

Problem Understanding

The problem asks us to compute a special average for every index in the array. For each position i, we want to look at a subarray centered at i with radius k. That means we include all elements from index i - k through i + k, inclusive.

The size of this window is always:

$$2k + 1$$

For example, if k = 2, then the average centered at index i uses:

  • two elements to the left,
  • the current element,
  • two elements to the right.

So the total number of elements is 5.

If an index does not have enough elements on either side, then the answer for that index must be -1.

The output array must have the same length as the input array. Every position contains either:

  • the integer average of the corresponding radius window, or
  • -1 if the window cannot exist.

The problem specifies integer division, which means any fractional part is discarded. For example:

$$17 / 5 = 3$$

not 3.4.

The constraints are important:

  • n can be as large as 10^5
  • nums[i] can also be as large as 10^5

Because the array can be very large, any algorithm that repeatedly scans large subarrays for every index will likely be too slow.

There are several important edge cases to consider:

  • k = 0, every element becomes its own average.
  • 2k + 1 > n, no valid window exists anywhere.
  • Arrays with only one element.
  • Large values in the array, which means the running sum can become large. We must avoid overflow in languages with fixed integer sizes.
  • Windows overlapping heavily, which suggests that recomputing sums from scratch would waste work.

Approaches

Brute Force Approach

The most direct solution is to process each index independently.

For every index i:

  1. Check whether there are at least k elements before and after it.
  2. If not, store -1.
  3. Otherwise, iterate from i - k to i + k, compute the sum manually, and divide by 2k + 1.

This approach is correct because it directly follows the definition of the problem.

However, it is inefficient. Each valid center requires scanning a window of size 2k + 1. In the worst case, this happens for nearly every index.

If:

  • n = 100000
  • k = 50000

then we repeatedly scan extremely large overlapping windows.

The total complexity becomes:

$$O(n \times (2k+1))$$

which can degrade to O(n^2).

This is too slow for the given constraints.

Optimal Sliding Window Approach

The key observation is that consecutive windows overlap heavily.

Suppose we already know the sum of the window centered at index i.

When moving to index i + 1:

  • one element leaves the window,
  • one new element enters the window.

Instead of recomputing the entire sum, we can update it incrementally.

This is exactly what the sliding window technique is designed for.

We maintain:

  • the current window sum,
  • the left boundary,
  • the right boundary.

As the window moves one step to the right:

$$\text{newSum} = \text{oldSum} - \text{leftElement} + \text{newRightElement}$$

This reduces the total complexity to linear time.

Comparison of Approaches

Approach Time Complexity Space Complexity Notes
Brute Force O(n × (2k + 1)) O(1) excluding output Recomputes every window sum independently
Optimal O(n) O(1) excluding output Uses a sliding window to reuse previous sums

Algorithm Walkthrough

Optimal Sliding Window Algorithm

  1. Create a result array filled with -1.

Every index is initially assumed invalid. We only overwrite positions where a complete radius window exists. 2. Compute the required window size.

The radius window contains:

$$2k + 1$$

elements. 3. Handle the impossible case early.

If the window size is larger than the array length, then no valid center exists. Return the result array immediately. 4. Initialize the first window sum.

Compute the sum of the first windowSize elements.

This corresponds to the window centered at index k. 5. Store the first average.

The first valid center is index k.

Compute:

$$\text{sum} // \text{windowSize}$$

and place it into result[k]. 6. Slide the window across the array.

For every next position:

  • remove the leftmost element,
  • add the new rightmost element,
  • compute the new average.

The window moves exactly one step at a time. 7. Continue until the window reaches the end.

Every valid center receives its computed average. 8. Return the result array.

Why it works

The algorithm maintains the invariant that windowSum always equals the sum of the current contiguous window of size 2k + 1.

When the window moves one step right:

  • exactly one element exits,
  • exactly one element enters.

Therefore, updating the sum incrementally preserves correctness while avoiding repeated work. Every valid center is processed exactly once, so all averages are computed correctly.

Python Solution

from typing import List

class Solution:
    def getAverages(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        window_size = 2 * k + 1

        result = [-1] * n

        if window_size > n:
            return result

        window_sum = sum(nums[:window_size])

        center = k
        result[center] = window_sum // window_size

        left = 0
        right = window_size

        while right < n:
            window_sum -= nums[left]
            window_sum += nums[right]

            left += 1
            center += 1
            right += 1

            result[center] = window_sum // window_size

        return result

The implementation begins by determining the array length and the required window size. The result array is initialized with -1 because many positions may never receive valid averages.

The early return handles the case where the required radius window is larger than the entire array. In that situation, no valid center exists.

The first complete window is computed using Python's built in sum() function. This initial window corresponds to the center at index k.

The algorithm then maintains three important variables:

  • left, the outgoing index,
  • right, the incoming index,
  • window_sum, the sum of the current window.

Each iteration removes one value from the left side and adds one value from the right side. This keeps the running sum accurate in constant time.

Because every element enters and leaves the window at most once, the algorithm runs efficiently in linear time.

Go Solution

func getAverages(nums []int, k int) []int {
	n := len(nums)
	windowSize := 2*k + 1

	result := make([]int, n)

	for i := 0; i < n; i++ {
		result[i] = -1
	}

	if windowSize > n {
		return result
	}

	var windowSum int64 = 0

	for i := 0; i < windowSize; i++ {
		windowSum += int64(nums[i])
	}

	center := k
	result[center] = int(windowSum / int64(windowSize))

	left := 0
	right := windowSize

	for right < n {
		windowSum -= int64(nums[left])
		windowSum += int64(nums[right])

		left++
		center++
		right++

		result[center] = int(windowSum / int64(windowSize))
	}

	return result
}

The Go implementation closely follows the Python version, but there are a few language specific considerations.

The most important difference is the use of int64 for the running sum. Since the array may contain up to 10^5 elements, each as large as 10^5, the sum can exceed the safe range of a 32 bit integer.

The result slice is initialized manually with -1 because Go slices default to 0.

Go also requires explicit integer conversions when dividing int64 values and storing results back into an int.

Worked Examples

Example 1

Input:

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

Window size:

2 * 3 + 1 = 7

Initial window:

[7,4,3,9,1,8,5]

Sum:

37

Average:

37 // 7 = 5

Result so far:

[-1,-1,-1,5,-1,-1,-1,-1,-1]

Now slide the window.

Step Window Sum Center Average
Initial [7,4,3,9,1,8,5] 37 3 5
Slide 1 [4,3,9,1,8,5,2] 32 4 4
Slide 2 [3,9,1,8,5,2,6] 34 5 4

Final result:

[-1,-1,-1,5,4,4,-1,-1,-1]

Example 2

Input:

nums = [100000]
k = 0

Window size:

1

The single element forms a valid window by itself.

Window Sum Average
[100000] 100000 100000

Result:

[100000]

Example 3

Input:

nums = [8]
k = 100000

Window size:

200001

Since the window is larger than the array length, no valid center exists.

Result:

[-1]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every element enters and leaves the sliding window at most once
Space O(1) excluding output Only a few variables are used regardless of input size

The algorithm performs a constant amount of work per element. After the initial window computation, every subsequent step only updates the running sum by subtracting one value and adding another.

No auxiliary data structures proportional to the input size are required.

Test Cases

from typing import List

class Solution:
    def getAverages(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        window_size = 2 * k + 1

        result = [-1] * n

        if window_size > n:
            return result

        window_sum = sum(nums[:window_size])

        center = k
        result[center] = window_sum // window_size

        left = 0
        right = window_size

        while right < n:
            window_sum -= nums[left]
            window_sum += nums[right]

            left += 1
            center += 1
            right += 1

            result[center] = window_sum // window_size

        return result

sol = Solution()

assert sol.getAverages([7,4,3,9,1,8,5,2,6], 3) == [-1,-1,-1,5,4,4,-1,-1,-1]  # standard example

assert sol.getAverages([100000], 0) == [100000]  # single element with k = 0

assert sol.getAverages([8], 100000) == [-1]  # impossible window size

assert sol.getAverages([1,2,3,4,5], 0) == [1,2,3,4,5]  # every element alone

assert sol.getAverages([1,2,3,4,5], 2) == [-1,-1,3,-1,-1]  # exactly one valid center

assert sol.getAverages([1,1,1,1,1,1,1], 1) == [-1,1,1,1,1,1,-1]  # repeated values

assert sol.getAverages([10,20], 1) == [-1,-1]  # window larger than available centers

assert sol.getAverages([5], 0) == [5]  # smallest valid input

assert sol.getAverages([1,100000,1,100000,1], 1) == [-1,33334,66667,33334,-1]  # large values and truncation

assert sol.getAverages([0,0,0,0,0], 2) == [-1,-1,0,-1,-1]  # all zeros

Test Summary

Test Why
[7,4,3,9,1,8,5,2,6], k=3 Validates the primary sliding window behavior
[100000], k=0 Tests radius zero behavior
[8], k=100000 Tests impossible window condition
[1,2,3,4,5], k=0 Ensures every element becomes its own average
[1,2,3,4,5], k=2 Tests exactly one valid center
Repeated ones with k=1 Ensures stable sliding window updates
[10,20], k=1 Tests insufficient array length
[5], k=0 Smallest possible valid input
Large alternating values Validates integer division and large sums
All zeros Tests neutral values

Edge Cases

One important edge case occurs when k = 0. In this situation, every element forms a valid window of size 1. A buggy implementation might still attempt unnecessary sliding window logic or incorrectly mark elements as invalid. This implementation handles the case naturally because the computed window size becomes 1, and every index receives its own value as the average.

Another critical edge case happens when the required window size exceeds the array length. For example, if the array has length 5 and k = 10, then no index can possibly have enough neighbors on both sides. Without an early return, some implementations may attempt invalid indexing operations. This solution explicitly checks:

if window_size > n:
    return result

which safely handles the scenario.

Large numeric values are another possible source of bugs, especially in languages like Go or Java. Since each value can be up to 100000, the total window sum may become very large. The Go implementation uses int64 for the running sum to avoid integer overflow during accumulation.

A final subtle case involves integer division. The problem requires truncation toward zero. Some programmers mistakenly use floating point division and rounding. This implementation always uses integer division directly, ensuring the result matches the specification exactly.