Lesson 3 � Intermediate

Sliding Window Pattern

Sliding window DSA ka ek bahut powerful pattern hai jo subarray aur substring problems ko O(n�) se O(n) mein convert karta hai. Ye pattern arrays aur strings dono pe kaam karta hai. Isko samajh lo toh bahut saare problems easy ho jayenge.

? 28 min✓ Intermediate✓ Arrays & Two Pointers

Sliding Window kya hai?

WHAT

Sliding window ek technique hai jismein hum array/string mein ek "window" (subarray) maintain karte hain jo ek position slide hoti rehti hai. Window ka size fixed ho sakta hai ya variable. Har step mein window ko rightward move karte hain aur naya element add karte hain, purana remove karte hain.

WHEN

Jab question mein "contiguous subarray" ya "substring" ki baat ho, jab maximum/minimum sum find karna ho k size ke window mein, jab koi pattern match karna ho string mein, ya jab longest/shortest subarray find karna ho � tab sliding window use karo.

WHERE

Maximum Sum Subarray of Size K, Longest Substring Without Repeating Characters, Minimum Window Substring, Anagram Occurrences � ye sab sliding window se solve hote hain.

Mental Model: Imagine karo tum ek train mein ho jo ek fixed length ki hai. Train stations pe rukti hai � jab naya station aata hai, piche ka station chhut jaata hai. Sliding window bhi aise hi kaam karta hai � naya element add hota hai, purana remove hota hai, aur window ek position aage badhti hai.

Fixed Size Window

Fixed window mein window ka size constant hota hai. Har step mein window ko ek position rightward move karo � naya element add karo, purana remove karo. Ye O(n) time mein hota hai kyunki har element sirf ek baar process hota hai.

# Maximum sum subarray of size k
def max_sum_subarray(arr, k):
 n = len(arr)
 if n < k:
 return -1
 
 # Pehle window ka sum nikalo
 window_sum = sum(arr[:k])
 max_sum = window_sum
 
 # Window ko slide karo
 for i in range(k, n):
 window_sum += arr[i] - arr[i-k] # Naya add, purana remove
 max_sum = max(max_sum, window_sum)
 
 return max_sum

arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]
print(max_sum_subarray(arr, 3)) # 24 (subarray: 3, 1, 20)

Key Insight: Har step mein hum sirf ek element add karte hain aur ek remove karte hain � isliye O(n) hota hai. Agar har baar sum dobara nikalte toh O(n*k) hota. Sliding window ka fayda ye hai ki hum previous computation reuse karte hain.

Variable Size Window

Variable window mein window ka size fix nahi hota. Hum condition ke hisaab se window bada ya chhota karte hain. Ye fixed window se thoda complex hai but bahut powerful hai.

# Longest substring with at most k distinct characters
def longest_substring_k_distinct(s, k):
 char_count = {}
 left = 0
 max_length = 0
 
 for right in range(len(s)):
 # Right character add karo
 char_count[s[right]] = char_count.get(s[right], 0) + 1
 
 # Jab distinct characters zyada ho jayein
 while len(char_count) > k:
 char_count[s[left]] -= 1
 if char_count[s[left]] == 0:
 del char_count[s[left]]
 left += 1
 
 max_length = max(max_length, right - left + 1)
 
 return max_length

print(longest_substring_k_distinct("eceba", 2)) # 3 ("ece")

Variable window mein two pointers use hote hain � left aur right. Right pointer window badhata hai, left pointer window chhota karta hai jab condition violate ho. Dono pointers aage badhte hain � isliye O(n) time hota hai.

Sliding Window ka Approach

Har sliding window problem ka approach same hota hai. Ye 4 steps yaad rakho:

# Step 1: Window variables initialize karo
left = 0
window_state = {} # ya window_sum, window_count etc.

# Step 2: Right pointer se window badhao
for right in range(len(arr)):
 # arr[right] ko window mein add karo
 
 # Step 3: Jab condition violate ho, left move karo
 while condition_violated():
 # arr[left] ko window se remove karo
 left += 1
 
 # Step 4: Answer update karo
 max_length = max(max_length, right - left + 1)

Pattern Recognition: Agar question mein "longest/shortest subarray" hai ya "at most k" ya "exactly k" jaisi condition hai � toh sliding window try karo. Pehle fixed window try karo, agar kaam na kare toh variable window try karo.

Common Examples

# Example 1: Count anagram occurrences
def count_anagrams(text, pattern):
 from collections import Counter
 
 p_count = Counter(pattern)
 w_count = Counter()
 k = len(pattern)
 result = 0
 
 for i in range(len(text)):
 # Add right character
 w_count[text[i]] += 1
 
 # Remove left character when window full
 if i >= k:
 if w_count[text[i-k]] == 1:
 del w_count[text[i-k]]
 else:
 w_count[text[i-k]] -= 1
 
 if w_count == p_count:
 result += 1
 
 return result

print(count_anagrams("forxxorfxdofr", "for")) # 3

# Example 2: Minimum window substring
def min_window(s, t):
 from collections import Counter
 
 need = Counter(t)
 missing = len(t)
 left = 0
 start, end = 0, float('inf')
 
 for right in range(len(s)):
 if need[s[right]] > 0:
 missing -= 1
 need[s[right]] -= 1
 
 while missing == 0:
 if right - left < end - start:
 start, end = left, right
 need[s[left]] += 1
 if need[s[left]] > 0:
 missing += 1
 left += 1
 
 return s[start:end+1] if end < float('inf') else ""

Try it: code khud likho

Exercise

Question: Given array [3, 1, 2, 7, 4, 2, 1, 1, 5] and k = 3, maximum sum subarray of size k nikalo. Answer mein sirf maximum sum daalo.

Question: String "abcabcbb" mein longest substring with all unique characters nikalo. Answer mein length daalo.

Common mistakes

Window size maintain nahi karna: Fixed window mein har step mein sirf ek element add aur ek remove karo. Do elements add karoge toh size badh jayega.
Left element remove karna bhool jaana: Variable window mein jab condition violate ho, left element ko window se remove karo. Nahi toh window galat hoga.
Prefix sum se confuse karna: Sliding window aur prefix sum alag hain. Sliding window tab use karo jab contiguous subarray chahiye with some condition. Prefix sum tab use karo jab range sum queries ho.
Edge cases skip karna: Window size > array size, empty array, sab elements same � ye sab test karo. Interview mein ye hota hai.

Lesson complete?

Sliding window samajh aa gaya✓ Ab Prefix Sum technique seekhte hain � ye subarray sum queries ko efficiently solve karta hai.