# Concept Notes — Two Pointers ও Sliding Window (ভেতর থেকে বোঝা)

## সহজ করে শুরু: কোন শর্তে একটি প্রান্ত সরানো নিরাপদ

Sorted array-এ যোগ ছোট হলে বাঁ প্রান্ত বাড়িয়ে বড় মান নেওয়া যায়; যোগ বড় হলে ডান প্রান্ত কমানো যায়। Sliding window-তে পাশাপাশি থাকা অংশের হিসাব রাখি, একবারে একটি প্রান্ত সরাই। প্রতিবার কী শর্ত ঠিক রাখছি—সেটিই invariant।

**প্রোগ্রামে কোথায় ব্যবহার করবে:** নির্দিষ্ট সময়ের চলমান যোগ, দীর্ঘতম বৈধ substring, positive মানের target-sum window এবং sorted data-তে pair search-এ লাগে।

**কৌশল বাছার আগে শর্ত:** Sum-ভিত্তিক সাধারণ sliding window-তে negative মান থাকলে যুক্তি ভাঙতে পারে; তখন prefix sum + hash map দরকার হতে পারে। Product window-এর এখানে ব্যবহৃত নিয়ম strictly positive integer-এর জন্য।

পড়ার ক্রম: এই পরিচয় → নিচের বিস্তারিত ধারণা → [চিত্রে হাতে-কলমে হিসাব](visualization-ideas.md) → [সমস্যার তালিকা](problems/README.md)। প্রতিটি উদাহরণে আগে input, পরে বদলানো state, শেষে output মেলাও।

> এই 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`
- **সমান** হলে → পেয়ে গেছ!

```python
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`):

```text
l=0, r=4:  1 + 9 = 10  → পাওয়া গেল! উত্তর (0, 4)
```

খুব তাড়াতাড়ি মিলে গেল — আরেকটা চালাই (`target = 7`):

```text
l=0, r=4:  1 + 9 = 10 > 7  → r--
l=0, r=3:  1 + 6 = 7        → পাওয়া গেল! (0, 3)
```

**কেন `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]` বেশি বড় না হয়ে যায়।

```python
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`):

```text
i=0, j=1:  3-1=2 < 4  → j++
i=0, j=2:  5-1=4 ✓     → (0, 2)
```

লক্ষ করো দুজনেই শুধু **ডানে** যায়, কেউ পিছায় না — তাই মোট 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²)**।

```python
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 কমে ঠিকই, উচ্চতা **বাড়ার সম্ভাবনা** খোলে। অর্থাৎ ছোট দেয়ালকে রেখে দিয়ে আর কোনো ভালো পাত্র সম্ভব না — তাকেই ছাড়ো:

```text
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 আবার গোনার দরকার নেই:

```python
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:

```python
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`):

```text
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:

```python
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-এ এই সংখ্যাটা যোগ করো:

```python
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`):

```text
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 দিয়ে সোজা! আর লক্ষ করো:

```text
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
```

```python
def exactly_k_distinct(a, k):
    return at_most_k(a, k) - at_most_k(a, k - 1)
```

যেখানে `at_most_k` হলো section 6-এর window + section 7-এর `r - l + 1` গোনা। একটা কঠিন প্রশ্ন = দুটো সহজ প্রশ্নের বিয়োগ — এই decomposition-চিন্তা বহু জায়গায় কাজে লাগবে ("ঠিক K" যেখানেই দেখো, "বড়জোর K-এর বিয়োগ" মাথায় আসুক)।

## এক নজরে cheat sheet

```text
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 আটকে গেলে ছবিটা মনে মনে চালাও — পরের লাইনটা ছবিই বলে দেবে।