Two pointer আর sliding window — জোড়ার লুপ O(n²) থেকে O(n)

১ · জোড়া খোঁজার সমস্যা — দুই লুপ থেকে দুই আঙুল

ধরুন নীলক্ষেতের একটি বইয়ের দোকানে আপনার হাতে ঠিক ২৪০ টাকা। আপনি ঠিক দুটি বই কিনতে চান, যাদের দাম মিলিয়ে পুরো ২৪০ — এক টাকাও বেশি বা কম নয়। দোকানদার একটি তালিকা দিলেন, যেখানে বইয়ের দাম ছোট থেকে বড় সাজানো। কীভাবে খুঁজবেন?

সবচেয়ে সরল উপায়: প্রথম বইটি নিয়ে বাকি সব বইয়ের সাথে মিলিয়ে দেখুন, তারপর দ্বিতীয় বই নিয়ে আবার সবার সাথে… এটি brute force. n টি বই হলে জোড়া n(n − 1)/2 টি, অর্থাৎ quadratic time, Θ(n²). দশ হাজার বইয়ে প্রায় পাঁচ কোটি জোড়া; দশ লাখ বইয়ে প্রায় পঞ্চাশ হাজার কোটি — কনটেস্টের এক সেকেন্ডের সময়সীমায় অসম্ভব।

// brute force: every pair (i, j), i < j — Θ(n²) comparisons
for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j)
        if (a[i] + a[j] == target) return {i, j};

কিন্তু তালিকাটি যে সাজানো, এই তথ্য brute force একটুও কাজে লাগায়নি। এবার দুই বন্ধুর কথা ভাবুন। একজন তালিকার একেবারে শুরুতে (সবচেয়ে সস্তা বই), আরেকজন একেবারে শেষে (সবচেয়ে দামি বই)। দুজনের বইয়ের দাম যোগ করুন:

• যোগফল ২৪০-এর কম হলে — যোগফল বাড়াতে হবে। দামি বইয়ের বন্ধু আর ডানে যেতে পারেন না (তার চেয়ে দামি বই নেই), তাই সস্তা বইয়ের বন্ধু এক ঘর ডানে যান।
• যোগফল ২৪০-এর বেশি হলে — যোগফল কমাতে হবে, তাই দামি বইয়ের বন্ধু এক ঘর বাঁয়ে আসেন।
• ঠিক ২৪০ হলে — পাওয়া গেছে!

প্রতিটি তুলনার পর একজন বন্ধু এক ঘর ভেতরে আসেন, আর কেউ কখনো পিছনে ফেরেন না। দুজন মুখোমুখি হলে খোঁজা শেষ। তাই মোট তুলনা সর্বোচ্চ n − 1 টি — Θ(n²) থেকে O(n)!

এটাই two pointer কৌশল। এখানে “pointer” মানে C-র মেমরি pointer নয় — শুধু একটি index ভ্যারিয়েবল, যা অ্যারের কোনো একটি ঘর দেখিয়ে রাখে। কৌশলটির প্রাণ একটি শর্ত:

এই একটি ধারণা থেকে দুটি পরিবার জন্মায়, যাদের এই পর্বে একে একে দেখব:

২ · বিপরীত প্রান্তের pointer — sorted array-এ pair sum

বইয়ের দোকানের সমস্যাটিকে অ্যালগরিদমের ভাষায় লিখি। ইনপুট: ছোট থেকে বড় সাজানো একটি অ্যারে a[0..n−1] আর একটি লক্ষ্য T. খুঁজতে হবে এমন দুটি index i < j, যাতে a[i] + a[j] = T. এই সমস্যাকে সাধারণত two-sum বা pair sum বলা হয়। Pseudocode (0-based index):

Pseudocode (pair sum on a sorted array, 0-based)

PAIR-SUM(a[0..n-1], T):            // a is sorted ascending
    L = 0, R = n - 1
    while L < R:
        s = a[L] + a[R]
        if s == T: return (L, R)
        if s < T:  L = L + 1          // a[L] is too small for every partner left
        else:      R = R - 1          // a[R] is too big for every partner left
    return NOT FOUND

নিচে a = [2, 5, 7, 9, 12, 15, 18, 21] আর T = 24 নিয়ে অ্যালগরিদমটি ধাপে ধাপে চালানো হলো। “out” সারিতে x মানে সেই উপাদানটি বাদ পড়েছে — তাকে আর কোনো জোড়ায় দেখা হবে না। “পরে” চাপুন:

বিশ্লেষণ। প্রতিটি ধাপে হয় উত্তর মেলে, নয়তো R − L ঠিক ১ কমে। শুরুতে R − L = n − 1, আর L < R থাকা পর্যন্ত লুপ চলে — তাই সর্বোচ্চ n − 1 টি ধাপ, প্রতিটিতে O(1) কাজ: সময় O(n), বাড়তি জায়গা O(1). অ্যারে আগে থেকে সাজানো না থাকলে প্রথমে sort করতে হয় — তখন মোট O(n log n). (না সাজিয়ে hash set দিয়েও গড়ে O(n)-এ করা যায়: প্রতিটি x-এর জন্য দেখুন T − x আগে দেখা হয়েছে কি না — hash table নিয়ে পর্ব ৩২-এ বিস্তারিত।)

