Capturing values in a data set using the sliding window

The sliding window technique is a pattern for capturing a particular value in a set of data. The capture works by adding a new value to the start of the window (usually a sub-array) and kicking out the last value, thereby “sliding the window.” Adding or subtracting these elements will depend on the constraints of the problem. We repeat this process until a condition is met or we’ve hit the end of the data.

When would you consider using it?

This technique is commonly used for solving problems related to arrays, strings, or sequences where you need to find a subset (like subarray or substring) to meet a certain condition. If it applies to your problem, you’ll also need to decide if your problem requires a static or a dynamic sliding window using the constraints of the problem as guidance. Static windows don’t change in size, they remain the same throughout the duration of the slide. Dynamic windows on the other hand do change in size as they move over the data. The condition that changes their size must be carefully decided or algorithm may lose its efficiency or won’t yield the correct result.

Static Window

In a static sliding window, the window grows until it reaches a fixed size (k). Once it reaches that size, it stays the same size and “slides” forward one step at a time across the data. This is well suited for problems that require finding a sum, product, average, maximum, etc., on some select number of consecutive elements inside a dataset.

Implementing the static sliding window

Let’s take a look at how the static sliding window pattern can be implemented using Python. We’ll walk through the function def FindMaxAverage(nums: List[int], k: int) -> float where we take in an array of integers (nums), a window size (k) and return the max average of the consecutive elements inside the window (float). You can find the full source code here.

def FindMaxAverage(self, nums: List[int], k: int) -> float:
    # note: a '_' precedes "max" and "sum" because they're keywords in Python
    _max = float('-inf')
    _sum, left = 0, 0, 0            # left moves the end of the window

    for right in range(len(nums)):  # right moves the start of the window
        _sum += nums[right]

        # when our window has grown to include our max of k elements
        if right >= k - 1:
            avg = _sum / k
            if(avg > _max):
                _max = avg

            _sum -= nums[left]      # kick out the last element
            left += 1               # slide the end of the window (left) ahead

    return _max

Setting things up

_max = float('-inf')
_sum, left = 0, 0, 0

Before we start sliding the window we need to prepare some variables. _sum tracks the sum of all elements inside the window while _max tracks the current maximum average we need to return. left is the “pointer” that represents the left edge of the sliding window. This means it’s index of the element that will be removed when the window slides forward. Setting each variable to 0 gives us a clean slate to start.

Moving the right edge

for right in range(len(nums)):

This loop moves the right edge of the window one step at a time across the list (nums). Each time the right pointer increases, the size of the window grows by one element.

Adding new elements to the window

_sum += nums[right]

When the window grows, we need to include the new number into the total sum of the window (_sum). To improve efficiency we simply add the new value to _sum instead of counting through each element inside our window. This optimization is one of key benefits in choosing the sliding window technique—it keeps the algorithm efficient.

Tracking the window size

if right >= k - 1:

This is the condition that ensures we only calculate the max average when our window contains k elements (our maximum allowed window size). Since right is zero-based, the window reaches size k when right is at position k - 1. Before this point, the window is still growing and is not ready to be checked.

Sliding the window forward

_sum -= nums[left]
left += 1

To slide the window, we remove the element at the left edge from _sum and then move left forward by one position. This keeps the window size fixed at k. On the next loop iteration, a new element will be added on the right, and the process repeats. This “add one, remove one” pattern is the heart of a static sliding window.

Dynamic Window

In a dynamic sliding window, the window does not have a fixed size. Instead, it expands and shrinks based on a condition defined by the problem. The window grows as we move forward through the data, but when a rule is broken, the window is reduced from the left until the condition is satisfied again. This approach is well suited for problems where the size of the valid window can change, such as finding the longest or shortest sequence that meets certain constraints.

Implementing the dynamic sliding window

Let’s take a look at how the dynamic sliding window pattern can be implemented. We’ll walk through the function def longestOnes(nums: List[int], k: int) -> int, where we take in an array of binary values (nums) and a number (k) representing how many zeros we are allowed to flip. The goal is to return the length of the longest contiguous subarray that contains at most k zeros. You can find the full source code here.

def LongestOnes(self, nums: List[int], k: int) -> int:
    longest_ones = 0
    left, zero_count = 0, 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zero_count += 1

        # shrink the window while count is above k
        while zero_count > k:
            if nums[left] == 0:
                zero_count -= 1
            left += 1

        longest_ones = max(longest_ones, (right - left + 1))

    return longest_ones

Setting things up

longest_ones = 0
left, zero_count = 0, 0

We start by initializing some variables that will track the state of our window. left is a pointer to the left edge of the window. zero_count tracks how many zeros are currently inside the window. The variable longest_ones stores the longest sequence of ones that we’ve discovered in the list.

Moving the right edge

for right in range(len(nums)):

This loop moves the right edge of the window forward through the list. Each time right increases, the window expands to include one more element in the same way as the static window. At this stage, we are always trying to grow the window as large as possible.

Shrinking the window when the condition is broken

while zero_count > k:
    if nums[start] == 0:
        zero_count -= 1
    start += 1

If the window contains more than k zeros, it is no longer valid. At this point, we shrink the window by moving the left pointer forward. As elements leave the window, we update zero_count if a zero is removed. This process continues until the window becomes valid again. This expanding-and-shrinking behavior is what defines a dynamic sliding window.

Recording the size of the valid window

longest_ones = max(longest_ones, (end - start + 1))

Once the window satisfies the condition again, we calculate its current size and compare it to the largest valid window we have seen so far. If the current window is larger, we update longest_ones. Because this check happens after any necessary shrinking, we know the window is valid when we record its size. Once the loop finishes we can return longest_ones as the longest consecutive sequence we were able to discover.

Final Words

Static and dynamic sliding windows are both effective techniques for working with consecutive elements inside a dataset but they differ in how the window boundaries are adjusted. Both static and dynamic sliding windows run in O(n) time because each element enters and leaves the window at most once. Static windows maintain a fixed size, while dynamic windows adjust their size based on a condition, but neither revisits elements unnecessarily. In most cases, both approaches use O(1) extra space, since they rely on a few variables to track the window rather than additional data structures.