# Arrays and Strings — Concept (ধারণা)

## একটা বাস্তব জীবনের analogy দিয়ে শুরু করি

কল্পনা করো একটা apartment-এর lobby-তে **নম্বর দেওয়া একসারি mailbox**।

- বাক্সগুলো এক সরলরেখায় একসাথে bolt করা।
- প্রতিটা বাক্সের গায়ে একটা নম্বর লেখা: 0, 1, 2, 3, ...
- প্রতিটা বাক্স **একই size-এর**।
- বাক্সের নম্বর জানা থাকলে তুমি সোজা সেটার কাছে হেঁটে যাও। বাক্স 7 খুঁজতে কখনো বাক্স 0 খুলতে হয় না।

এটাই একটা array। ওই "সোজা হেঁটে যাওয়া" অংশটাই superpower: index জানা মানেই exact location জানা।

এবার analogy-র কষ্টের দিকটা। ধরো সব বাক্স ভরা, আর নতুন এক ভাড়াটিয়ার দরকার 3 নম্বর বাক্স:

- বাক্স 2 আর বাক্স 3-এর মাঝে নতুন বাক্স গুঁজে দেওয়া যায় না — ওগুলো একসাথে bolt করা।
- একমাত্র উপায়: 3 নম্বর থেকে শুরু করে প্রতিটা বাক্স এক ঘর ডানে সরাও, তারপর নতুনটা বসাও।

ওই সরানোর কাজটাই কারণ যে **array-র মাঝখানে insert করা slow**। এই structure-এর সবচেয়ে বড় শক্তি (সবকিছু পাশাপাশি, ঠাসাঠাসি করে রাখা) — সেটাই তার সবচেয়ে বড় দুর্বলতা।

**String** হলো সেই একই lobby, কিন্তু প্রতিটা বাক্সে ঠিক একটা করে character থাকে, আর Python-এ বাক্সগুলো ঝালাই করে বন্ধ — পড়তে পারবে কিন্তু ভেতরের জিনিস কখনো বদলাতে পারবে না। String "বদলাতে" হলে তোমাকে একদম নতুন একসারি বাক্স বানাতে হয়।

## বাংলা text-এ character বলতে কী বোঝাচ্ছি?

Python `str` Unicode code point-এর sequence। পর্দায় একটি অক্ষর বা যুক্তাক্ষর হিসেবে দেখা অংশ একাধিক code point দিয়ে তৈরি হতে পারে। যেমন `len("কি") == 2`: ক ও ি আলাদা code point, একসঙ্গে দেখা যায়। তাই `"কি"[::-1]` দিয়ে উল্টালে মানুষের পড়ার উপযোগী text নষ্ট হতে পারে।