৩ · কেন কোনো জোড়া হারায় না — শুদ্ধতার প্রমাণ

অনেকে প্রথমবার এই কৌশল দেখে অস্বস্তিতে পড়েন: “আমরা তো বেশিরভাগ জোড়া দেখলামই না! যদি (5, 19)-এর মতো কোনো জোড়া মাঝখানে লুকিয়ে থাকত?” প্রশ্নটি একদম ঠিক — আর এর উত্তর একটি loop invariant (পর্ব ০৩):

• শুরুতে সত্য: L = 0, R = n − 1 — পুরো অ্যারেই খোঁজার অংশ।
• যোগফল ছোট হলে (a[L] + a[R] < T): খোঁজার অংশে L-এর যেকোনো সঙ্গী j-এর জন্য j ≤ R, আর অ্যারে সাজানো বলে a[j] ≤ a[R]. তাহলে a[L] + a[j] ≤ a[L] + a[R] < T. অর্থাৎ বাকি অংশে a[L]-কে নিয়ে কোনো জোড়াই T হতে পারে না। তাই i* ≠ L, মানে i* ≥ L + 1 — L বাড়ালেও invariant টিকে থাকে।
• যোগফল বড় হলে: একই যুক্তি উল্টো দিকে। যেকোনো i ≥ L-এর জন্য a[i] + a[R] ≥ a[L] + a[R] > T, তাই j* ≠ R — R কমানো নিরাপদ।
• শেষে: লুপ থামে হয় উত্তর পেয়ে, নয়তো L ≥ R হলে। দ্বিতীয় ক্ষেত্রে খোঁজার অংশে দুটি আলাদা index-ই নেই; invariant বলছে সমাধান থাকলে সেটি এই অংশেই থাকত — তাই কোনো সমাধান নেই। “NOT FOUND” উত্তরটি ঠিক।

একটি ছবিতে ভাবলে আরও পরিষ্কার হয়। সব জোড়া (i, j)-কে একটি n × n ছকে সাজান — সারি i, কলাম j. Brute force ছকের প্রতিটি ঘর দেখে। Two pointer প্রতিটি তুলনায় একটি পুরো সারি (L বাদ) বা একটি পুরো কলাম (R বাদ) একসাথে বাতিল করে — কারণ সাজানো ক্রম বলে দেয় সেই সারি বা কলামের সব ঘরের যোগফল একই দিকে ভুল। তাই n − 1 টি তুলনায় পুরো ছক শেষ।

এবার কোডে চালিয়ে দেখুন। তিনটি লক্ষ্যের জন্য একই অ্যারেতে কতগুলো ধাপ লাগে, তা-ও গোনা হচ্ছে:

#include <iostream>
#include <vector>
#include <utility>
#include <initializer_list>
using namespace std;

// a is sorted ascending; returns (i, j), i < j, with a[i] + a[j] == target
pair<int, int> pairSum(const vector<int>& a, int target, int& steps) {
    int L = 0, R = (int)a.size() - 1;
    steps = 0;
    while (L < R) {
        ++steps;
        int s = a[L] + a[R];
        if (s == target) return {L, R};
        if (s < target) ++L;      // a[L] is too small for every remaining partner
        else --R;                 // a[R] is too big for every remaining partner
    }
    return {-1, -1};
}

int main() {
    vector<int> a{2, 5, 7, 9, 12, 15, 18, 21};
    int n = (int)a.size();
    for (int t : {24, 33, 10}) {
        int steps = 0;
        auto [i, j] = pairSum(a, t, steps);
        cout << "target " << t << ": ";
        if (i == -1) cout << "no pair";
        else cout << a[i] << " + " << a[j] << " (i=" << i << ", j=" << j << ")";
        cout << "  steps = " << steps << "  (brute force: up to " << n * (n - 1) / 2 << " pairs)\n";
    }
}

target 24: 9 + 15 (i=3, j=5)  steps = 6  (brute force: up to 28 pairs)
target 33: 12 + 21 (i=4, j=7)  steps = 5  (brute force: up to 28 pairs)
target 10: no pair  steps = 7  (brute force: up to 28 pairs)

def pair_sum(a, target):
    """a is sorted ascending; returns (i, j, steps) with a[i] + a[j] == target."""
    L, R, steps = 0, len(a) - 1, 0
    while L < R:
        steps += 1
        s = a[L] + a[R]
        if s == target:
            return L, R, steps
        if s < target:
            L += 1          # a[L] is too small for every remaining partner
        else:
            R -= 1          # a[R] is too big for every remaining partner
    return -1, -1, steps

a = [2, 5, 7, 9, 12, 15, 18, 21]
n = len(a)
for t in (24, 33, 10):
    i, j, steps = pair_sum(a, t)
    found = "no pair" if i == -1 else f"{a[i]} + {a[j]} (i={i}, j={j})"
    print(f"target {t}: {found}  steps = {steps}  (brute force: up to {n * (n - 1) // 2} pairs)")

