Sliding Window Pattern Questions 2026: 20+ Problems [Solved]

Last Updated: June 2026

Why Sliding Window is a Must-Know Pattern

Candidates report sliding window as one of the top five most-asked array patterns across Amazon, Microsoft, and service company NQT rounds. Based on public preparation resources and candidate-reported interview threads from 2025 to 2026, this pattern appears in roughly 15-20% of array and string coding questions at product and service companies alike. It converts brute-force O(n^2) or O(n^3) solutions into O(n) by maintaining a window that slides across the input without re-processing elements already seen.

If you cannot identify a sliding window problem on sight, you will write a nested loop and either time out or lose points for suboptimal complexity. This guide teaches pattern recognition first, then walks through 20+ solved problems.

The Core Idea

Array:  [a, b, c, d, e, f, g]
         [----window----]
              slide right -->
              [----window----]

Instead of re-summing the window from scratch each time, you:

1. Add the incoming element (right boundary moves right)
2. Remove the outgoing element (left boundary moves right when condition breaks)

This gives O(1) per step instead of O(k) per step.

Fixed-Size vs Variable-Size Windows

Fixed-Window Template

def fixed_window(arr, k):
    n = len(arr)
    if n < k:
        return -1

    # Build initial window
    window_sum = sum(arr[:k])
    result = window_sum

    # Slide
    for i in range(k, n):
        window_sum += arr[i]        # add incoming
        window_sum -= arr[i - k]    # remove outgoing
        result = max(result, window_sum)

    return result
# Time: O(n)  Space: O(1)

Variable-Window Template

def variable_window(arr, target):
    left = 0
    current = 0
    result = float('inf')

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

        while current >= target:       # condition met, try to shrink
            result = min(result, right - left + 1)
            current -= arr[left]
            left += 1

    return result if result != float('inf') else 0
# Time: O(n)  Space: O(1)

Practice Questions with Solutions

Problem 1: Maximum Sum Subarray of Size K (EASY)

Asked at: TCS, Wipro, Infosys, Cognizant

Problem: Given an array and integer k, find the maximum sum of any contiguous subarray of size k.

Approach: Fixed-size window. Build window of k, slide right.

def max_sum_subarray_k(arr, k):
    """
    Fixed window of size k.
    Time: O(n)  Space: O(1)
    """
    n = len(arr)
    if n < k:
        return -1

    window_sum = sum(arr[:k])
    max_sum = window_sum

    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)

    return max_sum

# Example
print(max_sum_subarray_k([2, 1, 5, 1, 3, 2], 3))  # Output: 9 (5+1+3)

Complexity: Time O(n), Space O(1)

Problem 2: Longest Substring Without Repeating Characters (MEDIUM)

Asked at: Amazon, Microsoft, Google, Adobe, Flipkart

Problem: Find the length of the longest substring with all unique characters.

Approach: Variable window. Expand right, shrink left when a duplicate enters.

def length_of_longest_substring(s):
    """
    Variable window with hash set.
    Time: O(n)  Space: O(min(n, alphabet))
    """
    char_set = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)

    return max_len

# Example
print(length_of_longest_substring("abcabcbb"))  # Output: 3 ("abc")
print(length_of_longest_substring("pwwkew"))    # Output: 3 ("wke")

Complexity: Time O(n), Space O(k) where k = alphabet size

Problem 3: Minimum Size Subarray Sum (MEDIUM)

Asked at: Amazon, Uber, Walmart Labs

Problem: Find the minimum length of a contiguous subarray whose sum is at least target. Return 0 if none.

def min_subarray_len(target, nums):
    """
    Variable window - shrink when sum >= target.
    Time: O(n)  Space: O(1)
    """
    left = 0
    current_sum = 0
    min_len = float('inf')

    for right in range(len(nums)):
        current_sum += nums[right]

        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= nums[left]
            left += 1

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

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

Complexity: Time O(n), Space O(1)

Problem 4: Longest Substring with At Most K Distinct Characters (MEDIUM)

Asked at: Google, Amazon, Goldman Sachs

Problem: Find the longest substring containing at most k distinct characters.

def longest_k_distinct(s, k):
    """
    Variable window with frequency map.
    Time: O(n)  Space: O(k)
    """
    from collections import defaultdict

    freq = defaultdict(int)
    left = 0
    max_len = 0

    for right in range(len(s)):
        freq[s[right]] += 1

        while len(freq) > k:
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1

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

    return max_len

# Example
print(longest_k_distinct("eceba", 2))   # Output: 3 ("ece")
print(longest_k_distinct("aa", 1))      # Output: 2 ("aa")

Complexity: Time O(n), Space O(k)

Problem 5: Permutation in String (MEDIUM)

Asked at: Microsoft, Amazon, Adobe

Problem: Given strings s1 and s2, return true if any permutation of s1 exists as a substring of s2.

