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

[ধারণা](concept-notes.md) · [চিত্র ও উদাহরণ](visualization-ideas.md) · [সমস্যার তালিকা](problems/README.md) · [মূল উৎস](source-map.md) · [পুরো শেখার মানচিত্র](../roadmap.md)

> আগের 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](../05-prefix-difference-contribution/README.md) — বিশেষ করে 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](problems/081-two-sum-sorted.md) | 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](problems/085-sliding-window-sum.md) | fixed window | Classic exercise |

### Medium

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 082 | [Pair with Difference K](problems/082-pair-with-difference-k.md) | same-direction pointers | LeetCode K-diff Pairs — <https://leetcode.com/problems/k-diff-pairs-in-an-array/> |
| 083 | [Three Sum](problems/083-three-sum.md) | fix + two pointers | LeetCode 3Sum — <https://leetcode.com/problems/3sum/> |
| 084 | [Container With Most Water](problems/084-container-with-most-water.md) | move shorter wall | LeetCode — <https://leetcode.com/problems/container-with-most-water/> |
| 086 | [Longest Subarray with Sum K (Positive)](problems/086-longest-subarray-sum-k.md) | grow/shrink window | Classic exercise |
| 087 | [Minimum Size Subarray Sum](problems/087-minimum-size-subarray-sum.md) | shrinkable window | LeetCode — <https://leetcode.com/problems/minimum-size-subarray-sum/> |
| 088 | [Count Subarrays with At Most K Distinct](problems/088-at-most-k-distinct.md) | 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](problems/090-product-less-than-k.md) | 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](problems/089-exactly-k-distinct.md) | 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](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](../07-binary-search-on-answer/README.md)-এ। সেখানে আঙুল আর জানালা ছেড়ে শিখবে অনুমানের খেলা — প্রতি প্রশ্নে অর্ধেক জগৎ বাদ।

## Source map

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