# 02 — Arrays and Strings

## এখান থেকে শুরু করো

প্রথমে [ধারণা](concept.md), তারপর [সম্পূর্ণ চিত্র ও ধাপে ধাপে উদাহরণ](visual-explanation.md), তারপর [কোন প্রশ্নে কোন pattern](patterns.md) পড়ো। প্রয়োজন হলে [operation ও খরচ](operations.md) পাশে রাখো। [সমস্ত problem ও বাংলা নোট](problems/README.md) এবং [উৎসের তালিকা](source-map.md) সরাসরি খোলা যাবে।

| ধাপ | কী শিখবে | প্রথম অনুশীলন |
| --- | --- | --- |
| 1 | index ও in-place update | [Reverse String](problems/001-reverse-string.md) |
| 2 | একবার scan করে তথ্য রাখা | [Buy/Sell Stock](problems/007-buy-sell-stock.md) |
| 3 | বারবার range query | [Static Range Sum](problems/009-static-range-sum.md) |
| 4 | window-এর শর্ত বজায় রাখা | [Longest Unique Substring](problems/010-longest-unique-substring.md) |
| 5 | আগের prefix মনে রাখা | [Subarray Sum K](problems/015-subarray-sum-k.md) |
| 6 | একাধিক pattern মেলানো | [Minimum Window](problems/020-minimum-window-substring.md) |

প্রতিটি ধাপে আগে ছোট input নিজে আঁকো, তারপর code লেখো। পরের ধাপে যাওয়ার আগে বলো: **কোন তথ্য রাখছি, প্রতি ধাপে কোন নিয়ম ঠিক থাকছে, এবং কাজের মোট খরচ কত?**

## বাস্তব প্রোগ্রামে সিদ্ধান্ত নেওয়া

| প্রোগ্রামে দরকার | তথ্য কীভাবে রাখবে | কেন এই পদ্ধতি | সীমাবদ্ধতা |
| --- | --- | --- | --- |
| প্রতিদিনের বিক্রির মোট ও যেকোনো তারিখসীমার যোগফল | দিনের পরিমাণ array-তে, আলাদা prefix array | একবার O(n) প্রস্তুতি; প্রতিটি query O(1) | পুরনো দিনের পরিমাণ বদলালে সাধারণ prefix আবার বানাতে হয় |
| sensor-এর শেষ 10টি sample-এর গড় | fixed-size window ও চলতি sum | নতুনটি যোগ, পুরনোটি বিয়োগ | window-এর আকার ও খালি input সামলাতে হবে |
| CSV export বা report text তৈরি | টুকরোগুলো list-এ রেখে একবার `join` | বারবার বড় string কপির খরচ এড়ায় | output-এর মোট দৈর্ঘ্যের memory লাগবেই |
| sorted দুই batch একত্র করা | দুইটি pointer | প্রতিটি item একবার নেওয়া হয় | input দুটি আগে থেকেই sorted হতে হবে |


> সবচেয়ে fundamental data structure: memory-তে পাশাপাশি বসে থাকা একসারি বাক্স।

---

## এই data structure টা কী

**Array** হলো fixed-size, ordered একটা collection যেখানে সব item memory-র একটা continuous block-এ পাশাপাশি থাকে। প্রতিটা item-এর একটা index আছে (0, 1, 2, ...), আর তুমি যেকোনো index-এ এক লাফে পৌঁছে যেতে পারো।

**String**-কে character-এর ক্রম হিসেবে ভাবা যায়। প্রায় সব array trick string-এও কাজ করে — সেজন্যই আমরা দুটো একসাথে শিখি।

Python-এ built-in `list` হলো একটা *dynamic array*: এমন array যেটা ভরে গেলে চুপিচুপি নিজে নিজেই বড় হয়ে যায়। Python-এর `str` হলো *immutable* character array — তুমি এটাকে in place বদলাতে পারবে না, শুধু নতুন string বানাতে পারবে।

## কেন এটার দরকার (কোন কষ্ট দূর করে)

Array আসার আগে ভাবো, 1,000টা exam score রাখতে হবে 1,000টা আলাদা variable-এ: `score1`, `score2`, ... `score1000`। এদের উপর loop চালানো যেত না, sort করা যেত না, এক জিনিস হিসেবে কোথাও পাঠানোও যেত না।

