Visualization Ideas — Two Pointers ও Sliding Window¶
এই level-এর সব কৌশল নড়াচড়ার গল্প — আঙুল সরে, জানালা হাঁটে। তাই static ছবির চেয়ে "film strip" বেশি কাজের: প্রতি step-এ এক frame। এখানে আঁকার idea গুলো, আর শেষে 3টা worked ASCII example।
প্রতি concept-এর visualization idea¶
1. Opposite pointers = দুই দিক থেকে বই চাপা¶
বইয়ের তাকের দুই প্রান্তে দুই হাত। array-টা লিখে নিচে L আর R তীর বসাও; প্রতি step-এ একটা তীর এক ঘর ভেতরে। পাশের column-এ লেখো sum আর সিদ্ধান্ত (বড়/ছোট/মিলল)। তীর দুটোর মাঝের অংশ = বেঁচে থাকা search space — প্রতি frame-এ সেটা সরু হচ্ছে, এটাই O(n)-এর চোখে-দেখা প্রমাণ।
2. Same-direction = ধাওয়া¶
দুটো দৌড়বিদ একই লেনে: সামনের জন (j) ফারাক বাড়ায়, পেছনের জন (i) ফারাক কমায়। Timeline-এ দুজনের অবস্থান দাগাও — দুটো রেখাই শুধু ডানে যায়, কখনো ক্রস করে না, কখনো পিছায় না।
3. Container = দুই দেয়ালের পাত্র¶
Bar chart-এর মতো উচ্চতাগুলো আঁকো, দুই প্রান্তের দেয়ালের মাঝে পানির আয়তক্ষেত্র shade করো — উচ্চতা সবসময় ছোট দেয়াল পর্যন্ত। প্রতি step-এ ছোট দেয়ালে × চিহ্ন দিয়ে সরাও। ছবিতেই দেখা যায়: বড় দেয়াল সরালে পানির উচ্চতা একই বা কম, width-ও কম — লাভ অসম্ভব।
4. Sliding window = শুঁয়োপোকার হাঁটা¶
Array-র নিচে একটা শুঁয়োপোকা: মাথা r, লেজ l। প্রতি frame-এ মাথা এক ঘর এগোয়; শরীর বেশি মোটা (শর্ত ভাঙা) হয়ে গেলে লেজ গুটিয়ে আসে। Window-র ভেতরের ঘরগুলো bracket দিয়ে ঘেরো: [ ... ]। পাশে লিখে রাখো invariant-এর মান (sum / distinct count)।
5. Invariant মিটার¶
Window-র পাশে একটা ছোট গেজ আঁকো — যেমন sum: ▓▓▓▓░░ (6/7)। মাথা এগোলে গেজ বাড়ে, সীমা পেরোলেই লাল — তখনই লেজ টানা। "কখন shrink করব" প্রশ্নটার উত্তর গেজ-ই দেয়: invariant চোখে দেখা গেলে template আর মুখস্থের ব্যাপার থাকে না।
6. r − l + 1 গোনা = লেজ থেকে মাথা পর্যন্ত সিঁড়ি¶
Window [l..r] valid হলে r-এ শেষ হওয়া subarray গুলো আঁকো একটার নিচে একটা — সবচেয়ে লম্বাটা [l..r], তার নিচে [l+1..r], ... একদম ছোট [r..r]। একটা সিঁড়ির মতো দেখাবে; ধাপ গুনলেই r − l + 1।
7. exactly K = দুই দলের পার্থক্য¶
দুটো বৃত্ত না — দুটো তাক আঁকো: উপরের তাকে atMost(K)-এর সব subarray (distinct 1 থেকে K), নিচের তাকে atMost(K−1)-এর সব (distinct 1 থেকে K−1)। নিচের তাকের সবাই উপরের তাকেও আছে — উপর থেকে নিচ মুছে দিলে পড়ে থাকে শুধু "distinct ঠিক K" দল।
Worked ASCII example 1: opposite pointers (target = 11)¶
a = [1, 2, 4, 7, 9, 11]
frame 1: [1 2 4 7 9 11] sum = 1+11 = 12 > 11 → R--
L R
frame 2: [1 2 4 7 9 11] sum = 1+9 = 10 < 11 → L++
L R
frame 3: [1 2 4 7 9 11] sum = 2+9 = 11 ✓
L R
3 frame-এই শেষ। প্রতি frame-এ L আর R-এর মাঝের দূরত্ব কমেছে — কখনোই কেউ পেছায়নি।
Worked ASCII example 2: শুঁয়োপোকা — minimum window with sum ≥ 7¶
a = [2, 3, 1, 2, 4, 3]
r=0: [2] 3 1 2 4 3 sum=2 best=∞
r=1: [2 3] 1 2 4 3 sum=5 best=∞
r=2: [2 3 1] 2 4 3 sum=6 best=∞
r=3: [2 3 1 2] 4 3 sum=8 ≥7 → best=4
গোটাও: [3 1 2] sum=6 l=1
r=4: 2 [3 1 2 4] 3 sum=10 ≥7 → best=4
গোটাও: [1 2 4] sum=7 ≥7 → best=3
গোটাও: [2 4] sum=6 l=3
r=5: 2 3 1 [2 4 3] sum=9 ≥7 → best=3
গোটাও: [4 3] sum=7 ≥7 → best=2 ★
গোটাও: [3] sum=3 l=5
উত্তর: 2 ([4, 3])
মাথা (r) 6 বার এগিয়েছে, লেজ (l) মোট 5 বার — দুটো মিলিয়ে ≤ 2n move। এটাই O(n)-এর ছবি।
Worked ASCII example 3: atMost দিয়ে exactly (a = [1, 2, 1, 3], K = 2)¶
atMost(2): প্রতি r-এ window টেনে r-l+1 যোগ —
r=0: [1] distinct=1 +1
r=1: [1 2] distinct=2 +2
r=2: [1 2 1] distinct=2 +3
r=3: [2 1 3]→[1 3] distinct=3→2 l সরে 2-এ +2
atMost(2) = 8
atMost(1):
r=0: [1] +1 r=1: [2] +1 (l সরে)
r=2: [1] +1 r=3: [3] +1
atMost(1) = 4
exactly(2) = 8 - 4 = 4
যাচাই — distinct ঠিক 2 ওয়ালা subarray: [1,2], [2,1], [1,2,1], [1,3] → 4টা ✓
দুটো সহজ পাসের বিয়োগে কঠিন উত্তর — হাতে একবার মিলিয়ে দেখলে trick-টা আর কখনো রহস্য থাকে না।
নিজে practice করার নিয়ম¶
- প্রতিটা two pointers problem-এ frame-টেবিল বানাও: step | l | r | হিসাব | সিদ্ধান্ত — অন্তত প্রথম 5-6 step
- Window problem-এ bracket দিয়ে window আঁকো প্রতি r-এর জন্য — কোথায় লেজ টানা হলো সেটা চিহ্নিত করো
- ভুল হলে জিজ্ঞেস করো: "invariant-টা ঠিক কী ছিল, আর কোন frame-এ সেটা ভেঙেছিল?" — bug প্রায় সবসময় ওখানেই
- একটা negative number ঢুকিয়ে (যেমন
[2, -1, 3]) window চালিয়ে দেখো কোথায় যুক্তি ভাঙে — সীমাটা নিজের চোখে দেখা জরুরি