def check_inclusion(s1, s2):
    """
    Fixed window of size len(s1). Compare frequency arrays.
    Time: O(n)  Space: O(1) - only 26 characters
    """
    if len(s1) > len(s2):
        return False

    need = [0] * 26
    window = [0] * 26

    for c in s1:
        need[ord(c) - ord('a')] += 1

    k = len(s1)

    for i in range(k):
        window[ord(s2[i]) - ord('a')] += 1

    if need == window:
        return True

    for i in range(k, len(s2)):
        window[ord(s2[i]) - ord('a')] += 1
        window[ord(s2[i - k]) - ord('a')] -= 1
        if need == window:
            return True

    return False

# Example
print(check_inclusion("ab", "eidbaooo"))   # True  ("ba" at index 3)
print(check_inclusion("ab", "eidboaoo"))   # False

Complexity: Time O(n), Space O(1)

Problem 6: Find All Anagrams in String (MEDIUM)

Asked at: Amazon, Facebook, Microsoft

Problem: Find all starting indices where an anagram of pattern p exists in string s.

def find_anagrams(s, p):
    """
    Fixed window - same idea as permutation check but collect positions.
    Time: O(n)  Space: O(1)
    """
    result = []
    if len(p) > len(s):
        return result

    p_count = [0] * 26
    s_count = [0] * 26
    k = len(p)

    for c in p:
        p_count[ord(c) - ord('a')] += 1

    for i in range(k):
        s_count[ord(s[i]) - ord('a')] += 1

    if s_count == p_count:
        result.append(0)

    for i in range(k, len(s)):
        s_count[ord(s[i]) - ord('a')] += 1
        s_count[ord(s[i - k]) - ord('a')] -= 1
        if s_count == p_count:
            result.append(i - k + 1)

    return result

# Example
print(find_anagrams("cbaebabacd", "abc"))  # [0, 6]

Complexity: Time O(n), Space O(1)

Problem 7: Maximum Average Subarray I (EASY)

Asked at: Infosys, Wipro, TCS NQT

Problem: Find the contiguous subarray of length k that has the maximum average value.

def find_max_average(nums, k):
    """
    Fixed window. Track sum, compute average at end.
    Time: O(n)  Space: O(1)
    """
    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 / k

# Example
print(find_max_average([1, 12, -5, -6, 50, 3], 4))  # 12.75

Complexity: Time O(n), Space O(1)

Problem 8: Fruits Into Baskets (MEDIUM)

Asked at: Google, Amazon (variant of at-most-2-distinct)

Problem: You have two baskets. Each basket holds one type of fruit. Moving left to right, collect maximum fruits. Return max fruits collectible (longest subarray with at most 2 distinct values).

def total_fruit(fruits):
    """
    Variable window: longest subarray with at most 2 distinct elements.
    Time: O(n)  Space: O(1) - at most 2 keys in map
    """
    from collections import defaultdict

    basket = defaultdict(int)
    left = 0
    max_fruits = 0

    for right in range(len(fruits)):
        basket[fruits[right]] += 1

        while len(basket) > 2:
            basket[fruits[left]] -= 1
            if basket[fruits[left]] == 0:
                del basket[fruits[left]]
            left += 1

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

    return max_fruits

# Example
print(total_fruit([1, 2, 1]))           # 3
print(total_fruit([0, 1, 2, 2]))        # 3
print(total_fruit([1, 2, 3, 2, 2]))     # 4 ([2,3,2,2] or [2,2,2])

Complexity: Time O(n), Space O(1)

Problem 9: Minimum Window Substring (HARD)

Asked at: Google, Amazon, Microsoft, Uber - classic hard sliding window

Problem: Find the minimum window in string s containing all characters of string t.

def min_window(s, t):
    """
    Variable window with character frequency tracking.
    Time: O(n + m)  Space: O(n + m)
    """
    from collections import Counter

    if not t or not s:
        return ""

    need = Counter(t)
    have = {}
    formed = 0
    required = len(need)

    left = 0
    min_len = float('inf')
    min_left = 0

    for right in range(len(s)):
        c = s[right]
        have[c] = have.get(c, 0) + 1

        if c in need and have[c] == need[c]:
            formed += 1

        while formed == required:
            # Update result
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_left = left

            # Shrink window
            left_char = s[left]
            have[left_char] -= 1
            if left_char in need and have[left_char] < need[left_char]:
                formed -= 1
            left += 1

    return s[min_left:min_left + min_len] if min_len != float('inf') else ""

# Example
print(min_window("ADOBECODEBANC", "ABC"))   # "BANC"
print(min_window("a", "a"))                 # "a"

Complexity: Time O(n + m), Space O(n + m)

Problem 10: Longest Repeating Character Replacement (MEDIUM)

Asked at: Amazon, Microsoft, Google

Problem: Replace at most k characters to make the longest substring with all same characters.

def character_replacement(s, k):
    """
    Variable window. Key insight: window is valid if
    (window_size - max_freq_char) <= k
    Time: O(n)  Space: O(26) = O(1)
    """
    count = {}
    left = 0
    max_freq = 0
    max_len = 0

    for right in range(len(s)):
        count[s[right]] = count.get(s[right], 0) + 1
        max_freq = max(max_freq, count[s[right]])

        # If replacements needed > k, shrink window
        while (right - left + 1) - max_freq > k:
            count[s[left]] -= 1
            left += 1

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

    return max_len

