Have you ever heard the term “Sliding Windows”? Wondering why it’s called windows and why they slide? Let’s find out!

A Simple Example

Suppose we have a large array nums and want to find the sum of the first 10 elements — indices 0 to 9. Think of this subarray as window 1. A window is just a subarray we’re interested in:

sum_of_window1 = 0
for i in range(0, 10):
    sum_of_window1 += nums[i]
print("Sum of window 1:", sum_of_window1)

Now we’re curious about the next window, the subarray from indices 1 to 10 (2nd to 11th elements). We’re moving — or sliding — the window by one element to the right. We could recalculate its sum:

sum_of_window2 = 0
for i in range(1, 11):
    sum_of_window2 += nums[i]
print("Sum of window 2:", sum_of_window2)

But this repeats a lot of work. Notice that window 2 differs from window 1 by just two elements:

• nums[0] is no longer included,
• nums[10] is newly included.

Instead of looping again, we can update in constant time by subtracting the old element and adding the new one:

sum_of_window2 = sum_of_window1 - nums[0] + nums[10]
print("Sum of window 2:", sum_of_window2)

With just one subtraction and one addition, we reuse the previous window’s sum rather than recomputing from scratch. That’s the core of the sliding window approach — taking advantage of what we already know to avoid extra work.

Why Does This Matter?

If we need the sums of the first 100 windows (each of size 10), we can do:

# Calculate the sum of the first window
sum_of_window = 0
for i in range(0, 10):
    sum_of_window += nums[i]
print("Sum of window 1:", sum_of_window)

# Calculate sums of subsequent windows
for window_index in range(1, 100):
    sum_of_window = sum_of_window - nums[window_index - 1] + nums[window_index + 9]
    print("Sum of window", window_index + 1, ":", sum_of_window)

Compare this to recalculating each window from scratch:

for window_index in range(1, 100):
    sum_of_window = 0
    for i in range(window_index, window_index + 10):
        sum_of_window += nums[i]
    print("Sum of window", window_index + 1, ":", sum_of_window)

You save a lot of time by avoiding an extra loop that runs k times (k = window size) for every shift of the window. Instead, you do just two operations per shift.

The essence of the Sliding Windows technique:

1. Find and maintain a subarray (window) of a specific size or condition.
2. Slide the window to the next position by removing the old element(s) and adding the new element(s). Recompute in O(1) or O(log(k)) time rather than O(k) each time.

Use this approach wherever a rolling or continuous data segment is involved—sums, averages, min/max values, counts of distinct elements, and more.

Practice using sliding windows in the task below.

qi_readings = [2, 1, 5, 1, 3, 2]
k = 3

9

The fixed-size sliding window is a straightforward application, but often we encounter problems where the window size isn’t fixed but is determined by problem constraints. A classic example is finding the smallest subarray with a sum greater than or equal to a given target.

nums = [2, 1, 5, 2, 3, 2]
target = 7

Multiple subarrays of different sizes meet the condition (e.g., [5, 2], [2, 3, 2]), but we seek the smallest one. A brute-force approach checks all subarrays, taking O(n^2) time—impractical for large arrays.

Dynamic Sliding Window Approach
Instead, let's use a dynamic sliding window in O(n) time. We will use two pointers, left and right, to manage the window’s boundaries, and move through subarrays akin to caterpillars crawling forward.

Expand & Shrink Strategy

• Expand by moving right to the right until current_sum meets or exceeds target.
• Shrink from the left by incrementing left while maintaining the sum condition, tracking the smallest subarray length found.
• Once current_sum is less than target, we can expand again to the right.

left = 0
current_sum = 0
min_length = float('inf')

for right in range(len(nums)):
    current_sum += nums[right]

    # Shrink the window while current_sum >= target
    while current_sum >= target:
        min_length = min(min_length, right - left + 1)
        current_sum -= nums[left]
        left += 1

if min_length == float('inf'):
    print("No subarray found.")
else:
    print("Smallest subarray length:", min_length)

Even though there are nested loops, the time complexity of this approach is O(n), because left and right pointers move through the array only once. The space complexity is O(1), because we are only using a few variables to track the state of the window.

