# Arrays and Strings — Core Operations

নিচের প্রতিটা operation চারটা প্রশ্নের উত্তর দেয়: এটা কী করে, এর খরচ যা তা কেন, দেখতে কেমন লাগে, আর beginner-রা কোথায় হোঁচট খায়।

---

## 1. Index দিয়ে access — `a[i]`

**কী করে:** position `i`-এর value পড়ে।

**কেন O(1):** address হলো `start + i * item_size` — খাঁটি arithmetic, কোনো scanning নেই। Array-র size দ্বিগুণ করলেও একটা access-এর খরচ বদলায় না।

```text
before: [ 5 | 2 | 7 | 9 ]      after: [ 5 | 2 | 7 | 9 ]   (unchanged)
                  ^ read              value 7 returned
```

```python
a = [5, 2, 7, 9]
print(a[2])    # 7
print(a[-1])   # 9  (negative index counts from the end)
```

**Pitfalls:** `a[len(a)]` দিলে `IndexError` — শেষ valid index হলো `len(a) - 1`। Negative index সুবিধার, কিন্তু কোনো index variable ভুল করে negative হয়ে গেলে bug চুপচাপ লুকিয়ে থাকতে পারে।

## 2. Index দিয়ে update — `a[i] = x`

**কী করে:** position `i`-এর value overwrite করে।

**কেন O(1):** সেই একই address arithmetic; শুধু পড়ার বদলে লিখছি।

```python
a = [5, 2, 7, 9]
a[2] = 70      # a is now [5, 2, 70, 9]
```

**Pitfalls:** string এটা support করে NA — `s[2] = 'x'` দিলে `TypeError`, কারণ Python-এর string immutable। Char-দের list-এ convert করো, edit করো, তারপর `''.join` দিয়ে ফেরত নাও।

## 3. শেষে append — `a.append(x)`

**কী করে:** শেষ element-এর পরে একটা element যোগ করে।

**কেন O(1) amortized:** সাধারণত spare capacity-ই এটাকে সাথে সাথে শুষে নেয়। মাঝে মাঝে array ভরে যায়, তখন বড় জায়গা allocate করে n-টা reference নেওয়া লাগে — O(n)। শিক্ষামূলক doubling মডেলে resize-এর মাঝে ক্রমশ বেশি সস্তা append হয়; Python list-এর বৃদ্ধির হার আলাদা, তাই প্রতি append-এর গড় খরচ constant-ই থাকে। (এটা live দেখো [implementation.py](implementation.py)-তে।)

```text
before: [ 5 | 2 | 7 | __ ]     after: [ 5 | 2 | 7 | 9 ]
size=3 cap=4                   size=4 cap=4 — nothing shifted
```

```python
a = [5, 2, 7]
a.append(9)    # [5, 2, 7, 9]
```

**Pitfalls:** `a.append([1, 2])` পুরো list-টাকে EKটা element হিসেবে append করে; একাধিক যোগ করতে `a.extend([1, 2])` বা `a += [1, 2]` ব্যবহার করো।

## 4. শেষ থেকে pop — `a.pop()`

**কী করে:** শেষ element-টা সরিয়ে return করে।

**কেন O(1):** শেষের ডানে কোনো প্রতিবেশী নেই, তাই কিছুই shift হয় না; শুধু size counter কমে।

```python
a = [5, 2, 7, 9]
x = a.pop()    # x = 9, a = [5, 2, 7]
```

**Pitfalls:** খালি list-এ pop করলে `IndexError` — আগে `if a:` দিয়ে guard করো।

## 5. Index i-তে insert — `a.insert(i, x)`

**কী করে:** position `i`-তে `x` বসায়, পরের element গুলোকে ডানে ঠেলে দেয়।

**কেন O(n):** index `i` থেকে শেষ পর্যন্ত প্রতিটা element-কে physically এক ঘর সরতে হয় — গড়ে অর্ধেক array।

```text
before: [ 5 | 2 | 7 | 9 ]          after insert(1, 8):
              <- shift these       [ 5 | 8 | 2 | 7 | 9 ]
```

```python
a = [5, 2, 7, 9]
a.insert(1, 8)   # [5, 8, 2, 7, 9]
```

**Pitfalls:** loop-এর ভেতরে `insert(0, x)` ডাকা মানে O(n^2) program। যদি বারবার সামনে insert করতেই হয়, তোমার দরকার deque ([../04-stack-and-queue/](../04-stack-and-queue/README.md)) অথবা linked list ([../03-linked-list/](../03-linked-list/README.md))।

## 6. Index i-তে delete — `a.pop(i)` / `del a[i]`

**কী করে:** position `i`-এর element সরিয়ে দেয়, পরের element গুলোকে বাঁয়ে টেনে আনে।

**কেন O(n):** ফাঁকটা বন্ধ করতে হয় — `i`-এর পরের সবকিছু এক ঘর বাঁয়ে shift হয়।

```text
before: [ 5 | 8 | 2 | 7 | 9 ]      after pop(1):
              x  <- shift left     [ 5 | 2 | 7 | 9 ]
```