এই অধ্যায়ের string problem-এ input alphabet-এর শর্ত দেখো। ইংরেজি ছোট হাতের অক্ষরের 26-slot frequency array সরাসরি বাংলা text-এ প্রযোজ্য নয়। ব্যবহারকারীর লেখা বাংলা text কাটতে, cursor সরাতে বা reverse করতে দৃশ্যমান অক্ষরগুচ্ছের (grapheme cluster) সীমানা ধরে কাজ করতে হয়। [Python-এর string model](https://docs.python.org/3/library/stdtypes.html#text-sequence-type-str) code point ব্যাখ্যা করে।

## Memory-র ছবিটা

RAM হলো নম্বর দেওয়া byte-এর একটা বিশাল লম্বা লাইন। একটা array সেই লাইনের একটা **contiguous** (অখণ্ড) টুকরো দখল করে।

ধরো প্রতিটা item 4 byte নেয় আর array শুরু হয় address 1000 থেকে:

```text
address:   1000      1004      1008      1012      1016
         +---------+---------+---------+---------+---------+
  value: |   17    |   42    |    8    |   99    |   23    |
         +---------+---------+---------+---------+---------+
  index:     0         1         2         3         4
```

Item `i` খুঁজতে computer হিসাব করে:

```text
address_of(a[i]) = start_address + i * item_size
                 = 1000          + i * 4
```

একটা multiplication, একটা addition — শেষ। কোনো loop নেই, কোনো search নেই। **এই arithmetic-টাই array access O(1) হওয়ার পুরো কারণ।**

Python নিয়ে একটা ছোট্ট সততার কথা: Python-এর `list` আসলে *reference* (pointer)-দের একটা array রাখে, যেগুলো অন্য জায়গায় থাকা object-দের দিকে point করে। Pointer array-টা নিজে কিন্তু contiguous-ই, তাই indexing এখনো O(1) — উপরের ছবিটাই সঠিক mental model, শুধু কল্পনা করো প্রতিটা বাক্সে আসল value-র দিকে একটা তীর আছে।

### Dynamic array এক্সট্রা কী যোগ করে

সাধারণ array-র size চিরকালের জন্য fixed। Dynamic array (Python-এর `list`) তার এখনকার দরকারের চেয়ে বড় একটা block ধরে রাখে:

```text
capacity = 8, size = 5

+----+----+----+----+----+----+----+----+
| 17 | 42 |  8 | 99 | 23 | __ | __ | __ |
+----+----+----+----+----+----+----+----+
  0    1    2    3    4   (spare room)
```

`append` নতুন item-টা spare room-এ ফেলে দেয় — O(1)। Spare room ফুরিয়ে গেলে বড় block allocate করে reference-গুলো সেখানে নেওয়া হয়। শেখার উদাহরণে capacity দ্বিগুণ ধরা যায়; Python list-এর প্রকৃত বৃদ্ধির হার আলাদা। ওই copy-টা O(n), কিন্তু এত কম ঘটে যে প্রতি append-এর *গড়* খরচ O(1)-ই থাকে। একেই বলে **amortized O(1)** — [implementation.py](implementation.py) এটা scratch থেকে বানায়, যাতে তুমি নিজের চোখে ঘটতে দেখো।

## Core invariants

Invariant মানে এমন একটা fact যেটা structure-এর জন্য *সবসময়* সত্য। এগুলো মাথায় গেঁথে নাও:

1. **Contiguity।** সব element memory-র এক অখণ্ড block-এ থাকে।
2. **Index arithmetic।** Element `i` থাকে `start + i * item_size`-এ। O(1) access-এর মানে এটাই।
3. **Order মানে position।** Array মনে রাখে তুমি জিনিসগুলো *কোথায়* রেখেছ — কখন বা কেন, সেটা না।
4. **Dynamic array-র spare room।** `size <= capacity`, আর growth-এ capacity multiply হয় (প্রতিবার +1 করে বাড়ে না — তাহলে append গড়ে O(n) হয়ে যেত)।
5. **String immutability (Python)।** একটা `str` তৈরি হওয়ার পর আর কখনো বদলায় না। প্রতিটা "modification" নতুন string বানায় আর তার জন্য O(length) খরচ দেয়।

## কখন array ব্যবহার করবে

- তোমার দরকার **position দিয়ে fast access**: "item 500 দাও" — সাথে সাথে।
- তুমি মূলত **শেষে append** করো আর **read/scan** করো — সস্তা operation গুলো।
- তুমি **সবকিছুর উপর iterate** করতে চাও যত fast সম্ভব (cache array-কে ভালোবাসে)।
- Size জানা আছে, অথবা মূলত এক প্রান্ত দিয়েই বাড়ে।
- তুমি এর উপর অন্য কিছু বানাতে যাচ্ছ: heap, hash table, prefix sums — সবই array-র উপর বসে।

## কখন array ব্যবহার করবে NA

- তুমি অনবরত **মাঝখানে insert বা delete** করো → প্রতিবার O(n) item shift হয়। Linked list ([../03-linked-list/](../03-linked-list/README.md)) এই shifting-টা সরিয়ে দেয় (যদিও বদলে O(1) indexing হারায়)।
- তোমার fast **"এই value-টা কি আছে?"** lookup দরকার → set বা dict দেয় O(1) average membership; unsorted array দেয় O(n)।
- ঘন ঘন update-এর সাথে fast **min/max** দরকার → একটা heap।
- তুমি মূলত **সামনে** add/remove করো → `collections.deque` ([../04-stack-and-queue/](../04-stack-and-queue/README.md)); list-এর সামনে থেকে pop করা O(n)।

## Complexity table

n element-এর একটা dynamic array-র জন্য:

| Operation | Time | Why |
| --- | --- | --- |
| Access `a[i]` | O(1) | address arithmetic |
| Update `a[i] = x` | O(1) | একই arithmetic |
| Append at end | O(1) amortized | spare room; কালেভদ্রে doubling copy |
| Pop from end | O(1) | কিছুই shift হয় না |
| Insert at index i | O(n) | i-এর পরের সবকিছু shift হয় |
| Delete at index i | O(n) | i-এর পরের সবকিছু পেছনে shift হয় |
| Search (unsorted) | O(n) | প্রতিটা item দেখতেই হবে |
| Search (sorted) | O(log n) | binary search |
| Slice `a[l:r]` | O(r - l) | ততগুলো item copy হয় |
| String concatenation `s + t` | O(len(s) + len(t)) | পুরো নতুন string বানায় |

## ছোট ছোট snippet, dry run সহ

### Snippet 1 — index access মানে শুধুই arithmetic

```python
a = [17, 42, 8, 99, 23]
x = a[3]          # jump straight to position 3
print(x)          # 99
```

Dry run:

```text
start of block known internally; index 3 requested
-> compute offset: 3 slots past the start
-> read that slot: 99
no other element was ever touched
```

### Snippet 2 — insertion-এ পরের সবকিছু shift হয়

```python
a = [17, 42, 8, 99, 23]
a.insert(2, 555)  # put 555 at index 2
print(a)          # [17, 42, 555, 8, 99, 23]
```

Dry run:

```text
before:  [17, 42,  8, 99, 23]
shift:   23 moves index 4 -> 5
shift:   99 moves index 3 -> 4
shift:    8 moves index 2 -> 3        (3 shifts = O(n) work)
place:   555 lands at index 2
after:   [17, 42, 555, 8, 99, 23]
```

### Snippet 3 — string concatenation-এর trap

```python
# BAD: O(n^2) total — each += copies the whole string so far
s = ""
for ch in "hello":
    s += ch

# GOOD: O(n) total — collect pieces, glue once
parts = []
for ch in "hello":
    parts.append(ch)
s = "".join(parts)
```

BAD version-এর dry run:

```text
s=""   += "h" -> copies 0 chars, writes 1   (new string "h")
s="h"  += "e" -> copies 1 char,  writes 1   (new string "he")
s="he" += "l" -> copies 2 chars, writes 1   (new string "hel")
s="hel" += "l" -> copies 3 chars, writes 1  (new string "hell")
s="hell" += "o" -> copies 4 chars, writes 1 (new string "hello")
total copying: 0+1+2+3+4 ≈ n^2/2 character moves for length n
```

### Snippet 4 — prefix sums অনেকগুলো scan-কে একটায় নামিয়ে আনে

```python
a = [3, 1, 4, 1, 5]
prefix = [0]
for x in a:
    prefix.append(prefix[-1] + x)
# prefix = [0, 3, 4, 8, 9, 14]
# sum of a[l..r] (inclusive) = prefix[r + 1] - prefix[l]
print(prefix[4] - prefix[1])   # sum of a[1..3] = 1+4+1 = 6
```

Dry run:

```text
prefix starts [0]
x=3 -> append 0+3=3      prefix=[0,3]
x=1 -> append 3+1=4      prefix=[0,3,4]
x=4 -> append 4+4=8      prefix=[0,3,4,8]
x=1 -> append 8+1=9      prefix=[0,3,4,8,9]
x=5 -> append 9+5=14     prefix=[0,3,4,8,9,14]
query a[1..3]: prefix[4]-prefix[1] = 9-3 = 6  (one subtraction, no loop)
```

এই idea টা সরাসরি math fundamentals থেকে এসেছে — আরো গভীরে যেতে দেখো [../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md)।

## মনে রাখার মতো এক বাক্য

> Array flexible shape-এর বদলে নেয় instant position: সে সবসময় জানে item `i` *কোথায়* থাকে, আর তার দাম দেয় মাঝখানে কিছু বদলালেই item গুলোকে physically shift করে।

এরপর: এই idea গুলোকে frame by frame নড়তে দেখো [visual-explanation.md](./visual-explanation.md)-তে।