Arrays and Strings — Frame-by-Frame Visuals¶
প্রতিটা sequence উপর থেকে নিচে পড়ো। প্রতিটা frame-এ arrow (^) গুলো কোথায় point করছে সেটা track করো — arrow-গুলোই পুরো গল্প।
1. Spare room-এ append (সস্তা case)¶
Capacity 4 আর size 3 এমন একটা dynamic array 9 append করছে।
FRAME 1 — before FRAME 2 — after append(9)
+----+----+----+----+ +----+----+----+----+
| 5 | 2 | 7 | __ | | 5 | 2 | 7 | 9 |
+----+----+----+----+ +----+----+----+----+
size = 3, capacity = 4 size = 4, capacity = 4
^ write here nothing moved — O(1)
2. যে append-এ resize লাগে (বিরল, দামি case)¶
এবার array টা ভরা, আর আমরা 4 append করছি।
FRAME 1 — full FRAME 2 — allocate double capacity
+----+----+----+----+ old: +----+----+----+----+
| 5 | 2 | 7 | 9 | | 5 | 2 | 7 | 9 |
+----+----+----+----+ +----+----+----+----+
size = 4 = capacity new: +----+----+----+----+----+----+----+----+
no room! | __ | __ | __ | __ | __ | __ | __ | __ |
+----+----+----+----+----+----+----+----+
FRAME 3 — copy all 4 items (O(n)) FRAME 4 — append lands, old block freed
new: +----+----+----+----+----+... +----+----+----+----+----+----+----+----+
| 5 | 2 | 7 | 9 | __ | | 5 | 2 | 7 | 9 | 4 | __ | __ | __ |
+----+----+----+----+----+... +----+----+----+----+----+----+----+----+
copy copy copy copy size = 5, capacity = 8
next 3 appends are O(1) again
এই doubling অনেকক্ষণের জন্য সস্তা append কিনে আনে। গড় হিসাবে append হলো O(1) amortized।
3. Index 1-এ insert (পরের সবকিছু ডানে shift হয়)¶
[5, 2, 7, 9]-এর index 1-এ 8 insert করো।
FRAME 1 — before FRAME 2 — shift right FRAME 3 — shift right
[ 5 | 2 | 7 | 9 | _ ] [ 5 | 2 | 7 | _ | 9 ] [ 5 | 2 | _ | 7 | 9 ]
^ target -----> ----->
9 moved 3 -> 4 7 moved 2 -> 3
FRAME 4 — shift right FRAME 5 — place 8
[ 5 | _ | 2 | 7 | 9 ] [ 5 | 8 | 2 | 7 | 9 ]
-----> ^
2 moved 1 -> 2 done — 3 shifts for a 4-item array = O(n)
4. Index 1-এ delete (পরের সবকিছু বাঁয়ে shift হয়)¶
[5, 8, 2, 7, 9] থেকে index 1 delete করো।
FRAME 1 — before FRAME 2 — shift left FRAME 3 — shift left
[ 5 | 8 | 2 | 7 | 9 ] [ 5 | 2 | _ | 7 | 9 ] [ 5 | 2 | 7 | _ | 9 ]
^ remove <----- <-----
2 moved 2 -> 1 7 moved 3 -> 2
FRAME 4 — shift left FRAME 5 — done
[ 5 | 2 | 7 | 9 | _ ] [ 5 | 2 | 7 | 9 ]
<----- size shrank by 1 — again O(n) shifting
5. Two pointers: in place reverse¶
[A, B, C, D, E] reverse করো — pointer L আর R একে অপরের দিকে হাঁটছে।
FRAME 1 FRAME 2 — swap A,E FRAME 3 — move inward, swap B,D
[ A | B | C | D | E ] [ E | B | C | D | A ] [ E | D | C | B | A ]
^ ^ ^ ^ ^ ^
L R L R L R
FRAME 4 — pointers meet
[ E | D | C | B | A ]
^
L = R -> stop. n/2 swaps total = O(n), no extra array used.
6. Sliding window: repeat ছাড়া longest substring¶
String "abcabcbb", window [L..R], একটা set-এ window-র character গুলো থাকছে।
FRAME 1: a b c a b c b b FRAME 2: a b c a b c b b FRAME 3: a b c a b c b b
^ ^...^ ^.....^
L=R=0 set={a} L=0 R=1 set={a,b} L=0 R=2 set={a,b,c}
best = 3
FRAME 4: R moves to index 3 ('a') — DUPLICATE! Shrink from the left.
a b c a b c b b
^...^
L=1 R=3 removed old 'a', window = "bca", set={b,c,a}
FRAME 5..: keep sliding — window stays duplicate-free
a b c a b c b b
^...^
L=3 R=5 window="abc" best stays 3
প্রতিটা index window-তে একবার ঢোকে আর একবার বের হয় → মোট O(n), দুটো pointer থাকা সত্ত্বেও।
7. Prefix sums: একটা range query-র উত্তর¶
Array a = [3, 1, 4, 1, 5], নিচে prefix row বানানো হয়েছে।
index: 0 1 2 3 4
a: [ 3 | 1 | 4 | 1 | 5 ]
prefix: [ 0 | 3 | 4 | 8 | 9 | 14 ]
0 1 2 3 4 5 (prefix[i] = sum of first i items)
Query: sum of a[1..3]?
cut here ->| |<- cut here
prefix: [ 0 | 3 | 4 | 8 | 9 | 14 ]
^ ^
prefix[1]=3 prefix[4]=9 answer = 9 - 3 = 6
বানাতে এক pass লাগে, তারপর প্রতিটা range-sum query শুধু একটা subtraction।
8. String concatenation: loop-এ += কেন quadratic¶
"abcd" এক character করে বানানো হচ্ছে। প্রতিটা += পুরো পুরনো string-টা copy করে।
step 1: "" + a -> [a] copies 0
step 2: [a] + b -> [a|b] copies 1 (a copied again)
step 3: [a|b] + c -> [a|b|c] copies 2 (a,b copied again)
step 4: [a|b|c]+ d -> [a|b|c|d] copies 3 (a,b,c copied again)
total copies = 0+1+2+3 — grows like n^2/2.
The fix: append pieces to a list (cheap), then one final ''.join:
[a] [b] [c] [d] --join--> [a|b|c|d] each char copied exactly once = O(n)
এই frame গুলো কীভাবে পড়বে¶
- প্রতিটা "after" frame হাত দিয়ে ঢেকে রেখে আগে নিজে predict করো, তারপর দেখো।
- Frame sequence 3, 5, আর 6 কাগজে মুখস্থ থেকে আবার আঁকো — interview এগুলোর উপরেই চলে।
- তারপর যাও operations.md-তে, যেখানে প্রতিটা operation-এর cost analysis আর pitfalls আছে।