Find the average of contiguous sub-arrays of size k

You are given an array of integers and a window size k, and your task is to return the average of every contiguous subarray of size k. This problem, also known as Average of Subarrays of Size K, is a textbook introduction to the sliding window pattern, one of the most important techniques for array and string problems in coding interviews.

TL;DR

Use a sliding window of size k. Maintain a running sum and slide it across the array, adding the new element and subtracting the old one at each step. Divide by k to get each average. This runs in O(n) time and O(1) auxiliary space.

Why This Problem Matters

The sliding window technique shows up everywhere in interviews: maximum sum subarrays, longest substring without repeating characters, minimum window substring, and more. This problem is the gentlest possible introduction. Once you see how reusing computation across overlapping windows works here, harder sliding window problems become much more approachable.

Understanding the Problem

Given an integer array arr and an integer k, compute the average of every contiguous subarray of length k.

averages([1, 3, -2, 6, 4], 4) -> [2.0, 2.75]
averages([1, 3, -2, 6, 4], 1) -> [1.0, 3.0, -2.0, 6.0, 4.0]
averages([1, 3, -2, 6, 4], 5) -> [2.4]

For k = 4 and the array [1, 3, -2, 6, 4]:

• First window [1, 3, -2, 6] has sum 8, average 2.0
• Second window [3, -2, 6, 4] has sum 11, average 2.75

The result has n - k + 1 elements, since that is how many windows of size k fit in an array of length n.

Edge Cases

1. k = 1: Every element is its own average, so the output mirrors the input as floating-point values
2. k = n: There is exactly one window covering the entire array
3. Negative numbers: The sum and average can be negative, which does not affect the algorithm

Solution Approach

The brute force way is to loop through each starting position and sum k elements from scratch. That costs O(k) per window and O(n * k) overall. But notice that adjacent windows overlap in k - 1 elements. Only one element changes between consecutive windows: one leaves on the left, one enters on the right.

The sliding window insight: instead of recalculating the full sum, subtract the element leaving the window and add the element entering it.

Here is the full trace for arr = [1, 3, -2, 6, 4] with k = 4:

The window grows until it reaches size k. Once it does, we record the average, then slide by subtracting arr[left] and advancing left. Each element is added once and removed once, giving O(n) total work.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public double[] averages(int[] arr, int k) {
    double[] out = new double[arr.length - k + 1];

    double windowSum = 0D;

    int left = 0;

    for (int right = 0; right < arr.length; right++) {
      windowSum += arr[right];

      if (right - left + 1 == k) {
        out[left] = windowSum / k;

        windowSum -= arr[left++];
      }
    }

    return out;
  }
}

Let's walk through the code:

1. Allocate the result array: Size arr.length - k + 1 since that is how many windows exist
2. Expand the window: Add arr[right] to windowSum on every iteration
3. Check window size: When right - left + 1 == k, the window is full
4. Record and slide: Store the average windowSum / k, subtract arr[left], and increment left

The left pointer only advances when the window is full, so the window never exceeds size k.

Complexity Analysis

Time: O(n) where n is the array length. Each element is visited exactly twice: once when right adds it and once when left removes it. The window size k does not affect the number of operations.

Space: O(1) auxiliary. We use a constant number of variables (windowSum, left, right). The output array of size n - k + 1 is required by the problem specification.

Why Not Brute Force?

The brute force approach sums k elements for each of the n - k + 1 windows:

// Works, but O(n * k)
for (int i = 0; i <= arr.length - k; i++) {
    double sum = 0;
    for (int j = i; j < i + k; j++) {
        sum += arr[j];
    }
    out[i] = sum / k;
}

For k = 100 and n = 1000, brute force does about 90,000 additions. The sliding window does about 2,000. The larger k gets, the bigger the gap.

Common Pitfalls

1. Off-by-one in result array size: The number of windows is n - k + 1, not n - k or n. Getting this wrong causes an array index out of bounds.

2. Integer division: In languages like Java, dividing two integers truncates the result. Make sure either the sum or k is a floating-point type. Using double windowSum = 0D handles this.

3. Forgetting to slide the window: After recording an average, you must subtract arr[left] and increment left. Skipping this step means the window keeps growing and the averages are wrong.

Interview Tips

When presenting this solution:

• Start by mentioning the brute force O(n * k) approach, then explain why adjacent windows overlap
• Draw the array with brackets showing two consecutive windows and circle the shared elements
• State the sliding window optimization: "subtract one element, add one element, O(1) per slide"
• Mention that this pattern generalizes to many problems: max sum subarray of size k, minimum window substring, and others
• If asked about streaming data, note that this approach works naturally with streams since it only needs the current window

Key Takeaways

• The sliding window technique eliminates redundant computation by reusing the sum from the previous window, reducing O(n * k) to O(n).
• The window grows from the right and shrinks from the left. A sum update of O(1) replaces a full O(k) recalculation.
• The output array has exactly n - k + 1 entries. Getting this size right avoids out-of-bounds errors.
• This is the foundational pattern for fixed-size sliding window problems. Master it here, and problems like maximum sum subarray of size k become trivial variations.
• The technique extends naturally to variable-size windows (e.g., smallest subarray with sum greater than a target), where the left pointer advances conditionally rather than on every full window.

Practice and Related Problems

Once you are comfortable with this fixed-size sliding window, try these progressions:

• Maximum sum subarray of size k (same pattern, track max instead of storing all)
• Longest substring without repeating characters (variable-size window)
• Minimum window substring (variable-size window with character frequency map)

