Level 6 — Two Pointers ও Sliding Window (দুটো আঙুল, একটা জানালা)

আগের level-এ শিখেছ আগে থেকে হিসাব করে রাখা। এই level-এ শিখবে চলতে চলতে হিসাব করা — array-র উপর দুটো আঙুল রেখে এমনভাবে নাড়াবে যে প্রতিটা নাড়াচাড়া search space ছোট করে। O(n²)-এর nested loop ভেঙে O(n) — শুধু এই বুদ্ধিতে interview-র এক বিশাল অংশ জেতা যায়।

এই level এ কী শিখবে?

মূল idea গুলো:

• Opposite two pointers — sorted array-তে দুই প্রান্ত থেকে চাপা: sum বেশি হলে right কমাও, কম হলে left বাড়াও; প্রতি step-এ search space নিশ্চিতভাবে ছোট
• Same-direction pointers — difference খোঁজার মতো problem-এ দুটো pointer একই দিকে দৌড়ায়, কেউ কাউকে পেরোয় না
• Fix + two pointers — 3Sum: একটা element ঠিক করে বাকি দুটোতে two pointers — O(n³) থেকে O(n²)
• প্রমাণসহ greedy move — Container With Most Water: ছোট দেয়ালটা সরাও, আর কেন বড়টা সরালে লাভ নেই তার যুক্তি
• Fixed sliding window — k দৈর্ঘ্যের জানালা ডানে সরে: নতুন element যোগ, পুরোনোটা বাদ
• Variable sliding window (শুঁয়োপোকা) — ডান প্রান্ত বড় হয়, invariant ভাঙলে বাঁ প্রান্ত গুটিয়ে আসে
• Window invariant — "window-র sum ≤ K" বা "distinct ≤ K" — কোন শর্ত ধরে রাখছ সেটা পরিষ্কার করা
• "exactly K" trick — exactly K = atMost(K) − atMost(K−1); কঠিন প্রশ্নকে দুটো সহজ প্রশ্নে ভাঙা
• Valid subarray গোনা — r-এ শেষ হওয়া valid subarray সংখ্যা = r − l + 1

কেন এই level দরকার?

Competitive programming (CP) এ: CSES-এর Sorting and Searching section-এর বড় অংশ two pointers; Codeforces-এ "two pointers" নিজেই একটা official tag। যেখানে monotonicity আছে সেখানে nested loop ভাঙার প্রথম অস্ত্র এটাই।

Interview এ: Two Sum II, 3Sum, Container With Most Water, Minimum Size Subarray Sum, Fruit Into Baskets — এগুলো common interview pattern; sliding window হলো interview-র সবচেয়ে বেশি জিজ্ঞেস করা array technique গুলোর একটা। Pattern-টা একবার শরীরে ঢুকলে নতুন variation দেখেও হাত কাঁপে না।

পরের ধাপে: string-এর substring problem (anagram, longest without repeat) সব sliding window; monotonic deque দিয়ে window max; আর Level 7-এর binary search-ও আসলে "search space কমানো"-র আরেক রূপ।

Prerequisites

• Level 5: Prefix, Difference, Contribution — বিশেষ করে 073 (Subarray Sum Equals K); ওটার hash map পথ আর এখানকার window পথ — কখন কোনটা, এই তুলনাটা দামি
• Sorted array-র ধারণা — sorting নিজে এখানে শেখানো হবে না, শুধু ব্যবহার হবে
• Python dict/Counter basics — distinct গোনার problem-এ লাগবে

Learning goals (checklist)

এই level শেষে নিজেকে জিজ্ঞেস করো:

• [ ] Opposite pointers-এ "sum বড় হলে right-- কেন নিরাপদ" — যুক্তিটা বলতে পারি, মুখস্থ না
• [ ] Two pointers কেন O(n) — "প্রতি step-এ কেউ না কেউ এগোয়, মোট n বার" argument-টা দিতে পারি
• [ ] 3Sum-এ duplicate skip করার নিয়মগুলো জানি (fix-ও skip, pointer-ও skip)
• [ ] Container With Most Water-এ ছোট দেয়াল সরানোর প্রমাণ নিজের ভাষায় দিতে পারি
• [ ] Fixed window-তে "একটা ঢোকে, একটা বেরোয়" — recompute ছাড়া sum ঠিক রাখতে পারি
• [ ] Variable window-র template (for r: ঢোকাও; while invariant ভাঙা: l থেকে বের করো) না দেখে লিখতে পারি
• [ ] কেন while loop-এ l কখনো r-কে পেরিয়ে অসীম ঘোরে না — বুঝি
• [ ] "exactly K = atMost(K) − atMost(K−1)" — কেন কাজ করে, ছবি এঁকে বলতে পারি
• [ ] "r-এ শেষ হওয়া valid subarray = r − l + 1" — এই গোনার নিয়মটা ব্যাখ্যা করতে পারি
• [ ] কোন problem-এ window চলে আর কোনটায় চলে না (negative number এলে কী হয়) — পার্থক্য ধরতে পারি

Problem list

মোট 10টা problem — 2টা Easy, 7টা Medium, 1টা Hard।

Easy

#	Problem	Pattern	Source
081	Two Sum Sorted	opposite pointers	LeetCode Two Sum II — https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/, CSES Sum of Two Values — https://cses.fi/problemset/task/1640
085	Sliding Window Sum	fixed window	Classic exercise

Medium

