Sliding Window Patterns in DSA: Complete Guide with Examples

Sliding window is a fundamental technique in Data Structures and Algorithms (DSA) for solving array and string problems efficiently. Recognizing the right sliding window pattern can transform a brute-force O(n²) solution into an elegant O(n) implementation. This guide covers all common sliding window patterns, their use cases and real interview examples.

What is Sliding Window?

A sliding window is a subarray or substring that moves through the main array/string. Instead of repeatedly recalculating values for overlapping subarrays, we “slide” the window and update results incrementally.

Benefits of Sliding Window:

• Reduces time complexity from O(n²) → O(n)

• Efficiently solves subarray/subsequence problems

• Handles both fixed and dynamic constraints

Why Use Sliding Window?

Problems that involve:

• Maximum, minimum, or sum of subarrays/substrings

• Longest or shortest valid substring/subarray

• Counting subarrays/substrings satisfying a property

• Optimization problems with contiguous elements

Sliding Window Patterns

1. Fixed-Size Window

A fixed-size sliding window is when the window length k is constant. As the window moves across the array or string, we update the result by adding the new element entering the window and removing the element that slides out.

When to Use:

Use this approach when the problem explicitly deals with subarrays or substrings of length k. This is common in problems involving sums, averages, counts or character checks within a fixed range.

Interview Questions:

• Find the maximum sum of any subarray of size k.

• Find the minimum average of a subarray of size k.

• Find if any substring of length k is a permutation of another string (anagram check).

• Find the maximum number of vowels in a substring of size k.

• Compute the maximum or minimum element in every subarray of size k.

• Count distinct elements in every subarray of size k.

• Longest subarray with sum less than or equal to a given target, if constrained to fixed size.

• Detect if a fixed-length substring contains only unique characters.

• Check if a substring of size k meets specific conditions (e.g., contains all digits 0–9).

Example : Maximum Sum Subarray of Size K

// ---------------------- Java --------------------------
int maxSumSubarray(int[] arr, int k) {
    int sum = 0, maxSum = 0;
    for (int i = 0; i < k; i++) sum += arr[i]; // first window
    maxSum = sum;
    for (int i = k; i < arr.length; i++) {
        sum += arr[i] - arr[i - k]; // slide the window
        maxSum = Math.max(maxSum, sum);
    }
    return maxSum;
}

2. Variable-Size Window

In a variable-size sliding window, the window size is not fixed. The window keeps expanding until a condition is violated and then it shrinks from the left until the condition is satisfied again. This dynamic resizing helps efficiently solve problems involving longest, shortest or constrained subarrays/substrings.

When to Use:

Use this approach when the problem requires finding:

• The longest or shortest substring/subarray under a constraint.
• A minimum or maximum length window that satisfies a given condition.
• A sliding range where constraints (like distinct characters, limited replacements, or sum bounds) are applied.

Interview Questions:

• Longest substring without repeating characters.

• Longest substring with at most k distinct characters.

• Smallest subarray with sum ≥ target.

• Longest substring with at most k character replacements.

• Minimum window substring containing all characters of another string.

• Longest subarray with sum ≤ target.

• Longest substring with equal number of 0s and 1s.

• Smallest substring containing all vowels at least once.

• Longest substring where frequency of each character ≤ k.

Example : Longest Substring Without Repeating Characters

// ---------------------- Java --------------------------
int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int left = 0, maxLen = 0;
    for (int right = 0; right < s.length(); right++) {
        while (set.contains(s.charAt(right))) {
            set.remove(s.charAt(left++));
        }
        set.add(s.charAt(right));
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

3. Minimum / Maximum Window (Special Case of Variable-Size Window)

This is a specialized form of the variable-size sliding window where the primary objective is to find either the smallest (minimum) window that satisfies a condition or the largest (maximum) window that remains valid under certain constraints. Instead of just growing and shrinking arbitrarily, the algorithm carefully adjusts the window to minimize or maximize its length while maintaining the required property.

When to Use:

Apply this pattern when the problem explicitly requires:

• The minimum window substring that meets certain requirements.

• The smallest subarray satisfying a sum or condition.

• The longest substring or subarray allowed under constraints.

Interview Questions:

• Minimum window substring containing all characters of another string.

• Smallest subarray with sum ≥ target.

• Longest substring with at most k distinct characters.

• Longest substring where at most k characters can be replaced.

• Smallest substring containing all vowels at least once.

• Longest valid substring of balanced parentheses.

• Minimum window that contains all unique characters of a string.

Example : Minimum window substring containing all characters of another string.

Given two strings s (the source) and t (the target), return the smallest substring of s that contains all characters of t (including duplicates).

// ---------------------- Java --------------------------
public String MinimumWindowSubstring(String s, String t) {
    if (s == null || s.length() == 0 || t == null || t.length() == 0) {
        return "";
    }
    // Count frequency of characters in t
    Map<Character, Integer> targetMap = new HashMap<>();
    for (char c : t.toCharArray()) {
        targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
    }
    // Sliding window variables
    int left = 0, right = 0;
    int required = targetMap.size();  // unique characters in t
    int formed = 0;                   // characters matched in current window
    Map<Character, Integer> windowCounts = new HashMap<>();
    int minLen = Integer.MAX_VALUE;
    int minLeft = 0;
    // Expand window with right pointer
    while (right < s.length()) {
        char c = s.charAt(right);
        windowCounts.put(c, windowCounts.getOrDefault(c, 0) + 1);
        if (targetMap.containsKey(c) && windowCounts.get(c).intValue() == targetMap.get(c).intValue()) {
            formed++;
        }
        // Contract window with left pointer
        while (left <= right && formed == required) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minLeft = left;
            }
            char leftChar = s.charAt(left);
            windowCounts.put(leftChar, windowCounts.get(leftChar) - 1);
            if (targetMap.containsKey(leftChar) && windowCounts.get(leftChar).intValue() < targetMap.get(leftChar).intValue()) {
                formed--;
            }
            left++;
        }
        right++;
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
}

