02 — Arrays and Strings¶

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

প্রথমে ধারণা, তারপর সম্পূর্ণ চিত্র ও ধাপে ধাপে উদাহরণ, তারপর কোন প্রশ্নে কোন pattern পড়ো। প্রয়োজন হলে operation ও খরচ পাশে রাখো। সমস্ত problem ও বাংলা নোট এবং উৎসের তালিকা সরাসরি খোলা যাবে।

ধাপ	কী শিখবে	প্রথম অনুশীলন
1	index ও in-place update	Reverse String
2	একবার scan করে তথ্য রাখা	Buy/Sell Stock
3	বারবার range query	Static Range Sum
4	window-এর শর্ত বজায় রাখা	Longest Unique Substring
5	আগের prefix মনে রাখা	Subarray Sum K
6	একাধিক pattern মেলানো	Minimum Window

প্রতিটি ধাপে আগে ছোট 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/) — বেশ কয়েকটা 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	Frequency counting / complement	নোট পড়ো
Valid Anagram — দুটো string কি একই letter ব্যবহার করে?	LeetCode 242	Frequency counting	নোট পড়ো
Reverse String — একটা char array in place reverse করো	LeetCode 344	Two pointers	নোট পড়ো
Merge Sorted Array — বড় array-টার ভেতরেই in place merge করো	LeetCode 88	Two pointers (পেছন থেকে)	নোট পড়ো
Remove Duplicates from Sorted Array	LeetCode 26	Two pointers (slow/fast)	নোট পড়ো
Best Time to Buy and Sell Stock — একবার buy, একবার sell, max profit	LeetCode 121	Running min (Kadane-ঘেঁষা)	নোট পড়ো
Watermelon — একটা weight কে দুটো জোড় ভাগে ভাঙো	Codeforces 4A	Parity / array warm-up	নোট পড়ো

Medium¶

Problem	Official task	Pattern	বাংলা ব্যাখ্যা
Maximum Subarray — contiguous run-এর সবচেয়ে বড় sum	LeetCode 53	Kadane's	নোট পড়ো
Longest Substring Without Repeating Characters	LeetCode 3	Sliding window	নোট পড়ো
Container With Most Water — দেয়ালের সেরা pair	LeetCode 11	Two pointers	নোট পড়ো
Product of Array Except Self	LeetCode 238	Prefix products	নোট পড়ো
Subarray Sum Equals K	LeetCode 560	Prefix sums + hash map	নোট পড়ো
Rotate Array — in place k ঘর ডানে shift করো	LeetCode 189	Triple-reversal	নোট পড়ো
3Sum — zero-তে sum হয় এমন সব unique triple	LeetCode 15	Sort + two pointers	নোট পড়ো
Group Anagrams — letter content অনুযায়ী word গুলো bucket করো	LeetCode 49	Frequency counting / canonical key	নোট পড়ো
Static Range Sum Queries	CSES Problem Set — "Static Range Sum Queries"	Prefix sums	নোট পড়ো

Hard¶

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

Visualization ideas¶

Array-টাকে একসারি বাক্স হিসেবে আঁকো, নিচে index লেখো; two pointers-এর জন্য রঙিন arrow নাড়াও।
Sliding window-র জন্য window-টা shade করে frame by frame সরাও।
Prefix sums-এর জন্য array-র নিচে একটা দ্বিতীয় row আঁকো যেখানে running total থাকবে।
VisuAlgo-র interactive visualizer try করো ("Array" / sorting module গুলো)।
Code চালানোর আগে 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/।

Recommended learning order¶

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

Source map¶

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