# Two pointers ও sliding window — প্রতিটি অবস্থার ছবি

## Sorted array-এ target 11

```dsa
kind: array
title: "বড় যোগে R বাঁয়ে, ছোট যোগে L ডানে"
steps:
  - label: "১. দুই প্রান্তের যোগ 12"
    values: [1, 2, 4, 7, 9, 11]
    active: [0, 5]
    pointers: {L: 0, R: 5}
    note: "1 + 11 > 11; R এক ঘর বাঁয়ে আনি।"
  - label: "২. এখন যোগ 10"
    values: [1, 2, 4, 7, 9, 11]
    active: [0, 4]
    muted: [5]
    pointers: {L: 0, R: 4}
    note: "1 + 9 < 11; L এক ঘর ডানে নিই।"
  - label: "৩. জোড়া পাওয়া গেছে"
    values: [1, 2, 4, 7, 9, 11]
    active: [1, 4]
    muted: [0, 5]
    pointers: {L: 1, R: 4}
    note: "2 + 9 = 11। ম্লান ঘরগুলো অনুসন্ধান থেকে আগেই বাদ গেছে।"
```

কেন প্রথম ধাপে 11 বাদ দেওয়া নিরাপদ? সবচেয়ে ছোট মান 1 দিয়েও যোগ বেশি; 11-এর সঙ্গে অন্য কোনো বেঁচে থাকা মান নিলে যোগ আরও বাড়বে।

## Sum অন্তত 7: সবচেয়ে ছোট positive window

Array `[2,3,1,2,4,3]`; প্রতিবার ডানে একটি মান যোগ করি, sum যথেষ্ট থাকলে বাঁ থেকে ছোট করি।

| নতুন R | সব পর্যবেক্ষিত valid window | shrink শেষে window | best দৈর্ঘ্য |
| --- | --- | --- | --- |
| 0, মান 2 | নেই | [2] | নেই |
| 1, মান 3 | নেই | [2,3] | নেই |
| 2, মান 1 | নেই | [2,3,1] | নেই |
| 3, মান 2 | [2,3,1,2], sum 8 | [3,1,2], sum 6 | 4 |
| 4, মান 4 | [3,1,2,4], sum 10; [1,2,4], sum 7 | [2,4], sum 6 | 3 |
| 5, মান 3 | [2,4,3], sum 9; [4,3], sum 7 | [3], sum 3 | 2 |

```mermaid
flowchart LR
    A["R ডানে: একটি মান যোগ"] --> B{"sum অন্তত 7?"}
    B -->|"হ্যাঁ"| C["best রাখি, বাঁয়ের মান বাদ, L বাড়াই"]
    C --> B
    B -->|"না"| D["পরের R"]
```

প্রতিটি pointer শুধু ডানে চলে; তাই মোট pointer move O(n)। Negative মান যোগ হলে sum কমতেও পারে—তখন এই প্রমাণ প্রযোজ্য নয়।

## Exactly 2 distinct: [1,2,1,3]

| গণনা | প্রতিটি R-এ নতুন valid subarray সংখ্যা | মোট |
| --- | --- | --- |
| atMost(2) | 1,2,3,2 | 8 |
| atMost(1) | 1,1,1,1 | 4 |
| exactly(2) | atMost(2) − atMost(1) | 4 |

সেই চারটি subarray: [1,2], [2,1], [1,2,1], [1,3]। সব একই value হলেও আলাদা index interval হলে আলাদা subarray হিসেবে গুনতে হয়।

## একই দিকে দুই pointer: difference 3

Sorted array `[1,2,4,7]`।

| i | j | a[j]−a[i] | সিদ্ধান্ত |
| --- | --- | --- | --- |
| 0 | 1 | 1 | j বাড়াই |
| 0 | 2 | 3 | (1,4) পাওয়া গেছে |

Difference বেশি হলে i বাড়িয়ে ছোট করার চেষ্টা করি; তবে `i<j` রাখতে হবে। Unsorted array-এ মানের এই monotonic যুক্তি নেই।

## Container: ছোট দেয়াল কেন সরাই

```dsa
kind: array
title: "দেয়ালের উচ্চতা ও দুই প্রান্তের পছন্দ"
steps:
  - label: "প্রথম দুই দেয়াল"
    values: [1, 4, 2, 3]
    active: [0, 3]
    pointers: {L: 0, R: 3}
    note: "ছোট উচ্চতা 1, দূরত্ব 3: area = 3।"
  - label: "ছোট দেয়ালটি সরাই"
    values: [1, 4, 2, 3]
    active: [1, 3]
    muted: [0]
    pointers: {L: 1, R: 3}
    note: "ছোট উচ্চতা এখন 3, দূরত্ব 2: area = 6।"
```

প্রথম area `min(1,3)×3=3`। ডানের দেয়াল সরালে width কমবে, উচ্চতা এখনও সর্বোচ্চ 1—উন্নতি হবে না। বাঁয়ের ছোট দেয়াল সরালে নতুন area `min(4,3)×2=6` হতে পারে।

## `r-l+1` কোথা থেকে আসে

Valid window `[1,2,1]`-এ r=2, l=0 হলে r-এ শেষ হওয়া সব suffix: `[1,2,1]`, `[2,1]`, `[1]`—মোট 3। At-most-distinct শর্তে এগুলো সব valid। Minimum-sum শর্তে ছোট suffix valid নাও হতে পারে, তাই এই count নির্বিচারে ব্যবহার করা যাবে না।

[ধারণায় ফিরি](concept-notes.md) · [সব সমস্যা ও অনুশীলন](problems/README.md) · [মূল উৎস](source-map.md)