Home › DSA › Sliding Window

Introduction to Sliding Window Pattern

In many problems dealing with an array (or a LinkedList), we are asked to find or calculate something among all the subarrays (or sublists) of a given size. For example, take a look at this problem:

Given an array, find the average of each subarray of ‘K’ contiguous elements in it.

Let's understand this problem with an example:

Array: [1, 3, 2, 6, -1, 4, 1, 8, 2], K=5

Here, we are asked to find the average of all subarrays of '5' contiguous elements in the given array. Let's solve this:

For the first 5 numbers (subarray from index 0-4), the average is:
The average of next 5 numbers (subarray from index 1-5) is:
For the next 5 numbers (subarray from index 2-6), the average is:
...

Here is the final output containing the averages of all subarrays of size 5:

Output: [2.2, 2.8, 2.4, 3.6, 2.8]

A brute-force algorithm will calculate the sum of every 5-element subarray of the given array and divide the sum by '5' to find the average. This is what the algorithm will look like:

java

import java.util.Arrays;

class Solution {

  public double[] findAverages(int K, int[] arr) {
    double[] result = new double[arr.length - K + 1];
    for (int i = 0; i <= arr.length - K; i++) {
      // find sum of next 'K' elements
      double sum = 0;
      for (int j = i; j < i + K; j++) sum += arr[j];
      result[i] = sum / K; // calculate average
    }

    return result;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    double[] result = sol.findAverages(
      5,
      new int[] { 1, 3, 2, 6, -1, 4, 1, 8, 2 }
    );
    System.out.println(
      "Averages of subarrays of size K: " + Arrays.toString(result)
    );
  }
}

Time Complexity
- Outer loop: The outer loop runs for each possible starting index of a subarray of size K. Since the array has N elements, the outer loop runs times, which is approximately .
- Inner loop: For each iteration of the outer loop, the inner loop runs for K elements to calculate the sum of the subarray. Since the inner loop runs times for each iteration of the outer loop, the total time complexity is .
- Overall time complexity: .

Can we find a better solution? Do you see any inefficiency in the above approach?

The inefficiency is that for any two consecutive subarrays of size '5', the overlapping part (which will contain four elements) will be evaluated twice. For example, take the above-mentioned input:

As you can see, there are four overlapping elements between the subarray (indexed from 0-4) and the subarray (indexed from 1-5). Can we somehow reuse the sum we have calculated for the overlapping elements?

The efficient way to solve this problem would be to visualize each subarray as a sliding window of '5' elements. This means that we will slide the window by one element when we move on to the next subarray. To reuse the sum from the previous subarray, we will subtract the element going out of the window and add the element now being included in the sliding window. This will save us from going through the whole subarray to find the sum and, as a result, the algorithm complexity will reduce to .

Here is the algorithm for the Sliding Window approach:

java

import java.util.Arrays;

class Solution {

  public double[] findAverages(int K, int[] arr) {
    double[] result = new double[arr.length - K + 1];
    double windowSum = 0;
    int windowStart = 0;
    for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
      windowSum += arr[windowEnd]; // add the next element
      // slide the window, we don't need to slide if we've not hit the required
      // window size of 'k'
      if (windowEnd >= K - 1) {
        result[windowStart] = windowSum / K; // calculate the average
        windowSum -= arr[windowStart]; // subtract the element going out
        windowStart++; // slide the window ahead
      }
    }

    return result;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    double[] result = sol.findAverages(
      5,
      new int[] { 1, 3, 2, 6, -1, 4, 1, 8, 2 }
    );
    System.out.println(
      "Averages of subarrays of size K: " + Arrays.toString(result)
    );
  }
}

Complexity Analysis

Time Complexity

Single pass: The algorithm only requires one pass through the array to calculate the sum of subarrays of size K. The loop runs for each element of the array, so the time complexity is , where N is the number of elements in the array.
Sliding window: The sliding window approach ensures that we add a new element to the sum and subtract the outgoing element in constant time, . As a result, for each subarray of size K, we perform constant-time operations. This avoids the need to re-calculate the sum for overlapping subarrays repeatedly, making it much more efficient than the nested loop approach.

Overall time complexity: .

Space Complexity

Result array: The result array requires space to store the averages of all possible subarrays of size K, which is approximately space.
Additional variables: The algorithm uses a few extra variables, such as windowSum, windowStart, and windowEnd, which take constant space, .

Overall space complexity: .

In the following chapters, we will apply the Sliding Window approach to solve a few problems.

In some problems, the size of the sliding window is not fixed. We have to expand or shrink the window based on the problem constraints. We will see a few examples of such problems in the next chapters.

Let's jump onto our first problem and apply the Sliding Window pattern.

🤖 Don't fully get this? Learn it with Claude

Stuck on Introduction to Sliding Window Pattern? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Introduction to Sliding Window Pattern** (DSA) and want to truly understand it. Explain Introduction to Sliding Window Pattern from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Introduction to Sliding Window Pattern** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Introduction to Sliding Window Pattern** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Introduction to Sliding Window Pattern** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

Maximum Average Subarray I →