Skip to main content

Sliding Window Pattern

The Sliding Window Pattern is one of the most foundational and frequently tested algorithmic design patterns in technical interviews. Top-tier engineering companies favor these problems because naive, brute-force iterations often cost $O(N^2)$ or $O(N^3)$ in runtime performance. By applying a sliding window strategy, you can optimize your solution to execute in efficient linear time: $O(N)$ or linearithmic time: $O(N \log N)$.

What is a Sliding Window?

Imagine a window of fixed or dynamic size that glides across a contiguous sequential structure (like an array or string). Instead of entirely recalculating values for every sub-segment from scratch, the window shifts positions by performing fractional, constant-time operations: evicting the leftmost element that falls out of bounds and incorporating the newest rightmost element entering the frame.

Consider an array with a window size of $K = 3$ moving from left to right:

Array: [1, 2, 3, 4, 5, 6]

Window Position 1:  [1  2  3]  4  5  6
Window Position 2:   1 [2  3  4] 5  6
Window Position 3:   1  2 [3  4  5] 6
Window Position 4:   1  2  3 [4  5  6]

Why Use the Sliding Window Pattern?

Suppose you are tasked with finding the maximum sum of a contiguous subarray of size 3 within an array: [1, 2, 3, 4, 5, 6].

A brute-force strategy evaluates every individual subarray window comprehensively:

  • 1 + 2 + 3 = 6
  • 2 + 3 + 4 = 9
  • 3 + 4 + 5 = 12
  • 4 + 5 + 6 = 15

Notice that we iteratively sum overlapping inner values over and over again. This yields a processing complexity of $O(N \times K)$, scaling poorly to quadratic $O(N^2)$ as bounds widen. Alternatively, a sliding window preserves the state of the previous window, drops the trailing value, and includes the leading value. This reduces computation costs down to a deterministic $O(N)$ runtime.

Types of Sliding Window

Sliding window problems fall into two distinct execution strategies based on bounds characteristics:

1. Fixed-Size Window

The total length of the window frame remains entirely constant throughout the entire runtime traversal. Examples include computing the maximum sum of $K$ elements or extracting the average of all sub-arrays of length $K$.

General Code Paradigm:

int left = 0;
for (int right = 0; right < n; right++) {
    // 1. Incorporate right element into operational state
    add_element(arr[right]);

    // 2. Maintain structural size compliance
    if ((right - left + 1) > k) {
        remove_element(arr[left]);
        left++;
    }

    // 3. Process valid frame output here
}

2. Variable-Size Window

The boundaries of the window dynamically expand or contract based on an evaluation condition. Examples include searching for the longest unique substring or the smallest subarray exceeding a target total.

General Code Paradigm:

int left = 0;
for (int right = 0; right < n; right++) {
    add_element(arr[right]);

    // Shrink bounds dynamically until conditional invariants are restored
    while (condition_is_violated()) {
        remove_element(arr[left]);
        left++;
    }

    // Process output or track structural maximums
}

Core Problems Deep Dive

Problem 1: Maximum Sum Subarray of Size K (Fixed Window)

Problem Statement: Given an array [2, 1, 5, 1, 3, 2] and $K = 3$, identify the maximum possible sum across all valid configurations of size 3.

Brute Force Approach

An inner nested loop computes sums for all sequential collections starting from each array index:

for (int i = 0; i <= n - k; i++) {
    int current_sum = 0;
    for (int j = i; j < i + k; j++) {
        current_sum += arr[j];
    }
    // Track maximum sum (Time Complexity: O(N * K))
}

Sliding Window Optimization

Compute an initial base window sum, then slide the frame systematically across the array by adding the element at right and subtracting the element at right - K.

Dry Run Execution:

  • Initial Window (Indices 0 to 2): 2 + 1 + 5 = 8 → maxSum = 8
  • Slide 1 (Drop 2, Add 1): 8 - 2 + 1 = 7 → maxSum = 8
  • Slide 2 (Drop 1, Add 3): 7 - 1 + 3 = 9 → maxSum = 9
  • Slide 3 (Drop 5, Add 2): 9 - 5 + 2 = 6 → maxSum = 9

