Arrays and Strings — বাক্সে বাক্সে বোঝা¶
Array-এর প্রতিটি বাক্স একটি position; index দিয়ে সেই position খুঁজে পাই। রঙ করা বাক্সে বর্তমান কাজটি হচ্ছে। আগে পরের অবস্থা অনুমান করো, তারপর ধাপটি দেখো।
1. Append: জায়গা থাকলে শুধু শেষের বাক্সটি লেখো¶
Size হলো ব্যবহৃত ঘরের সংখ্যা, capacity হলো মোট বরাদ্দ ঘর। এখানে capacity 4, কিন্তু শুরুতে 3টি ঘর ব্যবহৃত।
আগে · size 3, capacity 4
051227ফাঁকা বা বাদ দেওয়া ঘর: 3—↑ writeশেষের খালি ঘরেই নতুন মানটি যাবে।
পরে · size 4, capacity 4
051227চিহ্নিত ঘর: 39একটি write; এই append-এর খরচ O(1)।
Array ভরা থাকলে বড় block দরকার। শেখার সুবিধার জন্য এখানে capacity দ্বিগুণ করেছি; Python list ঠিক এই হারে বাড়ে না।
১ · পুরনো block ভরা
05122739size = capacity = 4।
২ · নতুন 8 ঘরের block
ফাঁকা বা বাদ দেওয়া ঘর: 0—ফাঁকা বা বাদ দেওয়া ঘর: 1—ফাঁকা বা বাদ দেওয়া ঘর: 2—ফাঁকা বা বাদ দেওয়া ঘর: 3—ফাঁকা বা বাদ দেওয়া ঘর: 4—ফাঁকা বা বাদ দেওয়া ঘর: 5—ফাঁকা বা বাদ দেওয়া ঘর: 6—ফাঁকা বা বাদ দেওয়া ঘর: 7—বরাদ্দ হয়েছে, এখনো কোনো মান কপি হয়নি।
৩ · পুরনো চারটি মান কপি
চিহ্নিত ঘর: 05চিহ্নিত ঘর: 12চিহ্নিত ঘর: 27চিহ্নিত ঘর: 39ফাঁকা বা বাদ দেওয়া ঘর: 4—ফাঁকা বা বাদ দেওয়া ঘর: 5—ফাঁকা বা বাদ দেওয়া ঘর: 6—ফাঁকা বা বাদ দেওয়া ঘর: 7—এই copy-এর খরচ O(n)।
৪ · নতুন মান বসাও
05122739চিহ্নিত ঘর: 44ফাঁকা বা বাদ দেওয়া ঘর: 5—ফাঁকা বা বাদ দেওয়া ঘর: 6—ফাঁকা বা বাদ দেওয়া ঘর: 7—size 5, capacity 8। পরের তিনটি append-এ resize লাগবে না।
একটি resize ধীর হলেও বহু append-এর মধ্যে তার খরচ ভাগ করলে প্রতি append amortized O(1) হয়।
2. Insert ও delete: মাঝের ঘরের জন্য সরানো লাগে¶
Index 1-এ 8 বসাতে আগে ডান প্রান্ত থেকে সরাও। বাঁ দিক থেকে সরালে এখনও না-সরানো মান মুছে যেতে পারে। এখানে খালি ঘরটি চলাচল দেখানোর জন্য; বাস্তবে copy-এর মাঝে একই মান দুই ঘরে সাময়িকভাবে থাকতে পারে।
শুরু
0512↑ target2739ফাঁকা বা বাদ দেওয়া ঘর: 4—9: index 3 থেকে 4
051227ফাঁকা বা বাদ দেওয়া ঘর: 3—চিহ্নিত ঘর: 497: index 2 থেকে 3
0512ফাঁকা বা বাদ দেওয়া ঘর: 2—চিহ্নিত ঘর: 37492: index 1 থেকে 2
05ফাঁকা বা বাদ দেওয়া ঘর: 1—চিহ্নিত ঘর: 2237498 বসাও
05চিহ্নিত ঘর: 18223749তিনটি মান সরিয়ে একটি write। মাঝখানে insert সাধারণভাবে O(n)।
Delete-এ বিপরীত কাজ: পরের মানগুলো এক ঘর বাঁয়ে আসে, তারপর size এক কমে।
8 বাদ দিতে হবে
05চিহ্নিত ঘর: 182237492: index 2 থেকে 1
05চিহ্নিত ঘর: 12ফাঁকা বা বাদ দেওয়া ঘর: 2—37497: index 3 থেকে 2
0512চিহ্নিত ঘর: 27ফাঁকা বা বাদ দেওয়া ঘর: 3—499: index 4 থেকে 3
051227চিহ্নিত ঘর: 39ফাঁকা বা বাদ দেওয়া ঘর: 4—ব্যবহৃত অংশ এখন প্রথম চারটি ঘর; capacity কমতেই হবে এমন নয়।
3. Two pointers: দুই প্রান্ত বদলে ভেতরে যাও¶
L ও R যে দুটি ঘর দেখায়, সেগুলোর মান swap করি। তারা মিললে বা পরস্পরকে পার হলে থামি।
১ · দুই প্রান্ত ধরো
চিহ্নিত ঘর: 0A↑ L1B2C3Dচিহ্নিত ঘর: 4E↑ R২ · A ও E swap
চিহ্নিত ঘর: 0E↑ L1B2C3Dচিহ্নিত ঘর: 4A↑ R৩ · ভেতরে এসে B ও D swap
0Eচিহ্নিত ঘর: 1D↑ L2Cচিহ্নিত ঘর: 3B↑ R4A৪ · মাঝখানে দেখা; শেষ
0E1D2C↑ L · R3B4Aদুইবার swap হয়েছে। মোট O(n) সময়, O(1) অতিরিক্ত জায়গা।
4. Sliding window: repeat হলে বাঁ দিক ছাড়ো¶
String abcabcbb-এ একই অক্ষর ছাড়া দীর্ঘতম contiguous অংশ চাই। L থেকে R পর্যন্ত ঘরগুলোই বর্তমান window।
R = 5 · বৈধ window abc
0a1b2cচিহ্নিত ঘর: 3a↑ Lচিহ্নিত ঘর: 4bচিহ্নিত ঘর: 5c↑ R6b7bwindow-তে প্রতিটি অক্ষর একবার আছে।
R = 6 · a ও পুরনো b বাদ দেওয়ার পরে
0a1b2c3a4bচিহ্নিত ঘর: 5c↑ Lচিহ্নিত ঘর: 6b↑ R7bনতুন window cb। শুধু একবার L বাড়ালে repeat দূর হতো না।
সব ধাপ নিচে আছে; প্রতিটি row-তে shrink শেষ হওয়ার পরের অবস্থা দেখানো হয়েছে।
| R | নতুন অক্ষর | বাঁ দিক থেকে বাদ | L | window | best length |
|---|---|---|---|---|---|
| 0 | a | কিছু নয় | 0 | a |
1 |
| 1 | b | কিছু নয় | 0 | ab |
2 |
| 2 | c | কিছু নয় | 0 | abc |
3 |
| 3 | a | index 0-এর a | 1 | bca |
3 |
| 4 | b | index 1-এর b | 2 | cab |
3 |
| 5 | c | index 2-এর c | 3 | abc |
3 |
| 6 | b | index 3-এর a, index 4-এর b | 5 | cb |
3 |
| 7 | b | index 5-এর c, index 6-এর b | 7 | b |
3 |
শর্ত পূরণ হওয়া পর্যন্ত while দিয়ে shrink করতে হয়। প্রতিটি index একবার ঢোকে ও একবার বের হয়, তাই মোট সময় O(n)।
5. Prefix sum: দুটি সীমার পার্থক্যই range sum¶
prefix[i] হলো প্রথম iটি মানের যোগফল। শুরুতে অতিরিক্ত 0 রাখলে index 0 থেকে শুরু হওয়া query-ও একই সূত্রে মেলে।
মূল array · চাওয়া তিনটি ঘর
03চিহ্নিত ঘর: 11↑ Lচিহ্নিত ঘর: 24চিহ্নিত ঘর: 31↑ R45prefix · ডান সীমার পরে একটি ঘর
00চিহ্নিত ঘর: 13↑ L2438চিহ্নিত ঘর: 49↑ R+1514prefix[4] − prefix[1] = 9 − 3 = 6।
Prefix বানাতে O(n) সময়। এরপর প্রতিটি query-তে prefix[R + 1] - prefix[L], অর্থাৎ O(1) কাজ।
6. String জোড়া লাগানো: একই অক্ষর বারবার কপি হচ্ছে কি?¶
সাধারণ immutable-string মডেলে পুরনো string-এর শেষে অক্ষর যোগ করতে নতুন string বানাতে হয়। abcd বানানোর পূর্ণ হিসাব:
| নতুন অক্ষর | পুরনো string | নতুন string | পুরনো অক্ষর আবার কপি |
|---|---|---|---|
| a | খালি | a |
0 |
| b | a |
ab |
1 |
| c | ab |
abc |
2 |
| d | abc |
abcd |
3 |
পুরনো অক্ষর কপি 0 + 1 + 2 + 3 বার; নতুন চারটি অক্ষরও লিখতে হয়। সাধারণভাবে মোট খরচ O(n²) হতে পারে। কিছু Python implementation বিশেষ ক্ষেত্রে += optimize করে; portable সমাধানে তার উপর নির্ভর করি না।
flowchart LR
A["a"] --> J["একবার join"]
B["b"] --> J
C["c"] --> J
D["d"] --> J
J --> O["abcd"]টুকরোগুলো list-এ জমিয়ে শেষে ''.join(parts) করলে মোট অক্ষরের সংখ্যার অনুপাতে কাজ হয়।
নিজে চেষ্টা করো: [1, 2, 3, 4] reverse করো; তারপর [2, 4, 6, 8]-এর index 1–2-এর যোগফল prefix দিয়ে বের করো। পরের পাঠ: operations ও patterns।