target 24: 9 + 15 (i=3, j=5)  steps = 6  (brute force: up to 28 pairs)
target 33: 12 + 21 (i=4, j=7)  steps = 5  (brute force: up to 28 pairs)
target 10: no pair  steps = 7  (brute force: up to 28 pairs)

৪ · একই ছাঁচে আরও সমস্যা — 3-sum, পানির পাত্র, palindrome

3-sum — একটি লুপ + two pointer = O(n²)

এবার তিনটি সংখ্যা: অ্যারেতে এমন সব আলাদা ত্রয়ী খুঁজুন, যাদের যোগফল 0. এটি 3-sum সমস্যা। তিন লুপের brute force Θ(n³). কৌশল: অ্যারে sort করুন, তারপর প্রথম সংখ্যা a[i] স্থির রেখে বাকি অংশ a[i+1..n−1]-এ লক্ষ্য −a[i]-এর জন্য pair sum চালান। প্রতিটি i-তে two pointer O(n), i আছে n টি — মোট O(n²), sort-এর O(n log n) তার তুলনায় নগণ্য।

// all distinct triplets with sum 0: sort, then two pointers for each i — O(n²)
vector<array<int, 3>> threeSum(vector<int> a) {
    sort(a.begin(), a.end());
    vector<array<int, 3>> res;
    int n = (int)a.size();
    for (int i = 0; i + 2 < n; ++i) {
        if (i > 0 && a[i] == a[i - 1]) continue;       // same first value: skip
        int L = i + 1, R = n - 1;
        while (L < R) {
            int s = a[i] + a[L] + a[R];
            if (s < 0) ++L;
            else if (s > 0) --R;
            else {
                res.push_back({a[i], a[L], a[R]});
                ++L; --R;
                while (L < R && a[L] == a[L - 1]) ++L;  // skip a repeated second value
            }
        }
    }
    return res;
}
// threeSum({-1, 0, 1, 2, -1, -4}) -> {-1, -1, 2} {-1, 0, 1}

সবচেয়ে বেশি ভুল হয় duplicate সামলাতে। sort-এর পরে অ্যারে হয় [−4, −1, −1, 0, 1, 2]. i = 1 (−1) থেকে আমরা {−1, −1, 2} আর {−1, 0, 1} পাই; i = 2-তেও প্রথম সংখ্যা −1, তাই continue না থাকলে {−1, 0, 1} আবার আসত। একইভাবে উত্তর পাওয়ার পর L-কে সব সমান মান পার করিয়ে নিতে হয়। এই দুটি লাইন বাদ দিলে কোড “চলে”, কিন্তু একই ত্রয়ী একাধিকবার ছাপে — ইন্টারভিউতে এটিই সবচেয়ে প্রচলিত ভুল।

Container with most water — খাটো দেয়ালটি সরান

একটি অ্যারে h[0..n−1]-এ প্রতিটি সংখ্যা একটি খাড়া দেয়ালের উচ্চতা, পাশাপাশি এক ঘর দূরে দূরে। যেকোনো দুটি দেয়াল i < j বেছে নিলে মাঝে পানি ধরে (j − i) × min(h[i], h[j]) পরিমাণ — প্রস্থ × খাটো দেয়ালের উচ্চতা। সবচেয়ে বেশি পানি কোন জোড়ায়? এখানে অ্যারে সাজানো নয়, তবু two pointer কাজ করে:

int maxWater(const vector<int>& h) {
    int L = 0, R = (int)h.size() - 1, best = 0;
    while (L < R) {
        best = max(best, (R - L) * min(h[L], h[R]));
        if (h[L] < h[R]) ++L;      // the shorter wall limits every narrower pair
        else --R;
    }
    return best;
}
// maxWater({1, 8, 6, 2, 5, 4, 8, 3, 7}) -> 49   (walls at index 1 and 8: 7 * min(8, 7))

কেন খাটো দেয়ালটিই সরানো নিরাপদ? ধরুন h[L] ≤ h[R]. L-কে বাকি যেকোনো দেয়াল j (L < j < R)-এর সাথে জোড়া দিলে প্রস্থ (j − L) < (R − L), আর উচ্চতা min(h[L], h[j]) ≤ h[L]. তাই পানি ≤ (R − L) × h[L] = এখনকার জোড়ার পানি, যা আমরা ইতিমধ্যে best-এ নিয়েছি। অর্থাৎ L-এর আর কোনো ভালো সঙ্গী বাকি নেই — একে বাদ দেওয়া নিরাপদ। লম্বা দেয়ালটি সরালে এই যুক্তি খাটে না: সেটি অন্য কোনো লম্বা দেয়ালের সাথে মিলে বেশি পানি ধরতে পারে। এটি একটি ছোট greedy সিদ্ধান্ত, যার পেছনে আছে পরিষ্কার “বাদ দেওয়ার” প্রমাণ — পর্ব ৫০-এ greedy-র প্রমাণ নিয়ে আরও বিস্তারিত দেখবেন।

Palindrome যাচাই আর উল্টানো — সবচেয়ে সরল রূপ

