কনটেন্টে যান

Arrays and Strings — Problem-Solving Patterns

Pattern মানে আসলে চিন্তার একটা reusable আকার। Trigger word গুলো শেখো, core idea টা ধরো, আর সেই একটা mental tweak শেখো যেটা brute-force O(n^2) loop-কে একটা পরিষ্কার O(n) solution-এ বদলে দেয়।

Pattern 1 — Two Pointers

Trigger words: "pair that sums to...", "remove duplicates in place", "sorted array", "palindrome", "container / pair of walls", "move all zeros"।

Core idea: দুটো nested loop দিয়ে সব pair try করার (O(n^2)) বদলে দুটো index রাখো আর সেগুলোকে উদ্দেশ্য নিয়ে সরাও — সাধারণত দুই প্রান্ত থেকে ভেতরের দিকে, অথবা বাঁ দিক থেকে একটা slow আর একটা fast।

Thinking tweak: pointer-এর প্রতিটা move-এ কিছু candidate চিরতরে বাদ পড়তে হবে। তুমি যদি argue করতে পারো "L ডানে সরালে answer কখনো হারাতে পারি না", তাহলে তোমার হাতে একটা correct O(n) algorithm আছে।

Worked example — sorted [1, 3, 4, 6, 9]-এ 10-এ sum হয় এমন pair:

উদাহরণ
L=1, R=9 -> sum 10  FOUND.
(if sum had been < target: only moving L right can increase it;
 if sum had been > target: only moving R left can decrease it —
 each step kills one element forever, so at most n steps.)

Inherits from: সাধারণ array traversal + sorted-order invariant।

Representative problems:

Pattern 2 — Sliding Window

Trigger words: "longest/shortest substring বা subarray", "at most K distinct", "contains all characters of", "window of size k"।

Core idea: এমন একটা window [L..R] maintain করো যেটা সবসময় শর্ত মানে (বা মানার চেষ্টা করছে)। বড় করতে R expand করো; শর্ত ভাঙলেই শুধু L shrink করো। প্রতিটা index একবার ঢোকে একবার বের হয় → O(n)।

Thinking tweak: কিছু ভাঙলে কখনো window টা scratch থেকে restart করো না। বাঁ প্রান্ত sliding করে repair করো — মাঝের element গুলোর জন্য করা কাজটা এখনো valid।

Worked example — "abcabcbb"-এর repeat-ছাড়া longest substring:

উদাহরণ
grow:  a -> ab -> abc        (best = 3)
R hits second 'a': duplicate! slide L past the first 'a'
R=3: bca, L=1, best=3
R=4: cab, L=2, best=3
R=5: abc, L=3, best=3
R=6: cb,  L=5, best=3
R=7: b,   L=7, best=3

শর্তের সীমা: positive/nonnegative number-এর sum সীমা ছাড়ালে shrink করা কাজে লাগে; negative number থাকলে এই monotonic যুক্তি ভাঙতে পারে। Exact sum count করতে prefix + hash map দেখো। Minimum window-এ invalid হলে expand, valid হলে shrink — longest-valid window-এর নিয়ম সরাসরি কপি করবে না।

Inherits from: two pointers (এটা আসলে একই দিকে চলা two pointers-ই) + window-র contents-এর জন্য frequency counting।

Representative problems:

Pattern 3 — Prefix Sums

Trigger words: "sum of range [l, r]", "many queries", "count subarrays with sum K", "equilibrium / pivot index"।

Core idea: আগে থেকে হিসাব করে রাখো prefix[i] = প্রথম i-টা element-এর sum। তাহলে যেকোনো range sum নেমে আসে একটা subtraction-এ: sum(l..r) = prefix[r+1] - prefix[l]।

Thinking tweak: "subarray sum equals K" হয়ে যায় "আমি কি আগে current_prefix - K সমান কোনো prefix দেখেছি?" — দেখা prefix গুলো একটা hash map-এ রাখো, আর এক pass-এই এমন সব subarray count হয়ে যাবে।

Worked example — [1, 2, 1]-এর কয়টা subarray-র sum 3:

উদাহরণ
prefixes seen: {0:1}
running=1 -> need 1-3=-2, absent. record 1.
running=3 -> need 3-3=0, seen once! count=1. record 3.
running=4 -> need 4-3=1, seen once! count=2.       answer: 2  ([1,2] and [2,1])

Inherits from: prefix/difference/contribution chapter — পুরো derivation আর difference-array জমজটার জন্য দেখো ../01-math-based-programming-fundamentals/05-prefix-difference-contribution/।

Representative problems:

Pattern 4 — In-Place Reversal and Rotation

Trigger words: "rotate by k", "in place", "O(1) extra space", "reverse words/sections"।

Core idea: Two pointers দিয়ে reversal-এর খরচ O(n) time আর O(1) space। k দিয়ে rotation মানে তিনটা reversal: পুরো array reverse করো, তারপর প্রথম k-টা reverse করো, তারপর বাকিটা reverse করো।