We can summarize the dynamic sliding window approach as follows:

1. Two Pointers (Left & Right):
   • Right pointer extends the window.
   • Left pointer shrinks the window when a condition is exceeded or met.
2. Condition Checks:
   • Could be a sum threshold, a character frequency limit, etc.
   • Move the left pointer whenever the condition is violated or satisfied (depending on problem needs).
3. Track Answer:
   • Continuously update the result (e.g., the shortest window that meets a sum, or the longest window of unique chars).

Sliding windows are a subset of Two Pointers, crucial for problems with variable-size windows. For a deeper dive into Two Pointers, explore the guide on Two Pointers / Index Pointers technique here.

Practice using dynamic sliding windows with the task below to master this powerful technique.

candles = [7, 2, 3, 1, 5, 4, 3, 2]
max_brightness = 7

3

So far, we’ve looked at summation-based sliding windows, where the state of the window is tracked by a single variable (the sum). Another common pattern is frequency-based sliding windows, where we track how many times each element (or character) appears in the window. Some examples include:

• Finding the longest substring with unique characters.
• Locating subarrays that have at most k distinct elements.
• Solving anagrams or frequency-based search problems.

Let's start with a classic example of finding the longest substring with unique characters.

Task: given a string, find the length of the longest substring in which all characters are unique.

For example, given the string "faangfaang", the longest substring with unique characters is "angf", which has a length of 4.

We can solve this with a dynamic sliding window and a set to keep track of the characters in the window. Often you would use a hash map to keep track of the frequency of each character in the window, but in this problem, we only need to know if a character is in the window or not. The general approach is:

1. "Expand" - move the right pointer and add the character to the set.
2. "Shrink" - if the character is already in the set, move the left pointer to the right until the character is no longer in the set.
3. At any moment, after the "Shrink" step, the set will contain only unique characters.
4. When expanding, update the maximum length of the substring with unique characters.

def longest_unique_substring(s):
    char_set = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        # If the character at 'right' is already in our set,
        # remove chars from the left until it's safe to add the new one
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1

        # Add the new character and update max_len
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)

    return max_len

# Example usage
s = "abcabcbb"
print(longest_unique_substring(s))  # Output: 3 (e.g., "abc")

Frequency-based sliding windows let you handle frequency constraints within a subarray or substring. Notice that similar to summation-based sliding windows, frequency-based sliding windows performs the updates of the state of the window in O(1) time.

Practice using frequency-based sliding windows with the task below.

scroll = "aabacbebebe"

6

A common variation of frequency-based sliding windows is identifying anagrams of a given string within another string.

Task: Given two strings s1 and s2, determine if s2 contains any substring that’s an anagram (i.e., permutation) of s1. In other words, does a window in s2 have exactly the same character frequencies as s1?
For example, given s1 = "ab" and s2 = "eidbaooo", the output is True because s2 contains the substring "ba", which is an anagram of s1.

The key differences from earlier examples are:

• We’re comparing frequency maps (or arrays) for s1 and for each window in s2.
• The window size is fixed to len(s1).
• Checking if two frequency arrays match is not a single operation, but it's effectively O(1) if you have a fixed character set (e.g., 26 lowercase letters).

Here's the step-by-step approach:

1. Compute Character Frequency for s1:
   • Use an array or dictionary freq_s1 to store how many times each character appears.
2. Initialize a Window in s2:
   • The window size is len(s1).
   • Compute a similar frequency array/dict freq_s2 for the first len(s1) characters in s2.
3. Check Frequencies:
   • If freq_s2 == freq_s1, return True.
4. Slide the Window:
   • For each subsequent index in s2, remove the character going out of the window from freq_s2 and add the new character coming into the window.
   • Compare freq_s2 to freq_s1 again. If they match at any point, return True.
5. No Match Found:
   • If you slide the entire length of s2 without finding a matching frequency map, return False.