“madam”, “racecar”, “নয়ন” (ন-য়-ন) — যে শব্দ সামনে-পেছনে একই, তা palindrome. যাচাই করতে দুই প্রান্ত থেকে একটি করে অক্ষর মিলিয়ে ভেতরে আসুন; অমিল পেলেই উত্তর “না”। অ্যারে উল্টাতেও একই চলন — শুধু তুলনার বদলে swap. দুটিতেই প্রায় n/2 ধাপ, O(n) সময়, O(1) বাড়তি জায়গা — অর্থাৎ in-place.

bool isPalindrome(const string& s) {
    int L = 0, R = (int)s.size() - 1;
    while (L < R)
        if (s[L++] != s[R--]) return false;   // compare the two ends, move both inward
    return true;
}

void reverseInPlace(vector<int>& a) {
    for (int L = 0, R = (int)a.size() - 1; L < R; ++L, --R)
        swap(a[L], a[R]);
}

৫ · একই দিকে দুই pointer — duplicate সরানো আর merge

দ্বিতীয় পরিবারে দুটি pointer-ই বাঁ থেকে ডানে যায়, কিন্তু আলাদা গতিতে। একটি সাধারণ নাম fast/slow pointer: fast প্রতিটি ধাপে এক ঘর এগিয়ে নতুন উপাদান “পড়ে”, আর slow শুধু তখনই এগোয় যখন কিছু “লেখার” মতো পাওয়া যায়। পরীক্ষার খাতা দেখার মতো ভাবুন: একজন শিক্ষক (fast) প্রতিটি খাতা পড়ছেন, আর একজন সহকারী (slow) শুধু পাস করা খাতাগুলো নতুন স্তূপে সাজাচ্ছেন।

Sorted array থেকে duplicate সরানো, in-place

// sorted a: keep one copy of each value at the front, return how many
int removeDuplicates(vector<int>& a) {
    if (a.empty()) return 0;
    int slow = 1;                              // a[0..slow-1] = distinct values so far
    for (int fast = 1; fast < (int)a.size(); ++fast)
        if (a[fast] != a[slow - 1])            // a new value: write it
            a[slow++] = a[fast];
    return slow;
}
// {1, 1, 2, 2, 2, 3, 5, 5} -> returns 4, front becomes 1 2 3 5

Invariant: প্রতিটি ঘূর্ণনের শুরুতে a[0..slow−1]-এ এ পর্যন্ত দেখা (a[0..fast−1]) সব আলাদা মান ক্রমানুসারে একবার করে আছে। অ্যারে সাজানো বলে একই মানের সব কপি পাশাপাশি থাকে, তাই নতুন মান চেনার জন্য শুধু শেষ লেখা মান a[slow − 1]-এর সাথে তুলনাই যথেষ্ট। fast ঠিক n − 1 বার এগোয়, slow তার চেয়ে কম — সময় Θ(n), বাড়তি জায়গা O(1). নতুন অ্যারে বানিয়ে করলে জায়গা লাগত O(n). লেখার পরে অ্যারের পেছনের অংশে পুরোনো মান থেকে যায় (উদাহরণে পুরো অ্যারে হয় [1, 2, 3, 5, 2, 3, 5, 5]); তাই ফাংশন নতুন দৈর্ঘ্য ফেরত দেয়। C++-এর std::unique ঠিক এই কাজটিই করে (STL algorithms দেখুন)।

দুটি sorted array merge করা

দুটি আলাদা ক্লাসের রোল-তালিকা, দুটিই নম্বর অনুযায়ী সাজানো — একটি সম্মিলিত সাজানো তালিকা চাই। প্রতিটি তালিকার শুরুতে একটি করে আঙুল রাখুন; দুই আঙুলের নিচের ছোট সংখ্যাটি নতুন তালিকায় লিখে সেই আঙুলটি এগিয়ে দিন। এটিই merge:

vector<int> mergeSorted(const vector<int>& a, const vector<int>& b) {
    vector<int> out;
    out.reserve(a.size() + b.size());
    size_t i = 0, j = 0;
    while (i < a.size() && j < b.size())
        out.push_back(a[i] <= b[j] ? a[i++] : b[j++]);   // <= keeps equal keys in order
    while (i < a.size()) out.push_back(a[i++]);         // copy what is left
    while (j < b.size()) out.push_back(b[j++]);
    return out;
}
// mergeSorted({1, 4, 9}, {2, 3, 10, 12}) -> 1 2 3 4 9 10 12

প্রতিটি তুলনায় একটি উপাদান চূড়ান্ত জায়গায় যায়, তাই তুলনা সর্বোচ্চ n + m − 1 টি, মোট সময় Θ(n + m). দুই অ্যারের প্রতিটি জোড়া তুলনা করার কোনো দরকারই হয়নি। <= চিহ্নটি গুরুত্বপূর্ণ: সমান হলে প্রথম অ্যারের উপাদান আগে যায়, ফলে সমান key-গুলোর মূল ক্রম বজায় থাকে (stable). এই merge-ই পর্ব ২১-এর merge sort-এর হৃদপিণ্ড।

৬ · Dutch national flag — এক পাসে তিন ভাগ

