What Is Sliding Window Technique? Explained with Simple Examples

Definition: What Is Sliding Window Technique?

The Sliding Window Technique uses two pointers to maintain a window (subarray or substring) that slides through an array or string. The window expands or contracts based on conditions, allowing efficient O(n) solutions for subarray/substring problems without recalculating overlapping elements.

Sliding window is efficient because instead of checking all possible subarrays (O(n²) or O(n³)), you maintain a window that slides through the array, adding and removing elements as needed. Each element is processed at most twice (added once, removed once), giving O(n) time complexity.

Common types include: fixed-size window (window size stays constant) and variable-size window (window size changes based on conditions). Sliding window is one of the most important techniques for solving subarray/substring problems efficiently.

Key Point: Sliding window uses two pointers to maintain a window that slides through an array/string. Window expands/contracts based on conditions, giving O(n) time complexity. Common types: fixed-size (constant size) and variable-size (size changes). Avoids recalculating overlapping elements.

What: Understanding Sliding Window Types

Sliding window has two main types:

Real-Life Analogy: Window Shopping

Sliding window is like looking through a store window:

Fixed Window:Always look at 3 items at a time

Window size stays constant as you slide along the display

Variable Window:Look at items until you find what you want

Window size changes based on what you're looking for

Efficient:Don't re-examine items you've already seen

Just slide the window and update what's inside

Just like window shopping, sliding window efficiently processes elements without re-examining what you've already seen.

Fixed-Size Sliding Window

Window size stays constant. Both left and right pointers move together, maintaining the same window size. Common for: finding maximum/minimum sum of subarray of size k, average of subarray of size k. Example: Find maximum sum of subarray of size 3 in [1, 2, 3, 4, 5] → windows: [1,2,3], [2,3,4], [3,4,5].

Example: Find maximum sum of subarray of size k

Variable-Size Sliding Window

Window size changes based on conditions. Right pointer expands window, left pointer contracts when condition is met. Common for: longest substring with at most k distinct characters, minimum window substring, longest subarray with sum less than k. Window expands/contracts independently.

Example: Find longest substring with at most k distinct characters

Window State

Window state tracks elements within the window (using hash map, set, or variables). When window expands, add new element to state. When window contracts, remove element from state. State is updated incrementally, avoiding recalculation. This makes sliding window O(n) instead of O(n²).

Example: Use hash map to track character frequencies in window

Sliding Window Types Visualization

Fixed-Size Window (Size = 3)

Window 1: [1,2,3]

Window 2: [2,3,4]

Window 3: [3,4,5]

Window size stays constant (3), slides one position at a time

Variable-Size Window

Window size: 2

Window size: 3 (expanded)

Window size: 3 (contracted)

Window size changes based on conditions (expands/contracts)

Important: Fixed window maintains constant size, both pointers move together. Variable window changes size, expands/contracts independently. Window state tracks elements efficiently, avoiding recalculation. Both types give O(n) time complexity.

When: When to Use Sliding Window

Use sliding window in these situations:

Use Sliding Window When:

Subarray/substring problems: Longest substring, minimum window
Constraints on window: Sum less than k, at most k elements
Contiguous elements: Need consecutive subarray/substring
Fixed-size subarray: Maximum sum of subarray of size k
Can maintain state: Track window efficiently with hash map/set

Avoid Sliding Window When:

Non-contiguous elements: Need non-consecutive elements
Complex state: Window state too complex to maintain
Need all subarrays: Sliding window finds one solution
Sorted order needed: Sliding window works on unsorted arrays
Non-linear structure: Sliding window works on arrays/strings

Common Scenario: Use sliding window for subarray/substring problems, constraints on window, contiguous elements, and when you can maintain window state efficiently. Avoid sliding window for non-contiguous elements or complex state.

How To: Use Sliding Window with Examples

Learn to use sliding window with examples:

Example 1: Maximum Sum of Subarray of Size K (Fixed Window)

Find maximum sum of subarray of fixed size k:

# Maximum sum of subarray of size k
# Array: [1, 4, 2, 10, 23, 3, 1, 0, 20], k = 4

def max_sum_subarray_fixed(arr, k):
    n = len(arr)
    if n < k:
        return -1
    
    # Calculate sum of first window
    window_sum = sum(arr[0:k])
    max_sum = window_sum
    
    # Slide window: remove leftmost, add rightmost
    for i in range(k, n):
        window_sum = window_sum - arr[i - k] + arr[i]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

# Example usage
arr = [1, 4, 2, 10, 23, 3, 1, 0, 20]
k = 4
result = max_sum_subarray_fixed(arr, k)
print(result)  # Output: 39 (subarray [4, 2, 10, 23])

# How it works:
# Window 1: [1,4,2,10] sum = 17
# Window 2: [4,2,10,23] sum = 39 (max)
# Window 3: [2,10,23,3] sum = 38
# Window 4: [10,23,3,1] sum = 37
# ... and so on

Fixed Window Sliding Process

Window 1:

Sum: 17

Window 2:

Sum: 39 (max!)

Window 3:

Sum: 38

Example 2: Longest Substring with At Most K Distinct Characters (Variable Window)

Find longest substring with at most k distinct characters:

# Longest substring with at most k distinct characters
# String: "eceba", k = 2