This problem and hundreds of others are available on Firecode, where consistent daily practice helps you build the pattern recognition that top tech companies look for. Whether you are warming up for phone screens or preparing for on-site interviews, starting with fundamentals like the sliding window sets you up well.

Solutions in Other Languages

Python

class Solution:
    def averages(self, arr, k):
        out = []

        window_sum = 0.0

        left = 0

        for right in range(len(arr)):
            window_sum += arr[right]

            if right - left + 1 == k:
                out.append(window_sum / k)

                window_sum -= arr[left]
                left += 1

        return out

JavaScript

class Solution {
  averages(arr, k) {
    const out = [];

    let windowSum = 0.0;

    let left = 0;

    for (let right = 0; right < arr.length; right++) {
      windowSum += arr[right];

      if (right - left + 1 === k) {
        out.push(windowSum / k);

        windowSum -= arr[left++];
      }
    }

    return out;
  }
}

TypeScript

class Solution {
  averages(arr: number[], k: number): number[] {
    const out: number[] = [];

    let windowSum = 0.0;

    let left = 0;

    for (let right = 0; right < arr.length; right++) {
      windowSum += arr[right];

      if (right - left + 1 === k) {
        out.push(windowSum / k);

        windowSum -= arr[left++];
      }
    }

    return out;
  }
}

C++

#include <iostream>

class Solution {
public:
  std::vector<double> averages(std::vector<int> arr, int k) {
    std::vector<double> out(arr.size() - k + 1);

    double windowSum = 0.0;

    int left = 0;

    for (int right = 0; right < arr.size(); right++) {
      windowSum += arr[right];

      if (right - left + 1 == k) {
        out[left] = windowSum / k;

        windowSum -= arr[left++];
      }
    }

    return out;
  }
};

Go

package solution

func (s *Solution) Averages(arr []int, k int) []float64 {
	out := make([]float64, len(arr) - k + 1)

	windowSum := 0.0

	left := 0

	for right, num := range arr {
		windowSum += float64(num)

		if right - left + 1 == k {
			out[left] = windowSum / float64(k)

			windowSum -= float64(arr[left])
			left++
		}
	}

	return out
}

Scala

class Solution {
  def averages(arr: Array[Int], k: Int): Array[Double] = {
    val out = new Array[Double](arr.length - k + 1)

    var windowSum = 0D

    var left = 0

    for (right <- arr.indices) {
      windowSum += arr(right)

      if (right - left + 1 == k) {
        out(left) = windowSum / k

        windowSum -= arr(left)
        left += 1
      }
    }

    out
  }
}

Kotlin

class Solution {
  fun averages(arr: IntArray, k: Int): DoubleArray {
    val out = DoubleArray(arr.size - k + 1)

    var windowSum = 0.0

    var left = 0

    for (right in arr.indices) {
      windowSum += arr[right]

      if (right - left + 1 == k) {
        out[left] = windowSum / k

        windowSum -= arr[left++]
      }
    }

    return out
  }
}

Swift

class Solution {
    func averages(_ arr: [Int], _ k: Int) -> [Double] {
        var out = [Double]()

        var windowSum = 0.0

        var left = 0

        for right in 0..<arr.count {
            windowSum += Double(arr[right])

            if right - left + 1 == k {
                out.append(windowSum / Double(k))

                windowSum -= Double(arr[left])
                left += 1
            }
        }

        return out
    }
}

Rust

pub struct Solution;

impl Solution {
    pub fn averages(&self, arr: Vec<i32>, k: i32) -> Vec<f64> {
        let mut out = vec![0.0_f64; arr.len() - k as usize + 1];

        let mut window_sum = 0.0_f64;

        let mut left = 0;

        for right in 0..arr.len() {
            window_sum += arr[right] as f64;

            if right - left + 1 == k as usize {
                out[left] = window_sum / k as f64;

                window_sum -= arr[left] as f64;
                left += 1;
            }
        }

        out
    }
}

C#

public class Solution {
    public double[] Averages(int[] arr, int k) {
        var result = new double[arr.Length - k + 1];

        double windowSum = 0;

        int left = 0;

        for (int right = 0; right < arr.Length; right++) {
            windowSum += arr[right];

            if (right - left + 1 == k) {
                result[left] = windowSum / k;

                windowSum -= arr[left++];
            }
        }

        return result;
    }
}

Dart

class Solution {
  List<double> averages(List<int> arr, int k) {
    List<double> out = List<double>.filled(arr.length - k + 1, 0.0);

    double windowSum = 0.0;

    int left = 0;

    for (int right = 0; right < arr.length; right++) {
      windowSum += arr[right];

      if (right - left + 1 == k) {
        out[left] = windowSum / k;

        windowSum -= arr[left++];
      }
    }

    return out;
  }
}

PHP

class Solution {
    public function averages(array $arr, int $k): array {
        $out = [];

        $windowSum = 0.0;

        $left = 0;

        for ($right = 0; $right < count($arr); $right++) {
            $windowSum += $arr[$right];

            if ($right - $left + 1 == $k) {
                $out[] = $windowSum / $k;

                $windowSum -= $arr[$left++];
            }
        }

        return $out;
    }
}

Ruby

class Solution
  def averages(arr, k)
    result = []

    window_sum = 0

    left = 0

    arr.each_with_index do |num, right|
      window_sum += num

      if right - left + 1 == k
        result << window_sum.to_f / k

        window_sum -= arr[left]
        left += 1
      end
    end

    result
  end
end