Sliding Window

The sliding window technique is an elegant algorithmic approach that transforms certain problems from brute-force solutions with quadratic complexity or worse into efficient linear-time solutions.

You’ll see a sliding window pop up in classic problems like finding the maximum sum of a subarray or the longest substring without repeating characters, and even in more advanced scenarios like streaming data analysis. If you’ve ever needed to process “chunks” of data that overlap, you’ve probably brushed up against this technique.

Note: To get the most out of sliding window problems, you’ll want a solid grasp of basic programming, especially working with arrays and pointers. If you’re comfortable with for-loops and indexing, you’re in good shape.

What is the Sliding Window technique?

At its core, the sliding window technique involves maintaining a “window”, a subset of elements from a larger dataset, that slides across the data structure from left to right. Rather than recalculating everything for each possible subset, the window efficiently updates by adding new elements on one end and removing old elements from the other.

1 / 4

Understanding Sliding Window with a real-world example

To better understand a sliding window, imagine looking through a physical window at a scenic landscape. As you walk alongside a wall, your view changes: new scenery appears on one side while the view on the other side disappears. The sliding window algorithm works similarly, maintaining a dynamic view of a portion of your data.

It uses two pointers to mark the window’s boundaries. As these pointers traverse an array or string, they define which portion of the data is currently being examined.

The window updates dynamically, new elements enter as the pointers advance, while old elements exit, maintaining an efficient view of the current subset.

Types of sliding window

The sliding window technique is built on two fundamental concepts: the window’s size and how its boundaries move. These concepts give rise to two primary approaches:

Fixed-size windows

Fixed-size windows maintain a constant width as they traverse the data, with both pointers moving together to keep the window size unchanged. These are useful when you need to examine all subarrays or substrings of a specific length.

For example, if you need to find the largest sum of three consecutive numbers, the window size stays at three while sliding across the array.

1 / 5

Variable-size windows

Variable-size windows allow independent pointer movement, with one pointer (usually the right) expanding the window while the other (left) contracts it based on certain conditions. These are powerful for problems where you need to find the smallest or largest subarray that satisfies specific criteria. A classic example that uses variable-sized windows is finding the smallest subarray with a sum greater than a target value.

Python implementation

Here’s a Python implementation that finds the maximum sum of any subarray using a fixed sliding window:

def maxSumSubarray(arr, k):
    # Edge cases: invalid k or empty array
    if not arr or k <= 0 or k > len(arr):
        return None

    # Pre-calculate the first window
    # This avoids the "if end - start + 1 < k" check inside the loop
    current_window_sum = sum(arr[:k])
    max_sum = current_window_sum

    # Slide the window
    # Start loop from index k to the end of the array
    for i in range(k, len(arr)):
        # Add the next element and subtract the one sliding out
        current_window_sum += arr[i] - arr[i - k]
        
        if current_window_sum > max_sum:
            max_sum = current_window_sum

    return max_sum


def main():
    tests = [
        ([2, 1, 5, 1, 3, 2], 3),
        ([1, 2, 3, 4, 5], 2),
        ([-2, -1, -3, -4], 2),
        ([5], 1),
    ]

    for i, (arr, k) in enumerate(tests, start=1):
        print(f"{i}.\tArray: {arr}")
        print(f"\tWindow size (k): {k}")

        result = maxSumSubarray(arr, k)
        print(f"\tMaximum sum of any subarray of size {k}: {result}")
        print("-" * 75)


if __name__ == "__main__":
    main()

When to use a sliding window?

You should strongly consider a sliding window when a coding problem has any of the following signals:

• The problem describes contiguous sequences:
  • The prompt mentions “consecutive elements,” “substring,” or “subarray.”
  • You need to find a subarray with a specific sum, product, or other aggregate property.
  • The task resembles finding an optimal window, such as smallest subarray with sum ≥ target.
• The task involves optimization with conditions:
  • It asks for maximum, minimum, longest, or shortest among all windows of a certain size or condition.
  • The problem involves “at most k” or “at least k” of something within a contiguous range.
  • The input includes phrases like “all anagrams,” “permutation in string,” or “repeating characters.”
• Efficiency is a concern:
  • You need to track frequencies or counts of elements within a range that shifts.
  • The constraints suggest that checking every possible subarray with nested loops would be too slow.

Common pitfalls and edge cases

These mistakes frequently cause incorrect answers or timeouts.

1. You should not move the left pointer backward in variable-size windows, because this violates the linear time guarantee and can cause infinite loops.
2. You should not forget to update your result before or after adjusting the window, because the optimal answer might be found mid-slide.
3. You should handle edge cases like empty arrays, single-element arrays, or windows larger than the array itself.
4. You should be careful with window initialization, ensuring you process the first window correctly before sliding.
5. You should choose the right condition for expanding versus contracting the window in variable-size problems, because reversing these leads to wrong answers.
6. You should not confuse “at most k” with “exactly k” conditions, because they require different window adjustment logic.