Coding Patterns - Sliding Window

Intuition

The sliding window technique is a powerful optimization strategy used in problems involving arrays or strings. Instead of recalculating values for every possible subarray or substring, we maintain a window that slides across the data, updating results incrementally. This reduces redundant work and often improves complexity from O(n^2) to O(n).

Think of it as looking through a moving window on a train: at each step, you see a slightly updated view without re-scanning the entire scene.

Sliding Window Strategies

1. Fixed-Size Window

• The window has a fixed length (e.g., subarray of size k).

• Useful for maximum/minimum averages, sums, or k-length substring checks.

2. Dynamic-Size Window (Variable)

• The window expands and contracts based on conditions.

• Useful for problems like smallest subarray with a sum ≥ target, or longest substring without repeating characters.

3. Two-End Control

• Maintain both left and right boundaries.

• Slide the window intelligently when constraints are violated.

When To Use Sliding Window

Use this technique when:

• Problems involve subarrays or substrings.

• You need to maintain a running metric (sum, max, count).

• Conditions depend on a contiguous segment of data.

Real-World Example

Network Traffic Monitoring: Routers often monitor packets over the last k seconds. Instead of recalculating traffic from scratch, they maintain a sliding window of the last k entries, updating it as time progresses.

Data Analytics: Moving averages in stock prices or website analytics use sliding windows to calculate trends in real time.

Coding Example 1: Maximum Sum of Subarray of Size k

def max_subarray_sum(nums, k):
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)

    return max_sum

# Example usage
print(max_subarray_sum([2, 1, 5, 1, 3, 2], 3))  # 9 (5 + 1 + 3)

Coding Example 2: Longest Substring Without Repeating Characters

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

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

    return max_len

# Example usage
print(longest_unique_substring("abcabcbb"))  # 3 ("abc")
print(longest_unique_substring("bbbbb"))    # 1 ("b")

Framework

1. Define window boundaries (left, right indices).

2. Expand the window by moving the right pointer.

3. Update metrics (sum, counts, frequency map).

4. Contract the window when conditions are violated.

5. Track best result during traversal.

Key Points

• Sliding window avoids redundant recalculations.

• Fixed windows solve problems like maximum sum in O(n).

• Dynamic windows handle constraints like substring uniqueness.

• Common in interview problems involving strings and arrays.

Practice Exercise

Exercise 1: Implement a function to find the smallest subarray with a sum greater than or equal to a target.

Sample Solution:

def min_subarray_len(target, nums):
    left = 0
    curr_sum = 0
    min_len = float("inf")

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

    return 0 if min_len == float("inf") else min_len

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