def check_inclusion(s1, s2):
    if len(s1) > len(s2):
        return False

    # Frequency array for s1 and current window in s2
    freq_s1 = [0] * 26
    freq_s2 = [0] * 26

    def char_to_index(c):
        return ord(c) - ord('a')

    # Build freq_s1 and initial freq_s2 window
    for i in range(len(s1)):
        freq_s1[char_to_index(s1[i])] += 1
        freq_s2[char_to_index(s2[i])] += 1

    # If the first window already matches, return True
    if freq_s2 == freq_s1:
        return True

    # Slide the window over s2
    for right in range(len(s1), len(s2)):
        # Character going out (left side)
        left_char_idx = char_to_index(s2[right - len(s1)])
        freq_s2[left_char_idx] -= 1

        # Character coming in (right side)
        right_char_idx = char_to_index(s2[right])
        freq_s2[right_char_idx] += 1

        # Check if we match s1's frequencies
        if freq_s2 == freq_s1:
            return True

    return False

# Example usage:
s1 = "ab"
s2 = "eidbaooo"
print(check_inclusion(s1, s2))  # Output: True (s2 contains "ba")

Practice using anagram-based sliding windows with the task below.

scroll = "ADOBECODEBANC"
passage = "ABC"

"BANC"

Beyond sums and character frequencies, sliding windows can also help you quickly find the minimum or maximum element in each window as it slides across an array. This is particularly handy for things like real-time streaming data, temperature logs, or any scenario where you want the max/min of a rolling window.

Here's how the task is described:

Task: Given an array nums and a window size k, determine the maximum value within each window of size k as the window slides from left to right.

For example:

nums = [1,3,-1,-3,5,3,6,7], k = 3
Output = [3,3,5,5,6,7]

Here’s how the windows progress:

• [1,3,-1] → max is 3
• [3,-1,-3] → max is 3
• [-1,-3,5] → max is 5
• [-3,5,3] → max is 5
• [5,3,6] → max is 6
• [3,6,7] → max is 7

Naively, you’d recalculate the max in each window by scanning all k elements in O(k) per window, leading to O(n*k) overall. If k is large and n is huge, that’s painful. Instead, we use a data structure to update or remove elements in O(1) time, typically a deque (double-ended queue). You can also use a heap, but that’s O(log n) per operation, which is slower.

Deque-Based Method

1. Store Indices (Not Values)
   • The deque holds indices of array elements. This helps you remove elements that slide out of the window’s range.
2. Monotonic Queue
   • You maintain the deque in a way that indices at the front always represent the largest element (for maximum).
   • When you insert a new element nums[i], you pop from the back while nums[i] is greater than or equal to nums[deque[-1]].
   • This preserves a descending order of elements in the deque (for maximum windows).
3. Drop Expired Indices
   • If the front index of the deque is out of the current window range (i.e., front_index < i - k + 1), pop it from the front.
4. Front of Deque = Window’s Max
   • At each step where the window fully forms, nums[deque[0]] is the maximum.

from collections import deque

def max_sliding_window(nums, k):
    if not nums or k == 0:
        return []

    dq = deque()  # Will store indices
    result = []

    for i in range(len(nums)):
        # Remove indices out of the current window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove elements smaller than current from the back
        while dq and nums[dq[-1]] <= nums[i]:
            dq.pop()

        # Add the current index
        dq.append(i)

        # Once the first window is fully formed, record the max
        if i >= k - 1:
            result.append(nums[dq[0]])  # The front index is the max

    return result

# Example usage:
nums = [1,3,-1,-3,5,3,6,7]
k = 3
print(max_sliding_window(nums, k))  # [3,3,5,5,6,7]

It's important to note:

• dq keeps indices, not values.
• We pop from the front if the index is out of the current window.
• We pop from the back if the new element is bigger or equal, ensuring we maintain a descending order for maximum.

Time Complexity:

• Each index enters and exits the deque once, so total time is O(n).
• Each window’s maximum is retrieved in O(1) time.

Try adapting this approach to find the minimum in a sliding window in the task below.

temps = [3, 1, 4, 1, 5, 9, 2, 6, 5]
k = 3

[1, 1, 1, 1, 2, 2, 2]