Skip to content

02 — Arrays and Strings

সবচেয়ে fundamental data structure: memory-তে পাশাপাশি বসে থাকা একসারি বাক্স।

এই data structure টা কী

Array হলো fixed-size, ordered একটা collection যেখানে সব item memory-র একটা continuous block-এ পাশাপাশি থাকে। প্রতিটা item-এর একটা index আছে (0, 1, 2, ...), আর তুমি যেকোনো index-এ এক লাফে পৌঁছে যেতে পারো।

String আসলে ভেতরে ভেতরে character-দের array। প্রায় সব 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। Scan করার জন্য array-ই সবচেয়ে দ্রুত structure, ব্যস।

আসল software-এ কোথায় ব্যবহার হয়

  • তুমি যে image দেখো, প্রতিটাই pixel-এর একটা 2D array।
  • Audio হলো sample-এর array; video হলো frame-এর array।
  • Database-এর row, spreadsheet-এর column, CSV file — সবই array।
  • 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 কীভাবে double হয় আর 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"

Practice list

নিচের সব problem statement আমাদের নিজের ভাষায় লেখা; official statement-এর জন্য link follow করো। Difficulty label গুলো মোটামুটি একটা ধারণা মাত্র।

Easy

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

Source map

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