একটি অ্যারেতে শুধু তিন ধরনের মান: 0, 1 আর 2. এদের এক পাসে, বাড়তি অ্যারে ছাড়া, সাজাতে হবে — সব 0 আগে, তারপর 1, শেষে 2. গুনে নিয়ে আবার লিখে দেওয়া (counting) যায়, কিন্তু মানগুলো যদি আসলে বড় record হয় (যেমন “লাল/সাদা/নীল” লেবেলের গ্রাহক তালিকা), তাহলে সরাসরি ভাগ করে সাজানোই দরকার। একে বলে partition — একটি মাপকাঠি অনুযায়ী অ্যারেকে কয়েকটি ভাগে সাজানো।

সমাধানে তিনটি pointer: lo, mid, hi. এরা অ্যারেকে চারটি অঞ্চলে ভাগ করে রাখে — আর পুরো অ্যালগরিদম হলো এই invariant বজায় রেখে মাঝের “অজানা” অঞ্চলটি শূন্য করা:

// sort an array of 0s, 1s and 2s in one pass (Dijkstra's Dutch national flag)
void dutchFlag(vector<int>& a) {
    int lo = 0, mid = 0, hi = (int)a.size() - 1;
    while (mid <= hi) {                         // the unknown zone a[mid..hi] is not empty
        if (a[mid] == 0) swap(a[lo++], a[mid++]);   // 0 joins the left zone
        else if (a[mid] == 1) ++mid;                // 1 is already in place
        else swap(a[mid], a[hi--]);                 // 2 goes right; new a[mid] is unseen
    }
}

নিচে a = [1, 2, 0, 2, 1, 0] নিয়ে পুরো চলন দেখুন। “zone” সারিতে প্রতিটি ঘরের অঞ্চল: 0, 1, 2 = নিশ্চিত অঞ্চল, ? = এখনো অজানা।

শুদ্ধতা আর খরচ। তিনটি শাখার প্রতিটি invariant বজায় রাখে (stepper-এর ক্যাপশনে প্রতিটি দেখানো হয়েছে)। প্রতিটি ঘূর্ণনে অজানা অঞ্চলের দৈর্ঘ্য hi − mid + 1 ঠিক ১ কমে, তাই লুপ ঠিক n বার চলে: সময় Θ(n), বাড়তি জায়গা O(1). শেষে অজানা অঞ্চল খালি, তাই invariant নিজেই বলে দেয় অ্যারে সাজানো। এখানে সবচেয়ে সূক্ষ্ম বিষয় হলো 2-এর শাখায় mid না বাড়ানো — AI-এর লেখা কোডে এই ভুলটি মাঝে মাঝে দেখা যায়, আর তখন [1, 2, 0]-এর মতো ছোট ইনপুটেই ভুল ফল আসে ([0, 1, 2] হওয়ার কথা, কিন্তু ভুল কোড দেয় [1, 0, 2] — ডান থেকে আসা 0-টি আর যাচাই হয় না)।

এটি নিছক ধাঁধা নয়। Quick sort-এ অনেক সমান মান থাকলে pivot-এর চারপাশে “ছোট / সমান / বড়” তিন ভাগে ভাগ করাই (3-way partition) সবচেয়ে কার্যকর — ঠিক এই অ্যালগরিদম, যেখানে 0 = pivot-এর চেয়ে ছোট, 1 = সমান, 2 = বড়। পর্ব ২২-এ quick sort-এর সাথে এটি আবার দেখবেন।

৭ · Fixed sliding window — k ঘরের জানালা

একটি টি-টোয়েন্টি ম্যাচে প্রতিটি ওভারের রান একটি অ্যারেতে আছে। ধারাভাষ্যকার জানতে চান: “পরপর কোন ৩ ওভারে ব্যাটিং দল সবচেয়ে বেশি রান তুলেছে?” সরল উপায়ে প্রতিটি শুরুর ওভার থেকে ৩টি সংখ্যা যোগ করুন — n − k + 1 টি অবস্থান, প্রতিটিতে k টি যোগ: O(n·k). k বড় হলে (ধরুন n = 10⁵, k = 5 × 10⁴) এটি O(n²)-এর কাছাকাছি।

পর্যবেক্ষণ: পাশাপাশি দুটি window-এর মধ্যে k − 1 টি উপাদান একই! window এক ঘর ডানে সরালে শুধু একটি নতুন উপাদান ঢোকে (ডানে), আর একটি পুরোনো উপাদান বের হয় (বাঁয়ে)। তাই পুরো যোগফল আবার হিসাব না করে শুধু হালনাগাদ করুন:

এটাই fixed sliding window: k দৈর্ঘ্যের একটি জানালা, যা ট্রেনের জানালার মতো এক ঘর এক ঘর করে সামনে সরে — বাঁয়ের দৃশ্য বেরিয়ে যায়, ডানে নতুন দৃশ্য আসে। নিচে a = [4, 2, 7, 1, 8, 3, 6] আর k = 3-এ দেখুন। “chg” সারিতে − মানে যে উপাদান বের হলো, + মানে যে ঢুকল:

// max sum of k consecutive elements (1 <= k <= n): O(n) time, O(1) extra space
long long maxWindowSum(const vector<int>& a, int k) {
    long long sum = 0;
    for (int i = 0; i < k; ++i) sum += a[i];          // the first window
    long long best = sum;
    for (int r = k; r < (int)a.size(); ++r) {
        sum += a[r] - a[r - k];                        // a[r] enters, a[r-k] leaves
        best = max(best, sum);
    }
    return best;
}