# Example
print(character_replacement("ABAB", 2))   # 4 (replace both B's or both A's)
print(character_replacement("AABABBA", 1)) # 4

Complexity: Time O(n), Space O(1)

Problem 11: Subarray Product Less Than K (MEDIUM)

Asked at: Amazon, Facebook

Problem: Count the number of contiguous subarrays where the product of all elements is less than k.

def num_subarray_product_less_than_k(nums, k):
    """
    Variable window. Each valid right boundary adds (right - left + 1) subarrays.
    Time: O(n)  Space: O(1)
    """
    if k <= 1:
        return 0

    left = 0
    product = 1
    count = 0

    for right in range(len(nums)):
        product *= nums[right]

        while product >= k:
            product //= nums[left]
            left += 1

        count += right - left + 1

    return count

# Example
print(num_subarray_product_less_than_k([10, 5, 2, 6], 100))  # 8

Complexity: Time O(n), Space O(1)

Problem 12: Count Occurrences of Anagrams (MEDIUM)

Asked at: Amazon, Samsung, Paytm

Problem: Given a text and pattern, find the count of occurrences of anagrams of pattern in text.

def count_anagram_occurrences(text, pattern):
    """
    Fixed window of pattern length. Compare sorted chars.
    Optimized: use frequency arrays.
    Time: O(n)  Space: O(1)
    """
    k = len(pattern)
    n = len(text)

    if k > n:
        return 0

    p_freq = [0] * 26
    w_freq = [0] * 26
    count = 0

    for c in pattern:
        p_freq[ord(c) - ord('a')] += 1

    for i in range(k):
        w_freq[ord(text[i]) - ord('a')] += 1

    if p_freq == w_freq:
        count += 1

    for i in range(k, n):
        w_freq[ord(text[i]) - ord('a')] += 1
        w_freq[ord(text[i - k]) - ord('a')] -= 1
        if p_freq == w_freq:
            count += 1

    return count

# Example
print(count_anagram_occurrences("aabaabaa", "aaba"))  # 4

Complexity: Time O(n), Space O(1)

Problem 13: Sliding Window Maximum (HARD)

Asked at: Google, Amazon, Microsoft - this is a hard variant requiring deque

Problem: Given array and window size k, return the maximum of each window as it slides.

from collections import deque

def max_sliding_window(nums, k):
    """
    Use a monotonic deque storing indices.
    Deque front = index of max in current window.
    Time: O(n)  Space: O(k)
    """
    dq = deque()
    result = []

    for i in range(len(nums)):
        # Remove indices outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove smaller elements from back
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        dq.append(i)

        # Window is fully formed
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

# Example
print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# Output: [3, 3, 5, 5, 6, 7]

Complexity: Time O(n), Space O(k)

Problem 14: Number of Subarrays with Bounded Maximum (MEDIUM)

Asked at: Amazon, Google

Problem: Count subarrays where max element is between left and right bounds (inclusive).

def num_subarray_bounded_max(nums, left, right):
    """
    Count subarrays with max in [left, right].
    = subarrays with max <= right - subarrays with max <= left-1
    Time: O(n)  Space: O(1)
    """
    def count_at_most(bound):
        count = 0
        cur = 0
        for num in nums:
            cur = cur + 1 if num <= bound else 0
            count += cur
        return count

    return count_at_most(right) - count_at_most(left - 1)

# Example
print(num_subarray_bounded_max([2, 1, 4, 3], 2, 3))  # 3

Complexity: Time O(n), Space O(1)

Pattern Recognition Guide

Use this decision tree when you see a new problem:

Is the problem about a CONTIGUOUS subarray or substring?
    NO  → sliding window probably not the right pattern
    YES → continue

Does it ask for FIXED length or VARIABLE length?
    FIXED (size k given)     → Fixed window template
    VARIABLE (find min/max)  → Variable window template

What constraint drives the window?
    Sum >= target            → Shrink when sum >= target
    At most k distinct       → Shrink when distinct count > k
    Character frequency      → Track counts, shrink when invalid
    All characters present   → formed/required count trick

Complexity Quick Reference

Company Frequency

Common Mistakes to Avoid

1. Forgetting to shrink the window: The while loop to shrink is as important as the expansion.
2. Off-by-one in window size: Window size is right - left + 1, not right - left.
3. Not handling empty input: Always check edge cases before the main loop.
4. Using O(k) comparison for fixed windows: Use frequency arrays instead of sorting.
5. Nested loops instead of amortized sliding: Each element enters and exits the window at most once; total work is O(n).

Related Articles

• Two Pointers Pattern Questions 2026
• Prefix Sum Questions 2026
• Arrays Questions Placement
• Dynamic Programming Patterns 2026
• Must-Do Coding Questions