Sliding Window and Pattern - (Theory)

What is the Sliding Window Technique?

The Sliding Window Technique is an algorithmic approach used to solve problems that require examining all contiguous subarrays or substrings of a given size or range in a linear structure like arrays or strings.

This technique involves moving a “window” across the input data to keep track of specific properties (like sum, max, frequency) without reprocessing the entire window after every move.

Key Benefits:

• Reduces time complexity from O(n²) (brute-force) to O(n) or O(n log n)

• Ideal for problems involving subarrays or substrings

• Efficient for large inputs

Relation to the Two Pointers Technique

The Sliding Window Technique is conceptually derived from the Two Pointers Technique.

Two Pointers Basics:

• You maintain two pointers (typically called start and end) that traverse the data structure.

• They can move independently or in coordination, often used in sorted arrays or linked lists.

How Sliding Window Extends Two Pointers:

• One pointer marks the start of the window, and the other marks the end.

• You perform operations (like maintaining a sum, a frequency map, etc.) on the current window.

• The window "slides" forward by incrementally updating only the changed elements.

Core Sliding Window Patterns

The technique can be categorized into three core patterns based on the window behavior and constraint types.

1. Fixed Size Sliding Window

Definition:

Used when the window size is constant (usually given as k in the problem).

Typical Use Cases:

• Find the maximum/minimum sum of subarrays of size k

• Calculate average of each subarray of size k

• Track max/min element in every window of size k

Algorithm Logic:

• Initialize start = 0, end = 0, and any variable you need to track (e.g., sum, max)

• Expand the window by increasing end

• Once end - start + 1 == k, calculate the result, update the answer, and slide the window forward by incrementing start

Time and Space Complexity:

• Time: O(n)

• Space: O(1) unless using extra data structures like Deque (O(k))

Example: Maximum Sum Subarray of Size K

public int maxSum(int[] nums, int k) {
    int start = 0, sum = 0, maxSum = 0;
    for (int end = 0; end < nums.length; end++) {
        sum += nums[end];
        if (end - start + 1 == k) {
            maxSum = Math.max(maxSum, sum);
            sum -= nums[start++];
        }
    }
    return maxSum;
}

2. Variable Size Sliding Window

This pattern is used when the window size changes dynamically depending on a condition.

There are two subtypes:

(a) Variable Size - Condition Based Only

Used when the condition is based on numerical thresholds or cumulative properties (like sum), without needing a hashmap or set.

Use Cases:

• Longest subarray with sum less than or equal to a target

• Minimum length subarray with sum greater than or equal to a target

Algorithm Logic:

• Expand end while the condition is valid

• Shrink start when the condition is violated

• Maintain the required variable (sum, length, etc.) throughout

Time and Space Complexity:

• Time: O(n)

• Space: O(1)

Example: Minimum Subarray Length With Sum ≥ Target

public int minSubArrayLen(int target, int[] nums) {
    int start = 0, sum = 0, minLength = Integer.MAX_VALUE;
    for (int end = 0; end < nums.length; end++) {
        sum += nums[end];
        while (sum >= target) {
            minLength = Math.min(minLength, end - start + 1);
            sum -= nums[start++];
        }
    }
    return minLength == Integer.MAX_VALUE ? 0 : minLength;
}

(b) Variable Size - Condition Based with Hash Table or Hash Set

Used when you must track the frequency, uniqueness, or count of specific elements within the window.

Use Cases:

• Longest substring without repeating characters

• Longest substring with at most K distinct characters

• Finding permutations or anagrams in a string

Algorithm Logic:

• Use a hash map or set to maintain current state (e.g., character frequency)

• Expand end, update the map/set

• If the condition is violated (e.g., duplicate found or more than K distinct characters), shrink start and update the structure accordingly

Time and Space Complexity:

• Time: O(n)

• Space: O(n)

Example: Longest Substring Without Repeating Characters

public int lengthOfLongestSubstring(String s) {
    Set<Character> seen = new HashSet<>();
    int start = 0, maxLen = 0;
    for (int end = 0; end < s.length(); end++) {
        while (seen.contains(s.charAt(end))) {
            seen.remove(s.charAt(start++));
        }
        seen.add(s.charAt(end));
        maxLen = Math.max(maxLen, end - start + 1);
    }
    return maxLen;
}

Summary Table of Sliding Window Patterns

Advanced Sliding Window Variations

In addition to the three core types, the following are advanced and specialized applications of the sliding window.

3. Sliding Window with Deque (Monotonic Queue)

Description:

Used to maintain elements in order (increasing or decreasing) for max/min queries in each window.

Use Case:

• Sliding window maximum

• Maximum of each subarray of size k

Time and Space Complexity:

• Time: O(n)

• Space: O(k)

4. Sliding Window with Binary Search

Description:

Used when you cannot directly determine the validity of a window in O(1) and must apply binary search on the window size.

Use Case:

• Longest substring with at most K character replacements

• Binary search over the length, sliding window as a validator

Time and Space Complexity:

• Time: O(n log n)

• Space: O(n)

5. Circular Sliding Window

Description:

Used when the array wraps around (circular structure). You can simulate this with an extended array or modulo indexing.

Use Case:

• Find the maximum sum in a circular array

When to Use Sliding Window Technique

Ask yourself these questions:

1. Are you dealing with contiguous elements in an array or string?

2. Are you interested in properties like sum, max, frequency, or uniqueness over a range?

3. Can the required property be maintained incrementally as the window slides?

4. Is brute-force giving you O(n²) complexity and you need optimization?

Checklist for Solving Sliding Window Problems

• Determine if the window size is fixed or variable.

• Identify the condition that governs the window’s validity.

• Decide if additional data structures (like HashMap or Set) are needed.

• Carefully handle window expansion and contraction.

• Track updates correctly when sliding the window forward.

Conclusion

The sliding window technique is one of the most powerful and versatile tools in algorithm design. With a solid grasp of its fixed and variable size patterns, and the ability to integrate auxiliary structures like hash tables and deques, you can approach a wide range of problems with optimal efficiency.

Quick Recap:

• Fixed Size: Best for averaging, max/min over k elements – O(n)

• Variable Size – Constraint Only: Sum/range-based problems – O(n)

• Variable Size – With Lookup: Uniqueness, frequency problems – O(n), O(n)

• Extended Variations: Useful in complex and real-world scenarios like circular data or sliding maximums