4. Monotonic Window (Deque Optimization)

A monotonic window uses a deque (double-ended queue) to maintain elements in either increasing or decreasing order. This allows efficient retrieval of the maximum or minimum value within the current window without scanning the entire window each time. It is a highly optimized variation of the fixed-size sliding window.

When to Use:

Use this pattern when the problem specifically asks for:

• The maximum or minimum element in every window of size k.

• Optimized calculations on extreme values within sliding windows to reduce time complexity from O(n·k) → O(n).

Interview Questions:

• Sliding Window Maximum (LeetCode 239).

• Sliding Window Minimum.

• Stock Price Span problem.

• Maximum of all subarrays of size k.

• Minimum of all subarrays of size k.

• Maximum temperature in the last k days.

• Longest subarray where all elements are ≤ current max.

• Sliding window for rainwater trapping per segment (optimized).

Key Insight:

The deque stores indices, not values and ensures monotonic order:

• Remove indices from the back if the current element is larger (for max) or smaller (for min).

• Remove indices from the front if they fall out of the current window.

This ensures O(n) time complexity while always keeping the extreme value at the front of the deque.

Example : Minimum element in every window of size k

Given an array arr[] and an integer k, find the minimum element in every contiguous subarray (window) of size k.

arr = [1, 3, -1, -3, 5, 3, 6, 1], k = 3
Output: [ -1, -3, -3, -3, 3, 1 ]

// ---------------------- Java --------------------------
public static int[] minSlidingWindow(int[] arr, int k) {
    if (arr == null || k <= 0 || arr.length < k) {
        return new int[0];
    }
    int n = arr.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> deque = new LinkedList<>(); // stores indices
    int ri = 0;
    for (int i = 0; i < n; i++) {
        // Remove indices that are out of the current window
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        // Remove elements from deque that are greater than current element
        while (!deque.isEmpty() && arr[deque.peekLast()] > arr[i]) {
            deque.pollLast();
        }
        // Add current element index to deque
        deque.offerLast(i);
        // The front of the deque is the min of the current window
        if (i >= k - 1) {
            result[ri++] = arr[deque.peekFirst()];
        }
    }
    return result;
}

5. Counting Windows

Counting windows focus on enumerating or counting the number of valid subarrays/substrings that satisfy a given condition, rather than returning a specific maximum, minimum or sum. This pattern often combines variable-size sliding windows with hash maps or frequency counters to efficiently keep track of elements in the current window.

When to Use:

Use this pattern when the problem explicitly asks for:

• The number of subarrays or substrings that meet certain criteria.

• Counting occurrences instead of finding extremes.

• Problems where constraints involve frequencies, sums, or products.

Interview Questions:

• Count subarrays with product < K.

• Count substrings with exactly k distinct characters.

• Count binary subarrays with sum = target.

• Count subarrays with sum divisible by K.

• Count subarrays with at most K distinct elements.

• Count substrings containing all vowels at least once.

• Count subarrays where the maximum element ≤ target.

• Count subarrays with exactly one odd number.

Key Insight:

• Often uses a hash map or frequency array to track element counts inside the window.

• Can be implemented with variable-size windows to dynamically expand and shrink based on the condition.

• Efficiently reduces brute-force O(n²) approaches to O(n) or O(n log n) depending on constraints.

Example : Count subarrays with product < K.

Given an array of positive integers arr[] and an integer k, count the number of contiguous subarrays where the product of all elements is less than k.

arr = [10, 5, 2, 6], k = 100
Output: 8
Explanation: The subarrays are [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]

// ---------------------- Java --------------------------
public static int countSubarraysProductLessThanK(int[] arr, int k) {
    if (k <= 1) return 0; // No product can be less than 1 if k <= 1
    int n = arr.length;
    int count = 0;
    long product = 1; // use long to avoid overflow
    int left = 0;
    for (int right = 0; right < n; right++) {
        product *= arr[right];
        while (product >= k && left <= right) {
            product /= arr[left++];
        }
        // All subarrays ending at right with product < k
        count += (right - left + 1);
    }
    return count;
}

Key Takeaways

• Fixed window: Constant length, update by adding/removing elements

• Variable window: Expand/shrink based on dynamic conditions

• Minimum/Maximum window: Special case focusing on extreme window lengths

• Monotonic window: Efficient retrieval of max/min using deque

• Counting window: Count number of valid subarrays/substrings meeting constraints

By identifying the right sliding window pattern, you can optimize your DSA solutions and handle complex array/string problems efficiently.