Vatsal.
Back to Notes

🧠 The Mental Logic: How to Spot It

Before you write a single line of code, you must identify if Sliding Window is the right tool. Use this mental checklist:

  1. Linear Data Structure: Is the input an Array, String, or Linked List?
  2. Contiguous Segment: Does the problem ask for a Subarray or Substring?
  3. Optimal/Specific Property: Does it ask for the Longest, Shortest, Maximum Sum, or a specific count (e.g., "contains K distinct characters")? If you answer YES to these, you are in Sliding Window territory.
The Fixed-Size Window Pattern

This is the foundational pattern. The problem specifies a window size k (e.g., "Find the maximum sum of k consecutive elements").

The Strategy: Instead of recalculating the sum/condition for every subarray (which is inefficient), you "slide" the window one step at a time.

  1. Initialize: Calculate the result for the first k elements.
  2. Slide: Move the window one step right.
  3. Update: Add the new element entering the window and remove the element leaving the window.

Senior-Level Template (Pseudo-code):

def fixed_sliding_window(arr, k):
    curr_sum = 0
    # 1. Build the first window
    for i in range(k):
        curr_sum += arr[i]
    
    max_sum = curr_sum
    
    # 2. Slide the window
    # Start from k because k elements are already processed
    for i in range(k, len(arr)):
        # Add the new element (right), subtract the old (left)
        curr_sum += arr[i] - arr[i - k] 
        max_sum = max(max_sum, curr_sum)
        
    return max_sum

Classic Problems: Maximum Sum Subarray of size K, Find All Anagrams in a String.

The Variable-Size Window Pattern (Flexible Window)

This is where interview questions get tricky. The window size is not fixed. It expands and contracts like a caterpillar based on constraints.

There are two major variations here:

A. Longest Window (Expansion Focus): Goal: Find the longest subarray satisfying a condition (e.g., "Longest substring with no repeating characters").

Technique:

  1. Expand: Move the right pointer to include elements.
  2. Violate: Stop expanding when the condition breaks (e.g., a duplicate char is found).
  3. Shrink: Move the left pointer just enough to make the window valid again.
  4. Record: Update your maximum length (right - left + 1).

Template:

def variable_longest_window(arr):
    left = 0
    right = 0
    max_len = 0
    seen = {} # HashMap or Frequency Array
    
    while right < len(arr):
        # 1. Add element at 'right' to window/map
        current_element = arr[right]
        seen[current_element] = seen.get(current_element, 0) + 1
        
        # 2. While condition is INVALID, shrink from left
        # Example condition: If duplicates exist, shrink
        while seen[current_element] > 1: # Replace with your specific condition
            left_element = arr[left]
            seen[left_element] -= 1
            if seen[left_element] == 0:
                del seen[left_element]
            left += 1
        
        # 3. Update answer (window is valid here)
        max_len = max(max_len, right - left + 1)
        right += 1
        
    return max_len

B. Shortest Window (Contraction Focus) Goal: Find the shortest subarray satisfying a condition (e.g., "Minimum Window Substring").

Technique:

  1. Expand: Move right until the window becomes valid (e.g., contains all required chars).
  2. Shrink: Once valid, try to squeeze the left pointer to make it as small as possible while remaining valid.
  3. Record: Update minimum length during the shrinking phase.
Senior-Level Techniques & "Secret Sauces"

To crack top-tier interviews, you need these specific optimizations and tricks found in our advanced notes.

🔧 The "At Most K" Trick

Sometimes finding "Exactly K" distinct characters is hard because you can't easily count "exactly" while sliding. The Trick: Calculate atMost(K) - atMost(K-1). • It is much easier to write a function that finds subarrays with at most K distinct items. You can then simply subtract the results to get "Exactly K".

🔧 Sliding Window with Auxiliary Data Structures

Sometimes simple variables (sum/count) aren't enough.

• Monotonic Queue (Deque): Used for Sliding Window Maximum problems. You maintain indices in a deque such that values are always decreasing. This allows you to find the max in O(1) time while sliding. • Hash Map / Frequency Array: Essential for string problems (e.g., "Longest Repeating Character Replacement"). Use an array int instead of a HashMap for O(1) space complexity regarding alphabet size.

🔧 Two-String Sliding Window

Used when comparing two strings (e.g., "Minimum Window Substring" or "Permutation in String"). • Technique: Create a frequency map of the target string. Expand the window on the source string and maintain a matchCount variable. When matchCount equals the distinct characters in the target, you have a valid window.

🏆 The "Must-Master" Problem List

To consider yourself a master, you must solve these specific problems listed in the guide:

  1. Longest Substring Without Repeating Characters (Variable Window - Expansion)
  2. Max Consecutive Ones III (Variable Window - Optimization)
  3. Fruit Into Baskets (Variable Window - Longest with K distinct)
  4. Minimum Window Substring (Variable Window - Contraction/Shortest)
  5. Sliding Window Maximum (Fixed Window + Deque)
  6. Subarrays with K Different Integers (The "At Most K" Trick)

Final Advice for the Interview: Always start by defining your left and right pointers. Explain to the interviewer: "I will use a sliding window approach to convert the nested loops into a single linear pass, reducing the time complexity from O(N^2) to O(N)."