Result: 9

C Code Implementation:

#include <stdio.h>

int main() {
    int arr[] = {2, 1, 5, 1, 3, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }

    int maxSum = windowSum;

    for (int i = k; i < n; i++) {
        windowSum = windowSum - arr[i - k] + arr[i];
        if (windowSum > maxSum) {
            maxSum = windowSum;
        }
    }

    printf("Maximum Sum = %d\n", maxSum); // Output: 9
    return 0;
}

Complexity: Time: $O(N)$ | Space: $O(1)$

Problem 2: Longest Unique Substring (Variable Window)

Problem Statement: Given a string "abcabcbb", isolate the length of the longest distinct contiguous substring without repeating characters.

Note: Substring components must remain entirely continuous (e.g., "abc" is a valid substring of "abcdef", whereas "ace" is not).

Optimized Strategy

Use independent left and right boundaries alongside a frequency hash-map tracker. Expand the right boundary to ingest characters. If a frequency count exceeds 1, systematically slide the left boundary forward and decrement counts until the duplication conflict resolves.

C Code Implementation:

#include <stdio.h>
#include <string.h>

int main() {
    char str[] = "abcabcbb";
    int freq[256] = {0};
    int left = 0, maxLen = 0;
    int n = strlen(str);

    for (int right = 0; right < n; right++) {
        freq[(unsigned char)str[right]]++;

        while (freq[(unsigned char)str[right]] > 1) {
            freq[(unsigned char)str[left]]--;
            left++;
        }

        int currentLen = right - left + 1;
        if (currentLen > maxLen) {
            maxLen = currentLen;
        }
    }

    printf("Longest Length = %d\n", maxLen); // Output: 3 ("abc")
    return 0;
}

Complexity Analysis: Although it contains nested loops, both the left and right pointers traverse the sequential space at most once. This ensures a strict linear performance runtime profile of $O(N)$ with an absolute constant space layout of $O(1)$ based on the fixed ASCII spectrum table (256 slots).

Essential Interview Practice Set

1. Longest Subarray with Sum K

Problem: Given [1, 2, 1, 1, 1] and target $K = 3$, look for the maximum length of a valid matching sequence.

#include <stdio.h>

int main() {
    int arr[] = {1, 2, 1, 1, 1};
    int n = 5, k = 3;
    int left = 0, sum = 0, maxLen = 0;

    for (int right = 0; right < n; right++) {
        sum += arr[right];
        while (sum > k) {
            sum -= arr[left];
            left++;
        }
        if (sum == k) {
            int len = right - left + 1;
            if (len > maxLen) maxLen = len;
        }
    }
    printf("Longest Length = %d\n", maxLen); // Output: 3 (Subarray: [1,1,1])
    return 0;
}

2. Maximum Consecutive Ones

Problem: Identify the maximum continuous streak of 1s within a binary stream [1, 1, 0, 1, 1, 1, 0, 1].

#include <stdio.h>

int main() {
    int arr[] = {1, 1, 0, 1, 1, 1, 0, 1};
    int n = 8, current = 0, maxCount = 0;

    for (int i = 0; i < n; i++) {
        if (arr[i] == 1) {
            current++;
            if (current > maxCount) maxCount = current;
        } else {
            current = 0;
        }
    }
    printf("Max Consecutive Ones = %d\n", maxCount); // Output: 3
    return 0;
}

3. Minimum Size Subarray Sum

Problem: Given [2, 3, 1, 2, 4, 3] and a goal threshold of 7, find the minimal length where total sum $\ge \text{target}$.

#include <stdio.h>
#include <limits.h>

