Sliding Windows Explained

Why “windows” and why do they slide? Let’s find out!

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

If you want to follow along with the built-in tasks and see the full guide, please read this guide on the Faangshui platform.

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 with the task below.

---

Fixed-Size vs Dynamic Sliding Windows

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.

---

Frequency-Based Sliding Windows

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.

---

As always, you can access the full guide with built-in exercises on the Faangshui platform.

Happy Coding!

Nurbo