```python
a = [5, 8, 2, 7, 9]
a.pop(1)        # removes 8 -> [5, 2, 7, 9]
```

**Pitfalls:** `a.remove(x)` *value* দিয়ে remove করে (এবং শুধু প্রথম match-টা) — আগে O(n) search করে, তারপর O(n) shift। সামনের দিকে iterate করতে করতে delete করলে element skip হয়; পেছন থেকে iterate করো অথবা নতুন একটা filtered list বানাও।

## 7. Search — `x in a`, `a.index(x)`

**কী করে:** কোনো value আছে কিনা (বা কোথায় আছে) খুঁজে বের করে।

**Unsorted-এ কেন O(n):** কোনো shortcut নেই; worst case-এ প্রতিটা element দেখতে হয়। **Sorted-এ কেন O(log n):** binary search প্রতি step-এ candidate অর্ধেক করে ফেলে।

```python
a = [5, 2, 7, 9]
print(7 in a)        # True   — linear scan

import bisect
b = [2, 5, 7, 9]                       # sorted!
i = bisect.bisect_left(b, 7)           # i = 2 — binary search
print(i < len(b) and b[i] == 7)        # True
```

**Pitfalls:** Unsorted list-এ `bisect` চালালে garbage দেয়, কোনো error ছাড়াই। `a.index(x)` value না থাকলে `ValueError` তোলে — আগে `in` দিয়ে check করো অথবা exception catch করো।

## 8. Slice — `a[l:r]`

**কী করে:** position `l` থেকে `r-1` পর্যন্ত নিয়ে একটা NOTUN list বানায়।

**কেন O(r − l):** range-এর প্রতিটা element নতুন memory-তে copy হয়।

```python
a = [5, 2, 7, 9, 4]
b = a[1:4]     # [2, 7, 9] — a copy; editing b never touches a
c = a[:]       # full shallow copy
d = a[::-1]    # reversed copy
```

**Pitfalls:** slice দেখতে free মনে হলেও memory copy করে — recursion-এর ভেতরে slice করলে (naive binary-search code-এর classic ভুল) একটি অর্ধেক ধরে নামা binary search-এর O(log n) সময় O(n) হয়ে যায়: n/2+n/4+n/8-এর geometric যোগফল O(n)। বদলে `lo`/`hi` index pass করো। আরো খেয়াল রাখো, list of lists-এ *shallow* copy ভেতরের object গুলো share করে।

## 9. Traverse — প্রতিটা element ঘুরে দেখা

**কী করে:** পুরো array একবার হাঁটে।

**কেন O(n):** n-টা element, প্রতিটায় constant কাজ। বাস্তবে array যেকোনো linked structure-এর চেয়ে fast traverse হয়, কারণ contiguous memory cache-friendly।

```python
a = [5, 2, 7, 9]
for i, x in enumerate(a):    # index AND value together
    print(i, x)
```

**Pitfalls:** `for i in range(len(a))` তারপর `a[i]` কাজ করে, কিন্তু noisy — `enumerate` prefer করো। এই loop-এর ভেতরে কখনো `a`-কে বাড়িও না, কমিও না।

## 10. String operations (immutability নিয়ম পাল্টে দেয়)

**কী করে:** string-এ read, slice, search চলে — কিন্তু কখনোই in-place write না।

**কেন প্রতিটা edit O(n):** যেকোনো "change" একদম নতুন string allocate করে আর প্রতিটা character তাতে copy করে।

```python
s = "hello"
t = s.upper()          # new string "HELLO"; s is untouched
u = s.replace("l", "L")  # new string; O(n)
parts = ["ab", "cd", "ef"]
joined = "".join(parts)  # O(total length) — the right way to build strings
```

**Pitfalls:** loop-এর ভেতরে `s += piece` হলো classic O(n^2) trap (দেখো [visual-explanation.md](visual-explanation.md)-র frame 8)। `==` দিয়ে string compare করা O(n), O(1) না — hot loop-এ string যখন dict-এর key, তখন এটা relevant।

---

## Big-O summary table

| Operation | Dynamic array (`list`) | Python string (`str`) | Notes |
| --- | --- | --- | --- |
| Access `[i]` | O(1) | O(1) | address arithmetic |
| Update `[i] = x` | O(1) | not allowed | strings are immutable |
| Append at end | O(1) amortized | O(n) (new string) | doubling strategy |
| Pop from end | O(1) | — | nothing shifts |
| Insert / delete at front | O(n) | O(n) | full shift / full copy |
| Insert / delete at index i | O(n) | O(n) | shift the tail |
| Search by value (unsorted) | O(n) | O(n·m) substring | use `in` |
| Search (sorted, `bisect`) | O(log n) | — | requires sorted data |
| Slice of length k | O(k) | O(k) | makes a copy |
| Concatenate two of total length n | O(n) | O(n) | builds new object |
| Build from n pieces with `join` | — | O(n) | the fix for the += trap |
| Traverse all | O(n) | O(n) | cache-friendly |

এরপর: এই mechanics গুলোকে problem-solving-এর চালে বদলাও [patterns.md](./patterns.md)-তে।