Sliding Window Technique — Core Concepts

What the sliding window solves

The sliding window technique processes subarrays or substrings efficiently by maintaining a window that moves through the data. Instead of examining every possible subarray (O(n²) or worse), the window updates incrementally — adding one element and removing another — achieving O(n) time.

It works on problems involving contiguous sequences: subarrays, substrings, or consecutive elements. If the problem asks about non-contiguous elements, sliding window is not the right tool.

Fixed-size window

When you know the window size in advance.

Template

def fixed_window(arr, k):
    # Initialize window with first k elements
    window_sum = sum(arr[:k])
    best = window_sum

    # Slide: add right element, remove left element
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        best = max(best, window_sum)

    return best

Example: Maximum sum of k consecutive elements

def max_sum_subarray(nums, k):
    window = sum(nums[:k])
    best = window

    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        best = max(best, window)

    return best

print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3))  # 9 (5+1+3)

Time: O(n). Without sliding window, checking all subarrays of size k takes O(n × k).

Example: Check if any k-length window contains duplicates

def contains_nearby_duplicate(nums, k):
    window = set()
    for i, num in enumerate(nums):
        if num in window:
            return True
        window.add(num)
        if len(window) > k:
            window.remove(nums[i - k])
    return False

Variable-size window

When you need to find the longest or shortest subarray meeting a condition.

Template for longest

def longest_window(arr):
    left = 0
    best = 0
    state = {}  # track window contents

    for right in range(len(arr)):
        # Expand: add arr[right] to state

        while not valid(state):  # shrink until valid
            # Remove arr[left] from state
            left += 1

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

    return best

Template for shortest

def shortest_window(arr, target):
    left = 0
    best = float('inf')
    state = 0

    for right in range(len(arr)):
        state += arr[right]  # expand

        while state >= target:  # shrink while valid
            best = min(best, right - left + 1)
            state -= arr[left]
            left += 1

    return best if best != float('inf') else 0

Notice the key difference: for longest, you shrink when invalid. For shortest, you shrink while valid.

Example: Longest substring without repeating characters

def longest_unique_substring(s):
    seen = {}
    left = 0
    best = 0

    for right, char in enumerate(s):
        if char in seen and seen[char] >= left:
            left = seen[char] + 1
        seen[char] = right
        best = max(best, right - left + 1)

    return best

print(longest_unique_substring("abcabcbb"))  # 3 ("abc")

Example: Minimum size subarray with sum ≥ target

def min_subarray_len(target, nums):
    left = 0
    current = 0
    best = float('inf')

    for right in range(len(nums)):
        current += nums[right]
        while current >= target:
            best = min(best, right - left + 1)
            current -= nums[left]
            left += 1

    return best if best != float('inf') else 0

print(min_subarray_len(7, [2, 3, 1, 2, 4, 3]))  # 2 (4+3)

How to identify sliding window problems

Look for these signals in the problem statement:

• “Contiguous subarray” or “substring”
• “Longest” or “shortest” with a condition
• “Maximum sum” of k consecutive elements
• “Contains all characters” of some target
• Constraint that suggests O(n) is expected

If the problem involves contiguous sequences and you can express the condition as something that either holds or breaks as the window expands, sliding window likely applies.

The two pointer connection

Sliding window is a specialized form of two pointers where both pointers move in the same direction (left to right). Classic two pointers move toward each other (converging). The key insight: in a sliding window, the left pointer never moves backward, guaranteeing O(n) total moves across both pointers.

Common misconception

“The inner while loop makes it O(n²).” It looks like the shrinking while loop adds an extra factor of n, but it does not. The left pointer moves at most n times total across the entire run. Each element is added once (by the right pointer) and removed at most once (by the left pointer). Total operations: 2n = O(n).

One thing to remember: The sliding window works because adding and removing one element at a time is cheaper than recomputing from scratch. If you can maintain your window state incrementally, you can transform an O(n²) brute force into an O(n) solution.