#	Problem	Pattern	Source
082	Pair with Difference K	same-direction pointers	LeetCode K-diff Pairs — https://leetcode.com/problems/k-diff-pairs-in-an-array/
083	Three Sum	fix + two pointers	LeetCode 3Sum — https://leetcode.com/problems/3sum/
084	Container With Most Water	move shorter wall	LeetCode — https://leetcode.com/problems/container-with-most-water/
086	Longest Subarray with Sum K (Positive)	grow/shrink window	Classic exercise
087	Minimum Size Subarray Sum	shrinkable window	LeetCode — https://leetcode.com/problems/minimum-size-subarray-sum/
088	Count Subarrays with At Most K Distinct	window + count map	LeetCode Fruit Into Baskets (K=2 version) — https://leetcode.com/problems/fruit-into-baskets/
090	Number of Subarrays with Product Less Than K	window count r−l+1	LeetCode Subarray Product Less Than K — https://leetcode.com/problems/subarray-product-less-than-k/

Hard

#	Problem	Pattern	Source
089	Count Subarrays with Exactly K Distinct	atMost(K)−atMost(K−1)	LeetCode Subarrays with K Different Integers — https://leetcode.com/problems/subarrays-with-k-different-integers/

পুরো tracker table (status সহ) আছে problems/README.md-তে।

Recommended order

1. 081 — opposite pointers-এর জন্ম এখানে; "কেন একটা move নিরাপদ" যুক্তিটা এখানেই শিখে নাও
2. 082 — এবার pointer দুটো একই দিকে; opposite-এর সাথে পার্থক্যটা অনুভব করো
3. 083 — fix + two pointers; duplicate handling-এর কড়া অনুশীলন
4. 084 — greedy move যার পেছনে প্রমাণ আছে; এটা interview-র প্রিয় "কেন?" প্রশ্ন
5. 085 — window-র হাতেখড়ি: fixed দৈর্ঘ্য, ঢোকা-বেরোনোর হিসাব
6. 086 → 087 — variable window: আগে longest (বড় করো), পরে minimum (ছোট করো) — দুই দিকের অনুশীলন
7. 088 — window-র ভেতরে count map; "at most K distinct" invariant
8. 090 — গোনার নিয়ম r − l + 1 হাতে-কলমে
9. 089 — সবশেষে atMost-এর বিয়োগ trick; 088 আর 090 দুটোই লাগবে

Common mistakes (সাধারণ ভুল)

1. Unsorted array-তে opposite pointers চালানো — "sum বড় তাই right--" যুক্তিটা দাঁড়িয়েই আছে sorted-এর উপর। Sort করতে ভুলো না (আর sort করলে original index হারায় — Two Sum II index চাইলে সাবধান)।
2. 3Sum-এ duplicate skip না করা — একই triple বারবার আসে। Fix করা element আগেরটার সমান হলে skip, আর match পাওয়ার পরেও দুই pointer-কে duplicate পেরিয়ে নিতে হয়।
3. Window shrink-এ if লেখা, while না — একটা element ঢোকার পর invariant ঠিক করতে একাধিক বার বাঁ থেকে বের করা লাগতে পারে। if দিলে window আধভাঙা থেকে যায়।
4. বাঁ থেকে বের করার সময় হিসাব update ভুলে যাওয়া — l += 1 করলে কিন্তু window_sum -= a[l] (বা count map থেকে কমানো) করলে না — এটা খুব common। আগে বাদ দাও, পরে pointer সরাও — ক্রমটা ঠিক রাখো।
5. Negative number-এও window চালাতে যাওয়া — "sum বড় হয়ে গেছে, বাঁ থেকে কমাই" — negative থাকলে কমানোর পর sum বাড়তেও পারে! Monotonic আচরণ ভেঙে যায়; তখন Level 5-এর prefix + hash map-ই পথ। এই দুই হাতিয়ারের সীমানা চেনা এ level-এর বড় শিক্ষা।
6. Count map-এ 0 হওয়া key মুছে না ফেলা — distinct গোনার সময় len(count_map) ব্যবহার করলে value 0 হওয়া key রয়ে গেলে ভুল উত্তর। del করতে ভুলো না।
7. r − l + 1 কী গুনছে গুলিয়ে ফেলা — এটা r-এ শেষ হওয়া valid subarray সংখ্যা; প্রতি r-এ যোগ করতে হয়, শেষে একবার না।
8. Product window-এ k <= 1 edge case — product সবসময় ≥ 1 (positive int-এ), তাই k <= 1 হলে উত্তর 0; এটা না ধরলে while loop-এ l, r-কে পেরিয়ে যেতে পারে।

পরের level এ যাওয়ার আগে checklist

• [ ] 081-এর dry run করেছি — প্রতি step-এ l, r, sum-এর টেবিল হাতে লিখে
• [ ] "প্রতি step-এ search space কমে, তাই O(n)" — argument-টা নিজের ভাষায় লিখেছি
• [ ] Variable window-র template টা মুখস্থ না, বুঝে — খালি কাগজে একবার লিখেছি
• [ ] 087-এ একই array-তে window পথ আর prefix পথ — দুটোই ভেবেছি, কোনটা কখন বুঝেছি
• [ ] atMost(2) − atMost(1)-এর হিসাব একটা ছোট array-তে হাতে মিলিয়েছি
• [ ] Negative number এলে window কেন ভেঙে পড়ে — একটা counter-example নিজে বানিয়েছি

সব টিক দিতে পারলে — চলো Level 7: Binary Search on Answer-এ। সেখানে আঙুল আর জানালা ছেড়ে শিখবে অনুমানের খেলা — প্রতি প্রশ্নে অর্ধেক জগৎ বাদ।

Source map

এই folder-এর প্রতিটা concept আর problem কোথা থেকে এসেছে, কোন link official, আর কোনটা original লেখা — সব হিসাব আছে source-map.md-তে।