গড় (average) চাইলে একই কোডে শুধু sum / k — যেমন সাত দিনের চলমান গড় তাপমাত্রা, বা শেয়ারবাজারের চার্টে “moving average”. sum-কে long long রাখা ইচ্ছাকৃত: 10⁵ টি সংখ্যা, প্রতিটি 10⁹ পর্যন্ত হলে যোগফল int-এর সীমা (প্রায় 2.1 × 10⁹) সহজেই ছাড়ায়।

৮ · Variable sliding window — ডানে বাড়ান, বাঁয়ে ছোট করুন

অনেক সমস্যায় window-এর দৈর্ঘ্য আগে থেকে জানা থাকে না — সেটিই আসলে প্রশ্ন। যেমন: “একটি string-এর সবচেয়ে লম্বা কোন substring-এ কোনো অক্ষর দুবার নেই?” বা “যোগফল অন্তত S হয় এমন সবচেয়ে ছোট subarray কত লম্বা?” (subarray আর substring দুটোই মানে পাশাপাশি উপাদানের একটি টানা অংশ, যেমন a[L..R].) সব টানা অংশ আছে n(n + 1)/2 টি — brute force কমপক্ষে Θ(n²).

Variable window-এর কৌশল: দুটি pointer L আর R, window = a[L..R]. R প্রতি ধাপে ডানে এক ঘর বাড়ে (নতুন উপাদান ঢোকে)। window কোনো শর্ত ভাঙলে (“অবৈধ” হলে) L-কে ডানে সরিয়ে বাঁ দিক থেকে উপাদান বের করুন, যতক্ষণ না আবার বৈধ হয়। প্রতিবার বৈধ window পেলে উত্তর হালনাগাদ করুন। ঢাকার রাস্তায় বাসের মতো ভাবুন: সামনের দরজা দিয়ে যাত্রী ওঠে (R), বাস বেশি ভরে গেলে পেছনের দরজা দিয়ে নামাতে হয় (L) — কেউ কখনো উল্টো দিকে যায় না।

Pseudocode (variable sliding window template, 0-based)

L = 0
for R = 0 to n - 1:
    add a[R] to the window                 // expand right
    while the window a[L..R] is invalid:
        remove a[L] from the window        // shrink left
        L = L + 1
    update the answer using a[L..R]        // the window is valid here

এই টেমপ্লেট তখনই ঠিক, যখন শর্তটি একমুখী (monotone): একটি বৈধ window-এর যেকোনো ছোট টানা অংশও বৈধ। “কোনো অক্ষর দুবার নেই” — এই শর্তে একটি বৈধ অংশ থেকে কিছু বাদ দিলে সেটি বৈধই থাকে। তাই R স্থির রেখে L সবচেয়ে কম যতটুকু সরালে বৈধ হয়, সেটিই R-এ শেষ হওয়া সবচেয়ে লম্বা বৈধ window; আর পরের R-এর জন্য L-কে কখনো পিছিয়ে আনার দরকার নেই, কারণ বাঁয়ের অংশটি অবৈধ ছিল বলে আরও লম্বা window-ও অবৈধ হবে।

Longest substring without repeating characters

নিচে s = "pwwkew"-এ টেমপ্লেটটি চালানো হলো। window-এ কোন কোন অক্ষর আছে, “set” সারিতে দেখুন:

Amortized O(n) — ভেতরের while লুপ থাকলেও কেন n² নয়? কোডে একটি for-এর ভেতরে একটি while দেখে অনেকে সরাসরি “O(n²)” বলে দেন। কিন্তু গুনে দেখুন: while-এর প্রতিটি ঘূর্ণনে L ঠিক ১ বাড়ে, আর L কখনো কমে না এবং n-এর বেশি হতে পারে না। তাই পুরো প্রোগ্রাম জুড়ে while সব মিলিয়ে সর্বোচ্চ n বার চলে — কোনো একটি R-এ বেশি চললে অন্যগুলোতে কম। প্রতিটি উপাদান window-এ একবার ঢোকে (R পেরোনোর সময়) আর সর্বোচ্চ একবার বের হয় (L পেরোনোর সময়)। মোট কাজ ≤ 2n টি ঢোকা-বের হওয়া, প্রতিটি O(1) — সময় O(n). একক কোনো ধাপ ব্যয়বহুল হলেও গড়ে প্রতি ধাপ O(1) — এই ধরনের হিসাবকে বলে amortized analysis, যার আনুষ্ঠানিক পদ্ধতিগুলো পর্ব ৬০-এ দেখবেন।

জায়গা: window-এ কোন অক্ষর কতবার আছে তা রাখতে একটি গণনা-টেবিল লাগে। ASCII-র জন্য ২৫৬ ঘরের অ্যারে — O(Σ), যেখানে Σ = বর্ণমালার আকার; hash map ব্যবহার করলে O(min(n, Σ)). এবার আসল কোড, ছয়টি ইনপুটে:

