Katkat
Back

Compute Sliding Window Averages

MetaSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to implement a sliding window algorithm to compute the average of contiguous subarrays, emphasizing optimization of time complexity.

Problem Statement

Given an array of integers nums and an integer k, calculate the average of every contiguous subarray of size k.

Return an array containing these averages. For an input array nums of length n, the result should contain n - k + 1 elements.

Function Signature

def find_averages(nums: List[int], k: int) -> List[float]:

Constraints

  • 1 <= k <= len(nums) <= 10^5
  • -10^4 <= nums[i] <= 10^4

Examples

Example 1: Input: nums = [1, 3, 2, 6, -1, 4, 1, 8, 2], k = 5 Output: [2.2, 2.8, 2.4, 3.6, 2.8] Explanation:

  • (1+3+2+6-1)/5 = 2.2
  • (3+2+6-1+4)/5 = 2.8
  • (2+6-1+4+1)/5 = 2.4
  • (6-1+4+1+8)/5 = 3.6
  • (-1+4+1+8+2)/5 = 2.8

Edge Cases

  • k = 1: The output should be the same as the input array (as floats).
  • k = len(nums): The output should contain exactly one element, the average of all numbers.

Goal

Aim for a solution with O(n) time complexity and O(1) extra space (excluding the output array).

Hints

Hint 1

A brute-force approach involves recalculating the sum for each window, which leads to redundant additions; consider how the window's sum changes when moving one position to the right.

Hint 2

When shifting the window, subtract the element that leaves the window (left side) and add the new element entering the window (right side) to the previous sum.

Hint 3

Maintain a running sum variable to keep track of the current window sum, then divide by k at each step to get the average.

Follow-up questions

  • How would you modify your solution to find the maximum average of any contiguous subarray of size k?
  • If the array elements were very large, how would you prevent potential overflow errors when calculating the sum?
  • How would you handle a scenario where k is larger than the size of the input array?