Array একসাথে তিনটা কষ্ট দূর করে:

- **এক নাম, অনেক value।** হাজারটা variable name-এর জায়গায় শুধু `scores[i]`।
- **Instant access।** Item গুলো পাশাপাশি থাকে বলে computer একটা multiplication দিয়েই item `i`-এর exact memory address বের করে ফেলে — কোনো searching লাগে না। এটাই সেই বিখ্যাত **O(1) random access**।
- **Cache friendliness।** আসল hardware-এ memory-র পাশের জিনিস পড়া ছড়ানো-ছিটানো pointer ধাওয়া করার চেয়ে অনেক fast। বড় data ধারাবাহিকভাবে পড়ার কাজে contiguous storage প্রায়ই সুবিধা দেয়।

## আসল software-এ কোথায় ব্যবহার হয়

- তুমি যে image দেখো, প্রতিটাই pixel-এর একটা 2D array।
- Audio হলো sample-এর array; video হলো frame-এর array।
- Database থেকে আনা row, spreadsheet column বা CSV record প্রোগ্রামে প্রায়ই array/list-এ রাখা হয়।
- Python `list`, Java `ArrayList`, C++ `vector`, JavaScript `Array` — সবই dynamic array।
- প্রতিটা parser, compiler, search engine আর text editor-এর শক্তি string।
- Hash table, heap, আর অনেক graph ভেতরে ভেতরে array-র *উপরেই* বানানো।

## Prerequisites

- Basic Python: variable, `for` loop, `while` loop, `if`, function।
- Indexing আর slicing: `a[0]`, `a[-1]`, `a[1:4]`।
- Big-O — "O(1) vs O(n) vs O(n^2)" এই intuition level পর্যন্ত হলেই চলবে।

## শেখার আগে কী revise করবে

- এমন loop যেটা index-কে `0` থেকে `len(a) - 1` পর্যন্ত হাঁটায়।
- *Value* আর *index*-এর পার্থক্য।
- Math fundamentals section-এর prefix sums ([../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md)) — বেশ কয়েকটা array pattern সরাসরি ওই idea থেকেই আসে।
- Integer division আর modulo (`//`, `%`) — rotation trick-এ লাগবে।

## Learning goals (checklist)

- [ ] এক বাক্যে বলতে পারবে কেন array access O(1) কিন্তু মাঝখানে insertion O(n)।
- [ ] কাগজে array-র memory layout আঁকতে পারবে।
- [ ] Dynamic array কীভাবে capacity বাড়ায় আর `append` কেন *amortized* O(1), বুঝিয়ে বলতে পারবে।
- [ ] Python string কেন immutable আর এর জন্য কী খরচ দিতে হয়, বলতে পারবে।
- [ ] কোনো hint ছাড়া একটা two-pointer problem solve করবে।
- [ ] কোনো hint ছাড়া একটা sliding-window problem solve করবে।
- [ ] Prefix-sum array দিয়ে range-sum query-র উত্তর দিতে পারবে।
- [ ] একটা array-কে in place reverse আর rotate করতে পারবে।
- [ ] Kadane's algorithm apply করবে আর *কেন* এটা কাজ করে সেটা বুঝিয়ে বলবে।
- [ ] O(n^2) string-concatenation trap টা চিনে `join` দিয়ে ঠিক করতে পারবে।

## Problem categories

| Category | Typical question shape |
| --- | --- |
| Two pointers | "কোনো property-ওয়ালা pair / triple", "in place duplicates remove করো" |
| Sliding window | "X শর্ত মানে এমন longest / shortest subarray বা substring" |
| Prefix sums | "একটা range-এর sum", "sum K এমন subarray count করো" |
| In-place reversal / rotation | "k দিয়ে rotate করো", "word গুলো reverse করো" |
| Frequency counting | "Anagram", "first unique character", "majority element" |
| String building | "Efficiently একটা string construct / transform করো" |
| Kadane's | "Maximum subarray sum (product-এর জন্য আলাদা min/max state লাগে)" |

## Practice list

নিচের সব problem statement আমাদের নিজের ভাষায় লেখা; official statement-এর জন্য link follow করো। Difficulty label গুলো মোটামুটি একটা ধারণা মাত্র।

### Easy