#include <iostream>
#include <string>
#include <array>
#include <utility>
#include <initializer_list>
using namespace std;

// {start, length} of the first longest substring with all distinct characters
pair<int, int> longestDistinct(const string& s) {
    array<int, 256> cnt{};                   // count of each character inside the window
    int L = 0, bestLen = 0, bestStart = 0;
    for (int R = 0; R < (int)s.size(); ++R) {
        unsigned char c = s[R];
        ++cnt[c];                             // expand: s[R] enters
        while (cnt[c] > 1) {                  // shrink until the window is valid again
            --cnt[(unsigned char)s[L]];
            ++L;
        }
        if (R - L + 1 > bestLen) { bestLen = R - L + 1; bestStart = L; }
    }
    return {bestStart, bestLen};
}

int main() {
    for (string s : {"abcabcbb", "bbbbb", "pwwkew", "", "dvdf", "abba"}) {
        auto [st, len] = longestDistinct(s);
        cout << '"' << s << "\" -> " << len << " \"" << s.substr(st, len) << "\"\n";
    }
}

"abcabcbb" -> 3 "abc"
"bbbbb" -> 1 "b"
"pwwkew" -> 3 "wke"
"" -> 0 ""
"dvdf" -> 3 "vdf"
"abba" -> 2 "ab"

def longest_distinct(s):
    """(start, length) of the first longest substring with all distinct characters."""
    cnt = {}                         # character -> count inside the window
    L = best_len = best_start = 0
    for R, c in enumerate(s):
        cnt[c] = cnt.get(c, 0) + 1   # expand: s[R] enters
        while cnt[c] > 1:            # shrink until the window is valid again
            cnt[s[L]] -= 1
            L += 1
        if R - L + 1 > best_len:
            best_len, best_start = R - L + 1, L
    return best_start, best_len

for s in ["abcabcbb", "bbbbb", "pwwkew", "", "dvdf", "abba"]:
    st, n = longest_distinct(s)
    print(f'"{s}" -> {n} "{s[st:st + n]}"')

"abcabcbb" -> 3 "abc"
"bbbbb" -> 1 "b"
"pwwkew" -> 3 "wke"
"" -> 0 ""
"dvdf" -> 3 "vdf"
"abba" -> 2 "ab"

Smallest subarray with sum ≥ S — বৈধ হলে ছোট করার চেষ্টা

এবার উল্টো প্রশ্ন: সবচেয়ে ছোট window চাই। ধনাত্মক সংখ্যার অ্যারেতে যোগফল অন্তত S হয় এমন সবচেয়ে ছোট টানা অংশের দৈর্ঘ্য বের করুন। এখানে “বৈধ” মানে sum ≥ S, আর বৈধ থাকাকালীনই L সরিয়ে ছোট করার চেষ্টা করি:

// smallest length of a subarray with sum >= S (all a[i] > 0); 0 if none
int minLenAtLeast(const vector<int>& a, long long S) {
    int L = 0, best = INT_MAX;
    long long sum = 0;
    for (int R = 0; R < (int)a.size(); ++R) {
        sum += a[R];                       // expand
        while (sum >= S) {                 // valid: record it, then try a shorter one
            best = min(best, R - L + 1);
            sum -= a[L++];                 // shrink
        }
    }
    return best == INT_MAX ? 0 : best;
}
// minLenAtLeast({2, 3, 1, 2, 4, 3}, 7) -> 2   (the subarray 4, 3)

যুক্তি একই: সব সংখ্যা ধনাত্মক বলে window-এ উপাদান যোগ করলে sum বাড়ে, বাদ দিলে কমে — একমুখী। কোনো R-এ a[L..R] বৈধ হলে, পরের কোনো R′ > R-এর জন্য L থেকে শুরু হওয়া window আরও লম্বা, তাই সেটি কখনো ভালো উত্তর নয় — L সামনে এগোনো নিরাপদ। সময় amortized O(n), জায়গা O(1).

At most K distinct — শর্ত বদলালেই নতুন সমস্যা

“সবচেয়ে লম্বা কোন substring-এ সর্বোচ্চ K টি ভিন্ন অক্ষর আছে?” বাজারের সারির দোকানের মতো ভাবুন — একটি টানা অংশ থেকে কেনাকাটা করবেন, কিন্তু ব্যাগ আছে মাত্র K টি, প্রতিটি ব্যাগে এক রকম জিনিস। টেমপ্লেট হুবহু এক, শুধু “অবৈধ” মানে বদলায়: ভিন্ন অক্ষরের সংখ্যা K ছাড়ালে। গণনা 0 হয়ে গেলে অক্ষরটি dict থেকে মুছে দিতে হয়, যাতে len(cnt) ঠিক ভিন্ন অক্ষরের সংখ্যা দেখায়:

def longest_at_most_k(s, k):
    cnt, L, best = {}, 0, 0
    for R, c in enumerate(s):
        cnt[c] = cnt.get(c, 0) + 1          # expand
        while len(cnt) > k:                 # too many distinct characters: shrink
            cnt[s[L]] -= 1
            if cnt[s[L]] == 0:
                del cnt[s[L]]               # forget characters that left completely
            L += 1
        best = max(best, R - L + 1)
    return best