Thinking tweak: rotation শুনলে মনে হয় একটা temporary array লাগবেই — কিন্তু দুইবার reverse করলে প্রতিটা block আবার forward order-এ ফিরে আসে, অথচ block দুটো নিজেদের মধ্যে জায়গা বদলে ফেলেছে।

Worked example — [1, 2, 3, 4, 5] কে ডানে k = 2 rotate করো:

উদাহরণ
reverse all:        [5, 4, 3, 2, 1]
reverse first 2:    [4, 5, 3, 2, 1]
reverse last 3:     [4, 5, 1, 2, 3]   done — the last two items moved to the front

Inherits from: Pattern 1-এর two-pointer swap।

Representative problems:

Pattern 5 — Frequency Counting

Trigger words: "anagram", "first unique", "majority", "appears exactly/at least k times", "permutation of each other"।

Core idea: এক O(n) pass-এ একটা dict-এ (বা collections.Counter-এ) occurrence count করো, তারপর বারবার re-scan না করে count গুলো থেকেই প্রশ্নের উত্তর দাও।

Thinking tweak: দুটো string anagram iff তাদের count map সমান — arrangement না, summary compare করো। Lowercase letter-এর জন্য 26-slot-এর একটা array আরো সস্তা counter।

Worked example — "listen" কি "silent"-এর anagram?

উদাহরণ
count("listen") = {l:1, i:1, s:1, t:1, e:1, n:1}
count("silent") = {s:1, i:1, l:1, e:1, n:1, t:1}
maps equal -> YES, in O(n), without trying any of the n! orderings

Inherits from: সাধারণ traversal + hash-map idea (constant-time lookup)।

Representative problems:

Pattern 6 — String Building (O(n^2) trap এড়াও)

Trigger words: "construct the result string", "transform/encode/decode", "repeat n times", যেকোনো loop যেটা একটা string বাড়াচ্ছে।

Core idea: string immutable, তাই s += piece প্রতিবার পুরো s copy করে — ওরকম একটা loop মানে O(n^2)। টুকরোগুলো একটা list-এ জমাও আর শেষে একবার ''.join করো: O(n)।

Thinking tweak: answer string-টাকে একদম শেষ মুহূর্ত পর্যন্ত frozen ধরে নাও। Final join-এর আগ পর্যন্ত সবকিছু স্রেফ fragment-এর একটা list।

Worked example — "aaabb"-এর run-length encode:

উদাহরণ
parts = []
run 'a' x3 -> parts = ["a", "3"]
run 'b' x2 -> parts = ["a", "3", "b", "2"]
"".join(parts) -> "a3b2"        every character written exactly once

Inherits from: dynamic array-র append-is-cheap property (চাইলে একে Pattern 0 বলতে পারো)।

Representative problems:

Pattern 7 — Kadane's Algorithm (maximum subarray)

Trigger words: "maximum sum of a contiguous subarray", "best segment", "maximum product subarray" (variant)।

Core idea: বাঁ থেকে ডানে হাঁটো আর রাখো best_ending_here = current index-এ শেষ হওয়া সেরা subarray। প্রতিটা element-এ choose করো: আগের run টা extend করবে, নাকি এখান থেকে fresh শুরু করবে।

Thinking tweak: negative running total মানে মরা ওজন — সামনে যা-ই আসুক সেটাকে শুধু টেনে নামাবে, তাই ওটা ফেলে দাও আর restart করো। প্রতি element-এ একটা local decision-ই global answer দিয়ে দেয়।

Worked example — [-2, 1, -3, 4, -1, 2, 1]:

উদাহরণ
x=-2: initialize end=-2, best=-2
x= 1: prev end -2 < 0 -> restart: end=1     best=1
x=-3: end=1-3=-2                   best=1
x= 4: prev end -2 < 0 -> restart: end=4     best=4
x=-1: end=4-1=3                    best=4
x= 2: end=3+2=5                    best=5
x= 1: end=5+1=6                    best=6   -> answer 6 (subarray [4,-1,2,1])

Inherits from: prefix-sum চিন্তা — prefix[j] প্রথম j-টি element-এর sum হলে best ending at i = prefix[i+1] - min(prefix[0..i]), আর Kadane's সেই minimum-টাই implicitly track করে। অনেকের জীবনের প্রথম dynamic-programming recurrence-ও এটাই।

Representative problems:

Pattern cheat sheet

Pattern Killer trigger Brute force-কে হারায় কারণ
Two pointers "pair/triple in sorted data", "in place" প্রতিটা move candidate চিরতরে বাদ দেয়
Sliding window "longest/shortest sub*" restart না, repair করো
Prefix sums "range sum", "subarrays summing to K" একবার precompute, উত্তর O(1)-এ
Reversal/rotation "rotate by k, O(1) space" তিনটা reversal temp array-র জায়গা নেয়
Frequency counting "anagram/unique/majority" arrangement না, summary compare
String building string বাড়ানো যেকোনো loop join প্রতিটা char একবারই copy করে, n বার না
Kadane's "max contiguous sum" negative prefix greedily ফেলে দাও

এবার implementation.py-র from-scratch build গুলো পড়ো, তারপর problems/README.md-তে tracker শুরু করো।