int main() {
    int arr[] = {2, 3, 1, 2, 4, 3};
    int n = 6, target = 7;
    int left = 0, sum = 0, minLen = INT_MAX;

    for (int right = 0; right < n; right++) {
        sum += arr[right];
        while (sum >= target) {
            int len = right - left + 1;
            if (len < minLen) minLen = len;
            sum -= arr[left];
            left++;
        }
    }
    printf("Minimum Length = %d\n", minLen == INT_MAX ? 0 : minLen); // Output: 2 ([4, 3])
    return 0;
}

4. Longest Repeating Character Replacement

Problem: Given "AABABBA" and operations limit $K = 1$, find the maximum string sequence achievable after replacing a single character.

Rule: The window configuration is valid if: $\text{windowSize} - \text{maxFrequency} \le K$.

#include <stdio.h>
#include <string.h>

int main() {
    char str[] = "AABABBA";
    int k = 1, freq[26] = {0}, left = 0, maxFreq = 0, result = 0;
    int n = strlen(str);

    for (int right = 0; right < n; right++) {
        freq[str[right] - 'A']++;
        if (freq[str[right] - 'A'] > maxFreq) maxFreq = freq[str[right] - 'A'];

        while ((right - left + 1) - maxFreq > k) {
            freq[str[left] - 'A']--;
            left++;
        }
        int len = right - left + 1;
        if (len > result) result = len;
    }
    printf("Max Length = %d\n", result); // Output: 4
    return 0;
}

5. Fruit Into Baskets

Problem: Collect continuous elements from an array [1, 2, 1, 2, 3] given a strict structural constraint of containing at most 2 distinct integers.

#include <stdio.h>

int main() {
    int arr[] = {1, 2, 1, 2, 3};
    int n = 5, freq[100] = {0}, left = 0, distinct = 0, answer = 0;

    for (int right = 0; right < n; right++) {
        if (freq[arr[right]] == 0) distinct++;
        freq[arr[right]]++;

        while (distinct > 2) {
            freq[arr[left]]--;
            if (freq[arr[left]] == 0) distinct--;
            left++;
        }
        int len = right - left + 1;
        if (len > answer) answer = len;
    }
    printf("Max Fruit Collected = %d\n", answer); // Output: 4
    return 0;
}

6. Minimum Window Substring

Problem: For input String "ADOBECODEBANC" and pattern match sequence "ABC", isolate the smallest continuous span containing all required search targets.

Strategy Note: This highly advanced task uses a tracking counter structure paired with an active frequency array to contract boundaries eagerly while verifying character requirements. Runtime is linear $O(N)$.

7. Sliding Window Maximum

Problem: Extract the maximum value for each sliding sub-block configuration of size $K$ across an array.

Strategy Note: Instead of simple parameters, this is optimized via a Monotonic Deque architecture keeping elements structured in sorted decreasing order. This avoids re-scanning values and handles updates in $O(1)$ amortized runtime.

8. Find All Anagrams / Permutations in a String

Problem: Find all matching sub-segments inside text "cbaebabacd" that match character patterns found in "abc".

#include <stdio.h>
#include <string.h>

int main() {
    char text[] = "cbaebabacd";
    char pattern[] = "abc";
    int freqP[26] = {0}, freqW[26] = {0};
    int pLen = strlen(pattern), tLen = strlen(text), count = 0;

    if (pLen > tLen) return 0;
    for (int i = 0; i < pLen; i++) {
        freqP[pattern[i] - 'a']++;
        freqW[text[i] - 'a']++;
    }

    for (int i = pLen; i <= tLen; i++) {
        int same = 1;
        for (int j = 0; j < 26; j++) {
            if (freqP[j] != freqW[j]) { same = 0; break; }
        }
        if (same) count++;

        if (i < tLen) {
            freqW[text[i] - 'a']++;
            freqW[text[i - pLen] - 'a']--;
        }
    }
    printf("Total Anagram Occurrences = %d\n", count); // Output: 2
    return 0;
}

Pattern Recognition Strategy Guide

If the Problem Mentions... Window Type Strategy
"Subarray of precise size K" / "Average of K size windows"Fixed-Size Sliding Window
"Find continuous anagram occurrences / string permutations"Fixed-Size Sliding Window
"Longest substring without repeating entities"Variable-Size Sliding Window
"Minimum frame span where cumulative value meets target"Variable-Size Sliding Window
"At most / Exactly K matching structural variations"Variable-Size Sliding Window

