Skip to content

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:

  • Sorted input-এ two-pointer pair sum — LeetCode 167
  • Container-এর দেয়ালের সেরা pair — LeetCode 11
  • সব zero-sum triple — LeetCode 15

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'
window becomes "bca", keep growing... best stays 3

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

Representative problems:

  • Repeating character ছাড়া longest substring — LeetCode 3
  • t-এর সবকিছু cover করা minimum window — LeetCode 76
  • Fixed size k-এর যেকোনো subarray-র max sum — classic fixed-window warm-up, দেখো USACO Guide-এর sliding-window module

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:

  • In place string compression — LeetCode 443
  • Zigzag conversion (row বানাও, join করো) — LeetCode 6
  • 3[a2[c]]-এর মতো string decode — LeetCode 394 (এটা ../04-stack-and-queue/-এর stack pattern-এরও একটা preview)

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: end=max(-2, ...)=-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 চিন্তা — best ending at i মানে prefix[i] - min(prefix[0..i-1]), আর Kadane's সেই minimum-টাই implicitly track করে। অনেকের জীবনের প্রথম dynamic-programming recurrence-ও এটাই।

Representative problems:

  • Maximum subarray — LeetCode 53
  • Best time to buy and sell stock (running-min variant) — LeetCode 121
  • Maximum product subarray (min EBONG max track করো) — LeetCode 152

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 শুরু করো।