Concept Notes — Two Pointers ও Sliding Window (ভেতর থেকে বোঝা)¶
এই level-এর দুই নায়ক — two pointers আর sliding window — আসলে একই পরিবারের। দুটোরই মূলমন্ত্র: একবার বাদ দেওয়া জিনিসে আর কখনো ফিরব না। ফেরার দরকার নেই — এটা প্রমাণ করতে পারলেই O(n²) ভেঙে O(n)।
1. Opposite two pointers — দুই দিক থেকে চাপা¶
Sorted array-তে এমন দুটো সংখ্যা খুঁজছ যাদের sum = target। Brute force: সব জোড়া — O(n²)। চালাক পথ: এক আঙুল একদম বাঁয়ে (l), আরেকটা একদম ডানে (r)। এবার দেখো:
a[l] + a[r]বেশি হলে → sum কমাতে হবে → বড় দিকটা ছাড়ো →r -= 1- কম হলে → sum বাড়াতে হবে → ছোট দিকটা ছাড়ো →
l += 1 - সমান হলে → পেয়ে গেছ!
def two_sum_sorted(a, target):
l, r = 0, len(a) - 1
while l < r:
s = a[l] + a[r]
if s == target:
return l, r
if s > target:
r -= 1
else:
l += 1
return None
print(two_sum_sorted([1, 3, 4, 6, 9], 10)) # (1, 3) → 3 + 6? না... দেখি dry run-এ
Mini dry run (target = 10):
খুব তাড়াতাড়ি মিলে গেল — আরেকটা চালাই (target = 7):
কেন r-- নিরাপদ? যখন a[l] + a[r] > target, তখন a[r]-এর সাথে a[l] জুটি হয় না — কিন্তু a[l]-এর ডানের সবাই তো a[l]-এর চেয়েও বড়, তাদের সাথেও a[r]-এর sum আরো বেশি হবে। মানে a[r]-এর কোনো জুটিই আর সম্ভব না (l-এর বাঁয়ে কিছু নেই) — তাকে নিশ্চিন্তে বাদ। প্রতি step-এ একটা element চিরতরে বাদ → বড়জোর n step → O(n)। এই "একজনকে চিরতরে বাদ দেওয়ার প্রমাণ"-ই two pointers-এর হৃদয়।
2. Same-direction pointers — পেছনেরটা সামনেরটাকে তাড়া করে¶
"Difference = K এমন জোড়া খোঁজো" — এবার দুই প্রান্ত থেকে চাপা চলে না (difference-এর সাথে দুই প্রান্তের সম্পর্ক অত পরিষ্কার না)। বরং দুটো pointer একই দিকে দৌড়াক: j সামনে এগোয়, i পেছন থেকে ধাওয়া করে যেন a[j] - a[i] বেশি বড় না হয়ে যায়।
def pair_with_diff_k(a, k): # a sorted, k > 0
i, j = 0, 1
while j < len(a):
d = a[j] - a[i]
if d == k and i != j:
return i, j
if d < k:
j += 1 # ফারাক ছোট → সামনেরটা এগোক
else:
i += 1 # ফারাক বড় → পেছনেরটা এগিয়ে আসুক
if i == j: j += 1
return None
Mini dry run (a = [1, 3, 5, 9], k = 4):
লক্ষ করো দুজনেই শুধু ডানে যায়, কেউ পিছায় না — তাই মোট move ≤ 2n → O(n)। Opposite আর same-direction — দুটো আলাদা নাচ, কিন্তু সুর এক: প্রতি step-এ অগ্রগতি, ফেরা নেই।
3. 3Sum — একজনকে বসিয়ে বাকি দুজনে পুরোনো খেলা¶
তিনটা সংখ্যার sum = 0? তিনটা nested loop = O(n³)। কিন্তু একটা সংখ্যা a[i] fix করে ফেললে বাকিটা হয়ে যায় "দুটো সংখ্যা যাদের sum = -a[i]" — সেটা তো section 1-এই পারি! Fix-এর জন্য O(n), প্রতিটার ভেতরে two pointers O(n) → মোট O(n²)।
def three_sum(a):
a.sort()
res = []
for i in range(len(a) - 2):
if i > 0 and a[i] == a[i - 1]: # একই fix আবার না
continue
l, r = i + 1, len(a) - 1
while l < r:
s = a[i] + a[l] + a[r]
if s == 0:
res.append([a[i], a[l], a[r]])
l += 1; r -= 1
while l < r and a[l] == a[l - 1]: l += 1 # duplicate পার হও
elif s < 0: l += 1
else: r -= 1
return res
Duplicate skip-এর দুটো জায়গা খেয়াল করো — fix-এ একবার, match-এর পরে pointer-এ একবার। এগুলো বাদ দিলে [-1, -1, 2] দুবার আসবে। এই "এক ধাপ fix + ভেতরে সস্তা খোঁজ" pattern-টা 3Sum-এর বাইরেও বহু জায়গায় ফেরে।
4. Container With Most Water — ছোট দেয়াল সরাও (প্রমাণসহ)¶
দুটো খাড়া রেখা + x-অক্ষ = পাত্র; পানি ধরবে min(height[l], height[r]) × (r - l)। দুই প্রান্ত থেকে শুরু করো, প্রতি step-এ ছোট দেয়ালটা ভেতরে সরাও।
কেন ছোটটা? ধরো height[l] < height[r]। যদি r সরাও: width কমল, আর উচ্চতা? এখনো বড়জোর height[l]-ই (ছোট দেয়ালই সীমা) — মানে নিশ্চিত লস বা সমান। কিন্তু l সরালে width কমে ঠিকই, উচ্চতা বাড়ার সম্ভাবনা খোলে। অর্থাৎ ছোট দেয়ালকে রেখে দিয়ে আর কোনো ভালো পাত্র সম্ভব না — তাকেই ছাড়ো:
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
l=0 (h=1), r=8 (h=7): area = min(1,7) × 8 = 8 → ছোট 1, l++
l=1 (h=8), r=8 (h=7): area = min(8,7) × 7 = 49 → ছোট 7, r--
... best = 49
Interview-তে শুধু code না — এই "কেন ছোটটা সরালে কিছু হারাই না" প্রমাণটা বলতে পারাই আসল নম্বর।
5. Sliding window = শুঁয়োপোকা¶
এবার window: array-র একটা টানা টুকরো [l..r] যেটা ডানে হাঁটে। দুই জাত:
Fixed window (দৈর্ঘ্য k): এক ঘর ডানে সরা মানে — ডানে একটা ঢোকে, বাঁয়ে একটা বেরোয়। পুরো sum আবার গোনার দরকার নেই:
def max_window_sum(a, k):
s = sum(a[:k])
best = s
for r in range(k, len(a)):
s += a[r] - a[r - k] # নতুনটা যোগ, পুরোনোটা বিয়োগ
best = max(best, s)
return best
Dry run (a = [2, 1, 5, 1, 3], k = 3): শুরুতে s = 8; r=3: s = 8 + 1 - 2 = 7; r=4: s = 7 + 3 - 1 = 9 → best 9 ✓
Variable window (শুঁয়োপোকা): ডান প্রান্ত প্রতি step-এ এক ঘর বড় হয় (মাথা এগোয়); যখনই window-র শর্ত (invariant) ভাঙে, বাঁ প্রান্ত গুটিয়ে এসে শর্ত ফেরায় (লেজ টেনে আনে)। Template:
def smallest_window_with_sum(a, target): # a-তে সব positive
l, s, best = 0, 0, float('inf')
for r in range(len(a)):
s += a[r] # মাথা এগোলো
while s >= target: # শর্ত পূরণ → যতটা পারো গোটাও
best = min(best, r - l + 1)
s -= a[l]
l += 1 # লেজ গুটালো
return best if best != float('inf') else 0
Mini dry run (a = [2, 3, 1, 2, 4, 3], target = 7):
r=0: s=2 r=1: s=5 r=2: s=6
r=3: s=8 ≥ 7 → best=4 (l=0..3); s=6, l=1
r=4: s=10 ≥ 7 → best=4; s=7, l=2 → এখনো ≥7 → best=3 (l=2..4); s=6, l=3
r=5: s=9 ≥ 7 → best=3; s=7, l=4 → ≥7 → best=2 (l=4..5)! s=3, l=5
উত্তর: 2 ([4, 3]) ✓
O(n) কেন? r মোট n বার এগোয়; l-ও জীবনে বড়জোর n বার এগোয় (পিছায় না কখনো)। ভেতরের while ভয়ংকর দেখালেও মোট কাজ ≤ 2n। এটার নাম amortized analysis — প্রতি step-এর খরচ না গুনে মোট খরচ গোনা।
সাবধানতা: এই যুক্তি দাঁড়িয়ে আছে "বাঁ থেকে বাদ দিলে sum কমে"-র উপর — negative number থাকলে সেটা মিথ্যা, window ভেঙে পড়ে। তখন Level 5-এর prefix + hash map।
6. Window-র ভেতরে গোনা — distinct ≤ K¶
Invariant সবসময় sum না — হতে পারে "window-তে distinct element বড়জোর K টা"। তখন window-র ভেতরের হিসাবটা একটা count map:
def longest_at_most_k_distinct(a, k):
from collections import defaultdict
cnt = defaultdict(int)
l, best = 0, 0
for r in range(len(a)):
cnt[a[r]] += 1
while len(cnt) > k: # শর্ত ভাঙল
cnt[a[l]] -= 1
if cnt[a[l]] == 0:
del cnt[a[l]] # 0 হলে মুছতেই হবে — নইলে len ভুল!
l += 1
best = max(best, r - l + 1)
return best
এটাই Fruit Into Baskets (k = 2)। কাঠামো section 5-এর হুবহু — শুধু "s" এর জায়গায় "cnt", আর শর্তটা ভিন্ন। Template এক, invariant বদলায় — এই উপলব্ধিটাই sliding window-তে দক্ষতা।
7. গোনার নিয়ম: r-এ শেষ হওয়া valid subarray = r − l + 1¶
"কয়টা subarray valid?" ধাঁচের প্রশ্নে একটা মোক্ষম নিয়ম। ধরো window [l..r] valid (যেমন product < K) এবং l হলো সবচেয়ে বাঁয়ের valid শুরু। তাহলে r-এ শেষ হওয়া valid subarray গুলো হলো [l..r], [l+1..r], ..., [r..r] — মোট r − l + 1 টা। (শুরু আরো বাঁয়ে নিলে invalid, আর ভেতরের সবগুলো valid — কারণ ছোট window তো আরো নিরাপদ।) প্রতিটা r-এ এই সংখ্যাটা যোগ করো:
def count_product_less_than_k(a, k):
if k <= 1: return 0
prod, l, ans = 1, 0, 0
for r in range(len(a)):
prod *= a[r]
while prod >= k:
prod //= a[l]
l += 1
ans += r - l + 1 # r-এ শেষ হওয়া সবগুলো
return ans
Dry run (a = [10, 5, 2, 6], k = 100):
r=0: prod=10 <100 → ans += 1 (l=0) মোট 1
r=1: prod=50 <100 → ans += 2 (l=0) মোট 3
r=2: prod=100 ≥100 → prod=10, l=1 → ans += 2 মোট 5
r=3: prod=60 <100 → ans += 3 (l=1) মোট 8 ✓
8. "Exactly K" trick — দুটো সহজের বিয়োগ¶
"ঠিক K টা distinct" সরাসরি window দিয়ে কঠিন — কারণ বাঁ প্রান্তের "সবচেয়ে ভালো জায়গা" একটামাত্র না। কিন্তু "বড়জোর K টা distinct" তো section 6/7 দিয়ে সোজা! আর লক্ষ করো:
exactly(K) = atMost(K) − atMost(K − 1)
ছবি: atMost(3) এর দল: [distinct=1] [distinct=2] [distinct=3]
atMost(2) এর দল: [distinct=1] [distinct=2]
বিয়োগ দিলে থাকে: [distinct=3] ← এটাই exactly 3
যেখানে at_most_k হলো section 6-এর window + section 7-এর r - l + 1 গোনা। একটা কঠিন প্রশ্ন = দুটো সহজ প্রশ্নের বিয়োগ — এই decomposition-চিন্তা বহু জায়গায় কাজে লাগবে ("ঠিক K" যেখানেই দেখো, "বড়জোর K-এর বিয়োগ" মাথায় আসুক)।
এক নজরে cheat sheet¶
opposite pointers : sorted; sum বড় → r--, ছোট → l++; প্রমাণ: বাদ পড়া প্রান্তের কোনো জুটি নেই
same-direction : i, j দুজনেই শুধু ডানে; diff ছোট → j++, বড় → i++
3Sum : sort + fix i + ভেতরে two pointers; duplicate দুই স্তরে skip
container : ছোট দেয়াল সরাও — বড়টা রেখে লাভের সম্ভাবনা শূন্য
fixed window : s += a[r] - a[r-k]
variable window : for r: ঢোকাও → while শর্ত-ভাঙা: l থেকে বের করো → answer update
distinct গোনা : count map; 0 হলে del
valid count : প্রতি r-এ ans += r - l + 1
exactly K : atMost(K) - atMost(K-1)
window-র সীমা : negative এলে monotonicity ভাঙে → prefix + hash map
প্রতিটা লাইনের পেছনে একটা চলমান ছবি আছে — চাপা পড়া দুই আঙুল, ধাওয়া, শুঁয়োপোকা। Code আটকে গেলে ছবিটা মনে মনে চালাও — পরের লাইনটা ছবিই বলে দেবে।