2090.k-radius-subarray-averages.md

2090. K Radius Subarray Averages

Sliding Window

We can iterate to maintain a window of size 2k + 1 to calculate the sum of the subarray. And we update result[x] at index i.

k = 4
0 1 2 3 4 5 6 7 8
|---k---i---k---|
|---------------|
        x       i
size = 2k + 1

// Fixed size window
fun getAverages(nums: IntArray, k: Int): IntArray {
    val n = nums.size
    var left = 0
    var right = 0
    var sum = 0L
    val result = IntArray(n) { -1 }
    val windowSize = 2 * k + 1

    for (i in nums.indices) {
        sum += nums[i].toLong()
        if (i >= windowSize) {
            sum -= nums[i - windowSize].toLong()
        }
        if (i >= windowSize - 1) {
            result[i - k] = (sum / windowSize.toLong()).toInt()
        }
    }
    return result
}

// General sliding window
fun getAverages(nums: IntArray, k: Int): IntArray {
    val n = nums.size
    var left = 0
    var right = 0
    var sum = 0L
    val result = IntArray(n) { -1 }
    val windowSize = 2 * k + 1
    while (right < n) {
        sum += nums[right].toLong()
        while (right - left + 1 > windowSize) {
            sum -= nums[left].toLong()
            left++
        }
        if (right - left + 1 == windowSize && right >= k) {
            result[right - k] = (sum / windowSize.toLong()).toInt()
        }
        right++
    }   
    return result
}

Prefix Sum

TODO