print(longest_at_most_k("eceba", 2))        # 3  ("ece")

একটি কাজের কৌশলও মনে রাখুন: “ঠিক K টি ভিন্ন অক্ষর আছে এমন substring কয়টি?” — এটি সরাসরি টেমপ্লেটে বসে না, কারণ “ঠিক K” শর্ত একমুখী নয়। কিন্তু (সর্বোচ্চ K টি থাকা substring-এর সংখ্যা) − (সর্বোচ্চ K − 1 টি থাকা substring-এর সংখ্যা) = ঠিক K. আর প্রতিটি R-এ “সর্বোচ্চ K” শর্তে বৈধ substring আছে R − L + 1 টি — যোগ করলেই গণনা। কনটেস্টে এটি বহুল ব্যবহৃত।

৯ · কখন কৌশলটি কাজ করে না — ঋণাত্মক সংখ্যা আর prefix sum

Two pointer আর sliding window জাদু নয়; এরা একটি গাণিতিক কাঠামোর ওপর দাঁড়িয়ে। Pair sum-এ সেই কাঠামো হলো সাজানো ক্রম, window-এ একমুখী শর্ত। কাঠামো না থাকলে কোড চলবে, কিন্তু নিঃশব্দে ভুল উত্তর দেবে। সবচেয়ে পরিচিত ফাঁদ: ঋণাত্মক সংখ্যা।

ওপরের minLenAtLeast-কে a = [4, −10, 3, 4] আর S = 7 দিন। সঠিক উত্তর 2 (শেষ দুটি: 3 + 4 = 7). কিন্তু কোড যা করে:

window কখনো বৈধ হয় না, তাই L একবারও নড়ে না, আর কোড বলে “কোনো উত্তর নেই” (0). সমস্যার মূল: −10 window-এর ভেতরে আটকে আছে। ঋণাত্মক উপাদান বাদ দিলে sum বাড়ে — তাই “বাঁ দিক থেকে বাদ দিলে sum কমে” — এই একমুখী যুক্তিটি আর সত্য নয়। কখন L সরানো লাভজনক, window আর জানে না।

একই কারণে “যোগফল ঠিক k এমন subarray কয়টি” প্রশ্নটি ঋণাত্মক সংখ্যা থাকলে window দিয়ে হয় না। এর সঠিক হাতিয়ার prefix sum: P[0] = 0, P[i + 1] = P[i] + a[i] ধরলে a[L..R]-এর যোগফল = P[R + 1] − P[L]. তাহলে “যোগফল k” মানে P[L] = P[R + 1] − k — অর্থাৎ প্রতিটি অবস্থানে শুধু জানতে হবে আগের কোন prefix-এর মান P[R + 1] − k ছিল, আর কতবার। একটি hash table-এ prefix-গুলোর গণনা রাখলে পুরো কাজ গড়ে O(n), ঋণাত্মক সংখ্যা থাকুক বা না থাকুক। এটি পরের পর্ব ১৭-এর বিষয়।

১০ · AI-এর যুগে two pointer আর sliding window — প্যাটার্ন চিনুন, প্রমাণ চান

“Longest substring without repeating characters-এর কোড দাও” লিখলে যেকোনো AI কয়েক সেকেন্ডে ঠিক কোড দেবে — সমস্যাটি এত পরিচিত যে উত্তরটি প্রায় মুখস্থ। বিপদ আসে যখন সমস্যা একটু বদলায়: ঋণাত্মক সংখ্যা ঢোকে, অ্যারে আর সাজানো থাকে না, বা “সর্বোচ্চ K”-এর বদলে “ঠিক K” চাওয়া হয়। তখন AI প্রায়ই চেনা টেমপ্লেটটিই বসিয়ে দেয় — দেখতে নিখুঁত, কিন্তু পেছনের একমুখী শর্তটি আর সত্য নয়। এই কৌশলে কোড ছোট, কিন্তু শুদ্ধতা পুরোটাই একটি যুক্তির ওপর দাঁড়িয়ে। সেই যুক্তি যাচাই করা আপনার কাজ।

এই কৌশলে AI সাধারণত যেসব ভুল করে

যাচাইয়ের চেকলিস্ট

• কোন ধর্মের ওপর কৌশলটি দাঁড়িয়ে (sorted? সব ধনাত্মক? শর্ত একমুখী?), তা এক বাক্যে লিখেছি — আর ইনপুটে সেটি সত্যিই আছে
• L আর R কখনো পিছনে ফেরে না, তা কোড পড়ে নিশ্চিত হয়েছি — তাই মোট চলাচল O(n)
• ৫–৬ উপাদানের একটি ইনপুটে হাতে trace করেছি, প্রতিটি ধাপে window বা pointer-এর অবস্থান লিখে
• খালি ইনপুট, এক উপাদান, সব সমান, আর ঋণাত্মক সংখ্যা — এই edge case-গুলো চালিয়েছি
• window-এর দৈর্ঘ্য R - L + 1 কি না দেখে off-by-one ভুল খুঁজেছি
• হাজারখানেক এলোমেলো ছোট ইনপুটে O(n²) brute force-এর সাথে মিলিয়ে stress testing করেছি