Pattern Blueprint Summary

Always remember the Golden Template when implementing solutions on whiteboard sessions:

// The Golden Sliding Window Template
for (int right = 0; right < total_elements; right++) {
    incorporate_element(arr[right]);

    while (window_state_is_invalid()) {
        evict_element(arr[left]);
        left++;
    }

    track_and_update_optimal_answer(right - left + 1);
}

Frequently Asked Questions (FAQs)

1. How do I differentiate between Two-Pointers and Sliding Window approaches?

While Sliding Window uses two pointers, it specifically targets contiguous subarrays or substrings where the elements enclosed between the pointers form the state. The standard Two-Pointer technique often operates from opposite ends of a sorted array to find pairs, without focusing on the elements in between.

2. Why isn't the nested while loop inside the variable window template considered $O(N^2)$?

Even though there is a loop inside a loop, the left pointer only moves forward and never backtracks. Across the entire array traversal, the left pointer can increment at most $N$ times total. This makes the amortized time complexity linear, or $O(2N)$, which simplifies to $O(N)$.

3. What should I look out for to avoid off-by-one errors in window sizing?

When computing the size of a window defined by inclusive bounds left and right, always use the formula (right - left + 1). Using simple subtraction will undercount your window size by exactly 1 element.

Labels:

Comments

Post a Comment

Popular posts from this blog

How I Got Selected in MNC

Virtusa Sometimes success does not come from having the best coding skills or the perfect roadmap. Sometimes it comes from simply refusing to quit. This is the honest story of how I transitioned from a confused, rejected fresher to getting selected as an Associate Engineer at Virtusa. The Beginning: Confused About My Future After completing my graduation, I stared blankly at my career options. Like many freshers, I lacked a clear direction. Should I join a Java course? Should I prepare on my own? Should I just wait for campus placement opportunities? One day, I called my friend Chetan. He suggested I join Naresh i Technologies and start learning Java seriously. Still unsure of my path, I told him I needed time to think about it. A couple of days later, my phone buzzed with a WhatsApp message offering a job opportunity. They asked me to come for the next round of the recruitment process. Excitement completely took over. I packed my bags, traveled to th...
Post a Comment
Read more

Spring Boot Introduction

Spring Boot Introduction: Architecture, Dependencies, and Embedded Servers Modern enterprise applications demand rapid development, frictionless deployment, and absolute minimal configuration. Before Spring Boot arrived, developers utilizing the Spring Framework wasted immense amounts of time configuring XML files, managing clashing dependencies, setting up clunky application servers, and stitching various Spring modules together manually. To eliminate these bottlenecks, Pivotal introduced Spring Boot . Built entirely on top of the traditional Spring Framework, Spring Boot is an "opinionated" framework. It aggressively simplifies application development by injecting auto-configuration, packaging starter dependencies, and embedding web servers directly into your application. This allows backend developers to focus entirely on building business logic rather than wrestling with infrastructure setup. What is Spring Boot? Spring Boot is a powerful extens...
Post a Comment
Read more

Data Types in C

C Programming: Understanding Data Types Think of your kitchen. You store a large bag of flour in a big bin, a pinch of saffron in a tiny jar, and milk in a liquid measuring jug. You do not put liquids into paper bags, and you do not use a massive bucket for a single teaspoon of sugar. C programming works the exact same way. When you create a variable, you must tell the computer exactly what kind of "container" to build in its memory. We call these containers Data Types . They dictate what kind of data the container holds, how much space it takes up, and what operations you can perform on it. 1. Primitive Data Types C offers several built-in, "primitive" data types. Think of these as the fundamental storage containers. int (Integer): You use this to store whole numbers without decimals. Real-life example: Counting the number of people in a room or tracking a player's score in a video game. char (Character): You use this ...
Post a Comment
Read more