| Problem | Official task | Pattern | বাংলা ব্যাখ্যা |
| --- | --- | --- | --- |
| Two Sum — এমন দুটো index খোঁজো যাদের value যোগ করলে target হয় | [LeetCode 1](https://leetcode.com/problems/two-sum/) | Frequency counting / complement | [নোট পড়ো](problems/002-two-sum.md) |
| Valid Anagram — দুটো string কি একই letter ব্যবহার করে? | [LeetCode 242](https://leetcode.com/problems/valid-anagram/) | Frequency counting | [নোট পড়ো](problems/003-valid-anagram.md) |
| Reverse String — একটা char array in place reverse করো | [LeetCode 344](https://leetcode.com/problems/reverse-string/) | Two pointers | [নোট পড়ো](problems/001-reverse-string.md) |
| Merge Sorted Array — বড় array-টার ভেতরেই in place merge করো | [LeetCode 88](https://leetcode.com/problems/merge-sorted-array/) | Two pointers (পেছন থেকে) | [নোট পড়ো](problems/005-merge-sorted-array.md) |
| Remove Duplicates from Sorted Array | [LeetCode 26](https://leetcode.com/problems/remove-duplicates-from-sorted-array/) | Two pointers (slow/fast) | [নোট পড়ো](problems/004-remove-duplicates-sorted.md) |
| Best Time to Buy and Sell Stock — একবার buy, একবার sell, max profit | [LeetCode 121](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/) | Running min (Kadane-ঘেঁষা) | [নোট পড়ো](problems/007-buy-sell-stock.md) |
| Watermelon — একটা weight কে দুটো জোড় ভাগে ভাঙো | [Codeforces 4A](https://codeforces.com/problemset/problem/4/A) | Parity / array warm-up | [নোট পড়ো](problems/008-watermelon.md) |

### Medium

| Problem | Official task | Pattern | বাংলা ব্যাখ্যা |
| --- | --- | --- | --- |
| Maximum Subarray — contiguous run-এর সবচেয়ে বড় sum | [LeetCode 53](https://leetcode.com/problems/maximum-subarray/) | Kadane's | [নোট পড়ো](problems/011-maximum-subarray.md) |
| Longest Substring Without Repeating Characters | [LeetCode 3](https://leetcode.com/problems/longest-substring-without-repeating-characters/) | Sliding window | [নোট পড়ো](problems/010-longest-unique-substring.md) |
| Container With Most Water — দেয়ালের সেরা pair | [LeetCode 11](https://leetcode.com/problems/container-with-most-water/) | Two pointers | [নোট পড়ো](problems/012-container-most-water.md) |
| Product of Array Except Self | [LeetCode 238](https://leetcode.com/problems/product-of-array-except-self/) | Prefix products | [নোট পড়ো](problems/014-product-except-self.md) |
| Subarray Sum Equals K | [LeetCode 560](https://leetcode.com/problems/subarray-sum-equals-k/) | Prefix sums + hash map | [নোট পড়ো](problems/015-subarray-sum-k.md) |
| Rotate Array — in place k ঘর ডানে shift করো | [LeetCode 189](https://leetcode.com/problems/rotate-array/) | Triple-reversal | [নোট পড়ো](problems/013-rotate-array.md) |
| 3Sum — zero-তে sum হয় এমন সব unique triple | [LeetCode 15](https://leetcode.com/problems/3sum/) | Sort + two pointers | [নোট পড়ো](problems/016-three-sum.md) |
| Group Anagrams — letter content অনুযায়ী word গুলো bucket করো | [LeetCode 49](https://leetcode.com/problems/group-anagrams/) | Frequency counting / canonical key | [নোট পড়ো](problems/017-group-anagrams.md) |
| Static Range Sum Queries | [CSES Problem Set](https://cses.fi/problemset/task/1646/) — "Static Range Sum Queries" | Prefix sums | [নোট পড়ো](problems/009-static-range-sum.md) |

### Hard

| Problem | Official task | Pattern | বাংলা ব্যাখ্যা |
| --- | --- | --- | --- |
| Minimum Window Substring — t-এর সব char cover করে এমন shortest window | [LeetCode 76](https://leetcode.com/problems/minimum-window-substring/) | Sliding window (shrinkable) | [নোট পড়ো](problems/020-minimum-window-substring.md) |
| Trapping Rain Water — bar-গুলোর মাঝে আটকে থাকা পানি | [LeetCode 42](https://leetcode.com/problems/trapping-rain-water/) | Two pointers / prefix max | [নোট পড়ো](problems/021-trapping-rain-water.md) |
| First Missing Positive — O(n)/O(1)-এ smallest missing positive | [LeetCode 41](https://leetcode.com/problems/first-missing-positive/) | In-place index marking | [নোট পড়ো](problems/022-first-missing-positive.md) |
| Sliding Window Maximum — size k-এর প্রতিটা window-র max | [LeetCode 239](https://leetcode.com/problems/sliding-window-maximum/) | Monotonic deque (দেখো [../04-stack-and-queue/patterns.md](../04-stack-and-queue/patterns.md)) | [নোট পড়ো](problems/023-sliding-window-maximum.md) |

## Visualization ideas

- Array-টাকে একসারি বাক্স হিসেবে আঁকো, নিচে index লেখো; two pointers-এর জন্য রঙিন arrow নাড়াও।
- Sliding window-র জন্য window-টা shade করে frame by frame সরাও।
- Prefix sums-এর জন্য array-র নিচে একটা দ্বিতীয় row আঁকো যেখানে running total থাকবে।
- [VisuAlgo](https://visualgo.net/en)-র interactive visualizer try করো ("Array" / sorting module গুলো)।
- Code চালানোর আগে [visual-explanation.md](visual-explanation.md)-র প্রতিটা example পেন্সিল আর কাগজে নিজে re-trace করো।

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

- Off-by-one error: `range(n)` vs `range(n + 1)`, window-র শেষটা inclusive নাকি exclusive।
- একটা list-এর উপর iterate করতে করতে সেটাকেই mutate করা।
- Loop-এর ভেতরে `+=` দিয়ে string বানানো — O(n^2)। ব্যবহার করো `''.join(parts)`।
- ভুলে যাওয়া যে Python-এর slice data copy করে: `a[1:]` time *এবং* memory দুটোতেই O(n)।
- "Subarray" (contiguous) আর "subsequence" (contiguous হওয়া জরুরি না) গুলিয়ে ফেলা।
- Sliding window ভুল order-এ shrink করা (আগে ডান দিক সরাও, তারপর বাঁ দিক ঠিক করো)।
- Loop-এর ভেতরে list-এ `in` চালানো (প্রতিবার O(n)), যেখানে একটা set ব্যবহার করলেই O(1) হয়ে যেত।

## Interview problem-এর সাথে connection

বড় tech company-গুলোর interview screen-এ arrays আর strings-এরই রাজত্ব। শুধু two pointers, sliding window, আর prefix sums মিলেই common big-tech interview style-এর "medium" question-এর বিশাল একটা অংশ cover হয়ে যায়। তুমি যদি narrate করতে পারো window *কেন* expand বা shrink করছে, তাহলে interviewer ঠিক যে reasoning শুনতে চায় সেটাই দেখাচ্ছ।

## Competitive programming-এর সাথে connection

- Codeforces আর CSES-এ prefix sums আর difference arrays রোজকার tool।
- Kadane's অনেক "best segment" problem-এ generalize হয়।
- Fast I/O আর একটা single array scan মিলে Div 2 A/B problem-এর বড় একটা অংশ solve হয়ে যায়।
- Monotonic-structure trick গুলো (next greater element, window max) এখানে যা শিখছ তার উপরেই দাঁড়ায় — দেখো [../04-stack-and-queue/](../04-stack-and-queue/README.md)।

## Recommended learning order

1. [concept.md](concept.md) — analogy, memory picture, invariants, complexity।
2. [visual-explanation.md](visual-explanation.md) — operation গুলো frame by frame দেখো।
3. [operations.md](operations.md) — প্রতিটা core operation, তার cost আর pitfalls সহ।
4. [patterns.md](patterns.md) — সাতটা named pattern, worked example সহ।
5. [implementation.py](implementation.py) — পড়ো, চালাও, ভাঙো, ঠিক করো।
6. `problems/` — tracker শুরু করো আর easy থেকে hard পর্যন্ত grind করো।

## Source map

এই folder-এর প্রতিটা idea আর link কোথা থেকে এসেছে, আর প্রতিটার copying status কী — সব দেখতে [source-map.md](./source-map.md) দেখো।