def longest_substring_k_distinct(s, k):
    if not s or k == 0:
        return 0
    
    left = 0
    max_len = 0
    char_count = {}  # Track character frequencies in window
    
    for right in range(len(s)):
        # Add current character to window
        char_count[s[right]] = char_count.get(s[right], 0) + 1
        
        # Shrink window if more than k distinct characters
        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1
        
        # Update maximum length
        max_len = max(max_len, right - left + 1)
    
    return max_len

# Example usage
s = "eceba"
k = 2
result = longest_substring_k_distinct(s, k)
print(result)  # Output: 3 (substring "ece" or "ceb")

# How it works:
# Expand window by moving right pointer
# Contract window when distinct chars > k
# Track max length of valid window

Variable Window Process: "eceba", k=2

Step 1:

Window: "ece" (2 distinct: e,c) Length: 3

Step 2:

Window: "ceb" (3 distinct: c,e,b) → Contract

Step 3:

Window: "eb" (2 distinct: e,b) Length: 2

Example 3: Minimum Window Substring (Variable Window)

Find minimum window substring containing all characters of pattern:

# Minimum window substring
# String: "ADOBECODEBANC", Pattern: "ABC"
# Find minimum window containing all characters of pattern

def min_window_substring(s, t):
    if not s or not t or len(s) < len(t):
        return ""
    
    # Count characters needed
    need = {}
    for char in t:
        need[char] = need.get(char, 0) + 1
    
    left = 0
    min_len = float('inf')
    min_start = 0
    missing = len(t)  # Characters still needed
    
    for right in range(len(s)):
        # Expand window
        if s[right] in need:
            if need[s[right]] > 0:
                missing -= 1
            need[s[right]] -= 1
        
        # Contract window when all characters found
        while missing == 0:
            # Update minimum window
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_start = left
            
            # Shrink window from left
            if s[left] in need:
                need[s[left]] += 1
                if need[s[left]] > 0:
                    missing += 1
            left += 1
    
    return s[min_start:min_start + min_len] if min_len != float('inf') else ""

# Example usage
s = "ADOBECODEBANC"
t = "ABC"
result = min_window_substring(s, t)
print(result)  # Output: "BANC" (minimum window containing A, B, C)

Best Practice: For fixed window, calculate first window sum, then slide by subtracting leftmost and adding rightmost. For variable window, expand with right pointer, contract with left pointer when condition met. Use hash map/set to track window state efficiently. Sliding window gives O(n) time complexity.

Why: Why Sliding Window Matters

Sliding window matters for these reasons:

O(n) Time Complexity

Sliding window provides O(n) time complexity for subarray/substring problems. Instead of O(n²) or O(n³) brute force, sliding window processes each element at most twice (added once, removed once). This makes algorithms much faster, especially for large inputs.

Avoids Recalculation

Sliding window avoids recalculating overlapping elements. When window slides, you only update the state (add new element, remove old element), instead of recalculating the entire window. This makes sliding window much more efficient than brute force approaches.

Common Interview Topic

Sliding window is a very common coding interview topic. Interviewers frequently ask about longest substring, minimum window, maximum sum subarray, and other sliding window problems. Understanding sliding window is essential for technical interviews.

Versatile Technique

Sliding window works for many problems: fixed-size subarrays, variable-size substrings, constraints on window, and problems requiring contiguous elements. It's a versatile technique that can be adapted to different problem types. Learning sliding window helps solve many coding problems efficiently.

Important: Sliding window matters because it provides O(n) time complexity (better than O(n²)), avoids recalculating overlapping elements, is a common interview topic, and is versatile for many problem types. Sliding window is one of the most important techniques for subarray/substring problems.

Frequently Asked Questions

What is the sliding window technique?

Sliding window technique uses two pointers to maintain a window (subarray/substring) that slides through an array or string. The window expands or contracts based on conditions, allowing efficient O(n) solutions for subarray/substring problems. Common types: fixed-size window (window size stays constant) and variable-size window (window size changes). Sliding window avoids recalculating overlapping elements.

How does sliding window technique work?

Sliding window works by: 1) Initialize left and right pointers, 2) Expand window by moving right pointer, 3) Contract window by moving left pointer when condition is met, 4) Process elements within window, 5) Continue until right pointer reaches end. Each element is added/removed from window once, giving O(n) time complexity. Window slides through array without recalculating overlapping parts.

When to use sliding window technique?

Use sliding window for: subarray/substring problems (longest substring with k distinct characters), problems with constraints (sum less than k, at most k elements), problems requiring contiguous subarrays, and when you can maintain window state efficiently. Sliding window is great for problems that ask about subarrays/substrings with specific properties.

What is the difference between fixed and variable sliding window?

Fixed sliding window: window size stays constant (e.g., find maximum sum of subarray of size k). Variable sliding window: window size changes based on conditions (e.g., find longest substring with at most k distinct characters). Fixed window moves both pointers together, variable window expands/contracts independently. Both use O(n) time complexity.

What is the time complexity of sliding window technique?

Sliding window technique has O(n) time complexity, where n is the size of the array or string. Each element is added to window once (right pointer) and removed once (left pointer), so each element is processed at most twice. Space complexity is O(k) where k is the window size (for hash map/set). Sliding window is one of the most efficient techniques for subarray/substring problems.