Opening your learning path
Progress is saved as you study.
Opening your learning path
Progress is saved as you study.
The Fixed Size (Subarray Calculation) pattern applies when you need the Fixed Size (Subarray Calculation) technique within the Sliding Window pattern. Its time complexity is O(n) and space complexity O(1). It is used in 5 problems on Thita, including Calculate Compressed Mean, Find the Power of K-Size Subarrays I and Find X-Sum of All K-Long Subarrays I. Common variations are Character Frequency Matching and Variable Size (Condition-Based).
Learn fixed-size sliding window for subarray calculations like maximum average, moving average, and k-size subarray problems.
Fixed Size (Subarray Calculation) is one of the 4 subpatterns of the Sliding Window pattern, which covers fixed-size, variable-size, and character frequency matching window techniques. The whole pattern is about 2.5 hours of study. This subpattern is a core technique: expect it to come up directly in interviews.
Master the sliding window technique for subarray and substring problems. Learn fixed size windows, variable size windows, and monotonic queue optimizations. Problems in this subpattern are usually searched for as fixed window, subarray calculation, maximum average, moving average, k-size subarray, leetcode 643.
Read the theory for Fixed Size (Subarray Calculation), then work the problems attached to it in the browser editor. Your solution runs against the problem's test cases, and the AI coach offers a hint about the technique you are missing rather than a finished solution. Progress is tracked per subpattern, so the Sliding Window tracker shows this one as covered once you have solved its problems.
Fixed Size (Subarray Calculation) is one lesson in a 16-pattern DSA course. If you are preparing end to end, work the interview-critical patterns first and use the pattern sheet as the checklist; if you are here for one technique, the Sliding Window guide is the shortest path back to the rest of it.
5 problems, easiest first.
The Fixed Size Sliding Window pattern allows you to process a contiguous subset of elements within an array or string where the length of the subset remains constant. Instead of iterating through the entire data structure for every possible starting position, you maintain a window of size that moves one step forward at a time. This approach enables you to track the state of the current subset efficiently as you traverse the data.
You should use this pattern when you need to compute a value—such as a sum, average, or count—for every possible contiguous segment of a specific length. By simply removing the element leaving the window and adding the new element entering it, you avoid recalculating the overlapping parts of the data. This significantly reduces redundant work and optimizes performance.
Common use cases include:
By eliminating nested loops, this pattern typically reduces the time complexity from to linear . It is also space-efficient, generally requiring only auxiliary space to store the current window's running calculation.
Let’s break down the key ideas behind the Fixed Size Sliding Window pattern:
A fixed-size window keeps a running sum: subtract the element that leaves, add the element that enters. With k = 3 the four window sums are 10, 15, 23 and 31.
k that moves from the start to the end of the array.Suppose you have an array: [2, 3, 5, 7, 11, 13] and window size k = 3.
[2, 3, 5][3, 5, 7][5, 7, 11][7, 11, 13]At each step, you process only the current window.
k elements → O(n*k) time.Analogy: Imagine reading a book page by page (sliding window) versus re-reading the whole book for each new page (naive).
Let’s build a mental model for solving fixed-size sliding window problems:
Identify the window size (k):
k consecutive elements?"Initialize the window:
Slide the window:
Store or output results:
k?k: What should your code do? Return an empty result or handle as invalid input.Suppose you want the sum of every 3-day period in [1, 2, 3, 4, 5]:
start, end) or just a loop index.Let’s look at a well-commented C++ example based on the "Maximum Average Subarray I" problem:
1#include <vector>
2#include <iostream>
3#include <limits>
4using namespace std;
5
6// Function to find the maximum average of any subarray of length k
7double findMaxAverage(vector<int>& nums, int k) {
8 int n = nums.size();
9 if (n < k) return 0.0; // Edge case: not enough elements
10
11 // Calculate the sum of the first window of size k
12 int windowSum = 0;
13 for (int i = 0; i < k; ++i) {
14 windowSum += nums[i];
15 }
16 int maxSum = windowSum; // Initialize maxSum with the first window's sum
17
18 // Slide the window across the array
19 for (int i = k; i < n; ++i) {
20 // Subtract the element leaving the window and add the new element
21 windowSum = windowSum - nums[i - k] + nums[i];
22 // Update maxSum if we found a larger sum
23 if (windowSum > maxSum) {
24 maxSum = windowSum;
25 }
26 }
27
28 // The maximum average is maxSum divided by window size k
29 return static_cast<double>(maxSum) / k;
30}
31
32int main() {
33 vector<int> nums = {1, 12, -5, -6, 50, 3};
34 int k = 4;
35 double result = findMaxAverage(nums, k);
36 cout << "Maximum average of any subarray of length " << k << " is: " << result << endl;
37 // Output: Maximum average of any subarray of length 4 is: 12.75
38 return 0;
39}Explanation:
k elements.k.Why this works:
We only ever process each element once, and we never recalculate sums for overlapping parts—just update as the window slides.
Let’s think about this step by step:
Problem:
Given an array nums and an integer k, find the contiguous subarray of length k with the maximum average.
Intuition:
k consecutive numbers and find the one with the highest average.Step-by-Step Solution:
k numbers. This is our starting point.k to get the average.Connecting to the Pattern:
Edge Cases:
k, we return 0 or handle as invalid.Takeaway:
Sliding window transforms a potentially slow O(n*k) solution into a fast O(n) one by reusing previous calculations.
How to recognize this pattern:
Common "aha!" moments:
Debugging tips:
Memory tricks:
Companies that love this pattern:
Spotify, Indeed, Amazon, Google, Apple, and more regularly ask sliding window questions, so mastering this will give you a real edge!
Key Concepts:
Hash Table, Data Stream, Queue, Heap (Priority Queue), Design, Array, Database, Sliding Window
Keep practicing, and soon this pattern will feel as natural as reading a sentence word by word!