Array আর dynamic array — মেমরিতে পাশাপাশি

১ · Array কী — মেমরিতে পাশাপাশি ঘর

ধরুন পরীক্ষার হলে বেঞ্চে রোল নম্বর অনুযায়ী সবাই বসেছে, প্রতি বেঞ্চে একজন, বেঞ্চগুলো একটানা এক সারিতে। পরিদর্শক জানেন প্রথম বেঞ্চ দরজা থেকে ২ মিটার দূরে, আর প্রতিটি বেঞ্চ ১ মিটার চওড়া। রোল ৩৭-এর পরীক্ষার্থীকে খুঁজতে তাঁকে ১ থেকে ৩৬ পর্যন্ত সবাইকে পেরিয়ে গুনতে হয় না — তিনি মনে মনে হিসাব করেন “২ + ৩৬ × ১ = ৩৮ মিটার” আর সোজা সেখানে চলে যান। ১০০ জন হোক বা ১০,০০০ জন, হিসাব একটাই।

এটিই array-এর মূল ধারণা। Array হলো একই ধরনের উপাদানের সারি, যা মেমরিতে রাখা থাকে পাশাপাশি, ফাঁকহীন ঘরে. প্রথম ঘরের ঠিকানাকে বলে base address. প্রতিটি উপাদানের আকার যদি size বাইট হয়, তাহলে index i-এর ঠিকানা:

মনে আছে পর্ব ০২-এর RAM model? সেখানে ধরেছিলাম যেকোনো ঠিকানার মেমরি ঘর এক ধাপে পড়া যায়। তাহলে a[i] পড়তে লাগে একটি গুণ, একটি যোগ, আর একবার মেমরি পড়া — i যত বড়ই হোক। তাই array-এ index দিয়ে পড়া বা লেখা constant time, Θ(1). এই ক্ষমতার নাম random access: যেকোনো ঘরে সরাসরি যাওয়া, আগের ঘরগুলো না ঘুরেই। নিচে ৫টি int-এর একটি array (প্রতিটি ৪ বাইট, base 1000) দেখুন:

এখান থেকে array-এর তিনটি বৈশিষ্ট্য সরাসরি বেরিয়ে আসে, আর এই পর্বের বাকি সব কিছু এদেরই ফল:

২ · Static array আর dynamic array

যে array-এর আকার তৈরির মুহূর্তেই ঠিক হয়ে যায়, তাকে বলে static array. C-তে int a[100]; বা C++-এ std::array<int, 100> — ১০০ মানে ১০০, পরে ১০১ নম্বর উপাদান রাখার উপায় নেই। ক্রিকেট স্টেডিয়ামের আসনের মতো: গ্যালারিতে আসন যতগুলো, দর্শক তার বেশি হলে আর বসানো যাবে না।

কিন্তু বাস্তব প্রোগ্রামে আমরা প্রায়ই জানি না কতগুলো উপাদান আসবে — ফাইলে কয়টি লাইন, কনটেস্টের ইনপুটে কয়টি সংখ্যা, bKash অ্যাপে আজ কয়টি লেনদেন। এর সমাধান dynamic array: বাইরে থেকে দেখতে এমন array যা ইচ্ছামতো বাড়ে, কিন্তু ভেতরে এটি একটি সাধারণ static array-ই, সাথে দুটি বাড়তি সংখ্যা:

• size — এখন কতগুলো উপাদান আসলে আছে।
• capacity — ভেতরের ব্লকে মোট কতগুলো ঘর নেওয়া আছে। সবসময় size ≤ capacity.

যতক্ষণ size < capacity, নতুন উপাদান শুধু পরের খালি ঘরে বসে। জায়গা ফুরালে dynamic array একটি বড় নতুন ব্লক নেয়, সব পুরোনো উপাদান সেখানে কপি করে, পুরোনো ব্লক ছেড়ে দেয় — একে বলে reallocation. এর বিস্তারিত হিসাব অংশ ৪-এ। ভাষাভেদে নাম আলাদা, ধারণা এক:

৩ · মাঝখানে insert আর delete — সবাইকে সরে বসতে হয়

ট্রেনের টিকিটের লাইনে কেউ যদি তৃতীয় স্থানে ঢুকতে চান (ধরুন তিনি সত্যিই একজন বয়স্ক যাত্রী, সবাই রাজি), তাহলে তৃতীয় থেকে শেষ পর্যন্ত প্রত্যেককে এক পা পিছিয়ে যেতে হয়। লাইনে ৫ জন হলে ৩ জন সরেন; ৫০০ জন হলে ৪৯৮ জন। Array-এর ক্ষেত্রেও ঠিক তাই — ঘরগুলো পাশাপাশি থাকতেই হবে, তাই index i-তে নতুন উপাদান বসাতে i থেকে শেষ পর্যন্ত সবাইকে এক ঘর ডানে সরাতে হয়। একে বলে shifting.

নিচে capacity ৮-এর একটি array-তে (ভরা আছে ৫টি) index 2-এ 25 বসানো, তারপর index 1-এর উপাদান মুছে ফেলা দেখুন। _ মানে খালি ঘর:

বিশ্লেষণ। size n-এর array-এ index i-তে insert করলে ঠিক n − i টি উপাদান সরে, erase করলে n − 1 − i টি। প্রতিটি সরানো Θ(1), তাই:

• শেষে insert/erase (i = n বা n − 1): Θ(1) — কাউকে সরাতে হয় না।
• শুরুতে insert/erase (i = 0): Θ(n) — সবাই সরে।
• এলোমেলো অবস্থানে (i সমান সম্ভাবনায় 0…n): গড়ে n/2 টি সরানো, তাই average case-ও Θ(n) (পর্ব ০৫-এর হিসাব মনে করুন)।

বাড়তি জায়গা O(1) — কাজটি in-place. Python-এ a.insert(0, x) বা a.pop(0), C++-এ v.insert(v.begin(), x) বা v.erase(v.begin()) — দেখতে এক লাইন, কিন্তু প্রতিটি Θ(n). লুপের ভেতরে n বার করলে মোট Θ(n²).

৪ · শেষে যোগ — capacity দ্বিগুণ আর amortized O(1)

এবার সবচেয়ে গুরুত্বপূর্ণ প্রশ্ন: dynamic array ভরে গেলে নতুন ব্লক কত বড় নেবে? সবচেয়ে সরল চিন্তা — “প্রতিবার ১টি ঘর বাড়াই।” তাহলে প্রতিটি push-ই reallocation: k-তম push-এ k − 1 টি উপাদান কপি। n বার push করলে মোট কপি 0 + 1 + 2 + … + (n − 1) = n(n − 1)/2 = Θ(n²). দশ লাখ push মানে প্রায় ৫০,০০০ কোটি কপি — অচল।

আসল কৌশল হলো গুণ করে বাড়ানো: জায়গা ফুরালেই capacity দ্বিগুণ। মেস বাড়ির কথা ভাবুন — প্রতিবার নতুন একজন সদস্য এলে বাসা বদলালে জীবন শেষ। তাই একবার বদলালে দ্বিগুণ বড় বাসা নিন; বাসা বদল (সব জিনিস টানা) দামি, কিন্তু ঘন ঘন হয় না। নিচে capacity 0 থেকে শুরু করে ৯ বার push দেখুন:

কেন মোট কপি 2n-এর কম — প্রমাণ

capacity 1 থেকে দ্বিগুণ হয়, n বার push করা হলো। reallocation হয় তখনই, যখন size ঠিক 1, 2, 4, …, 2^k — যেখানে 2^k হলো n-এর চেয়ে ছোট সবচেয়ে বড় দুইয়ের ঘাত (2^k < n). প্রতিটি reallocation তখনকার size-এর সমান কপি করে, তাই মোট কপি:

এটি একটি geometric series (পর্ব ০৬): শেষ পদটিই প্রায় পুরো যোগফল, আর শেষ পদ 2^k < n. সাথে n টি নতুন উপাদান লেখা — তাই n push-এর মোট কাজ < n + 2n = 3n = Θ(n). গড়ে প্রতিটি push-এর খরচ < ৩ ধাপ, অর্থাৎ O(1) amortized.

এবার নিজের হাতে একটি ছোট dynamic array বানিয়ে দেখি — প্রতিটি push-এ size, capacity আর কপির সংখ্যা ছাপবে। (বাস্তবে নিজে না লিখে std::vector ব্যবহার করবেন; এটি শুধু ভেতরটা বোঝার জন্য।)

#include <iostream>
using namespace std;

struct DynArray {
    int* data = nullptr;
    int size = 0, cap = 0;
    long long copies = 0;

    void push_back(int x) {
        int copied = 0;
        if (size == cap) {                              // full: grow
            int newCap = (cap == 0) ? 1 : 2 * cap;
            int* bigger = new int[newCap];
            for (int i = 0; i < size; ++i) bigger[i] = data[i];  // copy old items
            copied = size;
            delete[] data;
            data = bigger;
            cap = newCap;
        }
        data[size++] = x;
        copies += copied;
        cout << "push " << x << " -> size " << size << ", cap " << cap
             << ", copied " << copied << '\n';
    }
    ~DynArray() { delete[] data; }
};

int main() {
    DynArray a;
    const int n = 9;
    for (int x = 1; x <= n; ++x) a.push_back(x);
    cout << "total copies = " << a.copies << " (less than 2n = " << 2 * n << ")\n";
}

push 1 -> size 1, cap 1, copied 0
push 2 -> size 2, cap 2, copied 1
push 3 -> size 3, cap 4, copied 2
push 4 -> size 4, cap 4, copied 0
push 5 -> size 5, cap 8, copied 4
push 6 -> size 6, cap 8, copied 0
push 7 -> size 7, cap 8, copied 0
push 8 -> size 8, cap 8, copied 0
push 9 -> size 9, cap 16, copied 8
total copies = 15 (less than 2n = 18)

class DynArray:
    def __init__(self):
        self.data = []                   # fixed-size block (never .append to it)
        self.size = 0
        self.cap = 0
        self.copies = 0

    def push_back(self, x):
        copied = 0
        if self.size == self.cap:                    # full: grow
            new_cap = 1 if self.cap == 0 else 2 * self.cap
            bigger = [None] * new_cap
            for i in range(self.size):               # copy old items
                bigger[i] = self.data[i]
            copied = self.size
            self.data, self.cap = bigger, new_cap
        self.data[self.size] = x
        self.size += 1
        self.copies += copied
        print(f"push {x} -> size {self.size}, cap {self.cap}, copied {copied}")

a = DynArray()
n = 9
for x in range(1, n + 1):
    a.push_back(x)
print(f"total copies = {a.copies} (less than 2n = {2 * n})")

push 1 -> size 1, cap 1, copied 0
push 2 -> size 2, cap 2, copied 1
push 3 -> size 3, cap 4, copied 2
push 4 -> size 4, cap 4, copied 0
push 5 -> size 5, cap 8, copied 4
push 6 -> size 6, cap 8, copied 0
push 7 -> size 7, cap 8, copied 0
push 8 -> size 8, cap 8, copied 0
push 9 -> size 9, cap 16, copied 8
total copies = 15 (less than 2n = 18)

৫ · Growth factor, reserve আর shrink_to_fit

capacity প্রতিবার কত গুণ বাড়বে — সেই সংখ্যাকে বলে growth factor (g). g যেকোনো ধ্রুবক > 1 হলেই push amortized O(1) থাকে, কিন্তু ধ্রুবকগুলো বদলায়। শেষ reallocation-এ কপি হয় n-এর কম, তার আগেরটিতে তার 1/g অংশ, তার আগে 1/g² — যোগ করলে মোট কপি < n × g/(g − 1).

যোগ করে বাড়ানো (+c) কেন ব্যর্থ? কারণ তখন reallocation হয় প্রতি c টি push-এ একবার — n/c বার — আর প্রতিবার গড়ে প্রায় n/2 টি কপি: মোট Θ(n²/c), যা c যত বড়ই হোক, শেষ পর্যন্ত Θ(n²). গুণ করে বাড়ালে reallocation-এর সংখ্যা মাত্র Θ(log n).

কোন লাইব্রেরি কোনটি বেছেছে, দেখুন — সবাই একই trade-off-এর ভিন্ন বিন্দুতে দাঁড়িয়ে:

• GCC-র libstdc++ আর Clang-এর libc++ (std::vector): 2 গুণ।
• Microsoft-এর MSVC STL (std::vector) আর Java-র ArrayList: 1.5 গুণ (ArrayList-এ নতুন capacity = পুরোনো + পুরোনো/2).
• CPython-এর list: মাত্র প্রায় 1.125 গুণ, সাথে ছোট একটি ধ্রুবক — Python মেমরি বাঁচানোকে বেশি গুরুত্ব দেয়।

C++ standard নিজে কোনো নির্দিষ্ট g বলে না; শুধু দাবি করে push_back-এর খরচ “amortized constant” হতে হবে। তাই একই কোড ভিন্ন compiler-এ ভিন্ন capacity দেখাতে পারে — capacity()-এর নির্দিষ্ট মানের ওপর নির্ভর করে কোড লিখবেন না।

reserve — আগে থেকে জানলে আগেই জায়গা নিন

কতগুলো উপাদান আসবে তা আগে থেকে জানলে (যেমন কনটেস্টে প্রথম লাইনে n দেওয়া থাকে) reallocation পুরোপুরি এড়ানো যায়:

int n; cin >> n;
vector<int> v;
v.reserve(n);                   // capacity >= n now: no reallocation below
for (int i = 0; i < n; ++i) { int x; cin >> x; v.push_back(x); }

vector<int> w(n);               // different: size n, filled with zeros
v.clear();                      // size 0, but capacity stays (memory kept)
v.shrink_to_fit();              // a REQUEST to give the spare memory back

• reserve(n) শুধু capacity বাড়ায়, size বদলায় না — তাই এরপর v[0] লেখা ভুল (size এখনো 0); push_back করতে হবে। আর vector<int> w(n) সাথে সাথে n টি শূন্য বসায় — তারপর push_back করলে সেগুলো n টি শূন্যের পরে যোগ হয়। এই দুটি গুলিয়ে ফেলা নতুনদের খুব পরিচিত ভুল।
• clear() উপাদান মোছে কিন্তু মেমরি ফেরত দেয় না — একই vector বারবার ব্যবহার করলে এটি আসলে সুবিধা।
• shrink_to_fit() হলো অনুরোধ, আদেশ নয় — standard অনুযায়ী লাইব্রেরি চাইলে উপেক্ষা করতে পারে। কাজ করলে এটি নিজেও একটি reallocation (Θ(n) কপি)।
• Python-এ সমতুল্য কৌশল: আগে থেকে a = [0] * n বানিয়ে index দিয়ে লেখা, অথবা list comprehension.

৬ · Iterator invalidation — বাসা বদলালে পুরোনো ঠিকানা অচল

মেস বাড়ির উদাহরণে ফিরি। আপনি বন্ধুকে পুরোনো বাসার ঠিকানা দিয়ে রেখেছিলেন। এর মধ্যে আপনি বড় বাসায় উঠে গেছেন। বন্ধু পুরোনো ঠিকানায় গিয়ে দরজায় টোকা দিলেন — ভেতরে এখন অন্য কেউ থাকেন, বা ঘর ফাঁকা। Dynamic array-এর reallocation ঠিক এটাই করে: সব উপাদান নতুন ব্লকে চলে যায়, পুরোনো ব্লক ফেরত যায়। কিন্তু যে pointer, reference বা iterator আগে পুরোনো ব্লকের দিকে তাকিয়ে ছিল, সেটি জানে না যে বাসা বদলেছে। একে বলে iterator invalidation, আর এমন অচল pointer-কে বলে dangling pointer.

vector<int> v{1, 2, 3};
int& first = v[0];                  // reference into the current block
for (int i = 0; i < 100; ++i) v.push_back(i);   // block moves (several times)
cout << first;                      // UNDEFINED BEHAVIOUR: dangling reference

// the classic loop bug: growing the vector you are iterating over
for (auto it = v.begin(); it != v.end(); ++it)
    if (*it % 2 == 0) v.push_back(*it);   // may reallocate: 'it' now dangles

সবচেয়ে বিপজ্জনক দিক: এই কোড প্রায়ই ঠিকঠাক চলে বলে মনে হয়. ছোট ইনপুটে reallocation হয়তো হয়ই না (capacity যথেষ্ট ছিল), বা পুরোনো মেমরিতে তখনো পুরোনো মান পড়ে আছে। বড় ইনপুটে বা অন্য compiler-এ হঠাৎ ভুল উত্তর বা crash. std::vector-এর নিয়মগুলো মনে রাখুন:

নিরাপদ বিকল্প। (১) লুপে বদলাতে হলে iterator নয়, index ব্যবহার করুন — v[i] প্রতিবার নতুন করে base থেকে হিসাব হয়, তাই reallocation-এর পরেও ঠিক থাকে; আর শর্তে v.size() একবার আগে থেকে রেখে দিন, যাতে নতুন যোগ করা উপাদান আবার না ঘোরে। (২) মুছতে হলে it = v.erase(it); লিখুন (erase নতুন বৈধ iterator ফেরত দেয়), অথবা আরও ভালো — C++20-এর std::erase_if(v, pred), যা এক পাসে Θ(n)-এ সব মোছে। লুপে একটি একটি করে erase করা Θ(n²)!

৭ · 2D array, row-major আর cache — আর jagged array

সিনেমা হলের আসন ভাবুন — সারি A থেকে J, প্রতি সারিতে ১২টি আসন। এটি একটি 2D array. কিন্তু কম্পিউটারের মেমরি একমাত্রিক — একটিই লম্বা ঠিকানার সারি। তাই R সারি আর C কলামের int m[R][C]-কে কোনো এক নিয়মে এক সারিতে বিছাতে হয়। C, C++ আর Python-এর NumPy (ডিফল্টে) মানে row-major order: প্রথমে সারি 0-এর সব কলাম, তারপর সারি 1-এর সব, এভাবে। Fortran, MATLAB আর R মানে উল্টোটা — column-major order.

এখন প্রশ্ন: সব উপাদান যোগ করতে দুটি লুপ — বাইরে সারি, ভেতরে কলাম (for i … for j …), নাকি উল্টো? দুটিই Θ(R × C) কাজ। কিন্তু মেমরি থেকে ডেটা আসে টুকরো টুকরো — একেকটি cache line (বাস্তবে সাধারণত ৬৪ বাইট = ১৬টি int). একটি ঘর পড়লে পুরো line চলে আসে cache-এ। সময় না মেপে আমরা গুনব কতবার মেমরি থেকে নতুন line আনতে হয়। সরল মডেল: 3 × 4 matrix, এক line = ৪টি int, আর cache একসাথে মাত্র ১টি line ধরে রাখে। ঘরের নম্বর = i × 4 + j:

শিক্ষা সরল: C/C++/Python-এ ভেতরের লুপে শেষ index (j) বদলান — for (i …) for (j …) sum += m[i][j];. matrix গুণের মতো তিন-লুপের কাজে শুধু লুপের ক্রম বদলে (যেমন i-j-k থেকে i-k-j) একই Θ(n³) অ্যালগরিদম বাস্তবে কয়েক গুণ দ্রুত হয়ে যায়। Big-O বলে কত কাজ; cache বলে কাজটি মেমরির সাথে কতটা মানিয়ে চলে.

Jagged array — প্রতিটি সারি আলাদা দৈর্ঘ্যের

সব সারির দৈর্ঘ্য সমান না হলে? যেমন প্রতিটি ছাত্রের আলাদা সংখ্যক বিষয়ের নম্বর, বা গ্রাফে প্রতিটি node-এর প্রতিবেশীর তালিকা (adjacency list, পর্ব ৩৯)। তখন ব্যবহার হয় jagged array: প্রতিটি সারি একটি আলাদা dynamic array.

vector<vector<int>> marks(3);      // 3 students, rows start empty
marks[0] = {78, 85};                   // row lengths can differ
marks[1] = {90, 66, 71, 88};
marks[2].push_back(55);
// each row is its own block somewhere in memory:
// marks[i][j] = two lookups (find row i's block, then j inside it)

vector<int> flat(R * C);              // one block, manual row-major index
flat[i * C + j] = 7;                   // same as m[i][j], one lookup

vector<vector<int>> লেখা সহজ, কিন্তু সারিগুলো মেমরিতে পাশাপাশি নাও থাকতে পারে, আর প্রতিটি সারির নিজস্ব বাড়তি তথ্য (pointer, size, capacity) থাকে। আয়তাকার বড় matrix-এ পারফরম্যান্স জরুরি হলে অনেকে একটিমাত্র vector<int> flat(R * C) নিয়ে নিজে i * C + j হিসাব করেন। Python-এ grid = [[0] * C for _ in range(R)] লিখুন — [[0] * C] * R লিখলে R টি সারিই একই list-এর reference হয়, এক সারি বদলালে সব বদলে যায়!

৮ · সব খরচ এক টেবিলে, আর উল্টানো ও k ঘর ঘোরানো

এ পর্যন্ত যা দেখলাম, এক জায়গায় — n উপাদানের dynamic array (std::vector বা Python list):

উল্টানো — দুই প্রান্ত থেকে ভেতরে

বাজারের সারিতে সবাইকে উল্টো ক্রমে দাঁড় করাতে হবে, কিন্তু পাশে আরেকটি সারি বানানোর জায়গা নেই। উপায়: প্রথম আর শেষজন জায়গা বদলান, তারপর দ্বিতীয় আর শেষের আগেরজন — মাঝখানে পৌঁছালেই শেষ। দুটি index, lo শুরু থেকে আর hi শেষ থেকে, একে অপরের দিকে এগোয় — এটি two pointer কৌশলের সবচেয়ে সরল রূপ (পুরো আলোচনা পর্ব ১৬-এ)। n উপাদানে ঠিক ⌊n/2⌋ টি swap: সময় Θ(n), বাড়তি জায়গা O(1).

k ঘর ডানে ঘোরানো — তিনবার উল্টানোর কৌশল

Array rotation: [1 2 3 4 5 6 7]-কে ৩ ঘর ডানে ঘোরালে শেষের তিনটি সামনে চলে আসে: [5 6 7 1 2 3 4]. সরল উপায়গুলো দেখুন — (ক) একবারে এক ঘর ঘোরানো k বার: Θ(n·k); (খ) নতুন array-তে b[(i + k) % n] = a[i]: Θ(n) সময় কিন্তু Θ(n) বাড়তি জায়গা। Θ(n) সময় আর O(1) জায়গা কি একসাথে সম্ভব? হ্যাঁ — reversal algorithm:

Pseudocode (0-based; REVERSE(a, l, r) reverses a[l..r-1])

ROTATE-RIGHT(a, k):
    n = length(a)
    if n == 0: return
    k = k mod n                  // rotating by n changes nothing
    REVERSE(a, 0, n)             // whole array
    REVERSE(a, 0, k)             // first k elements
    REVERSE(a, k, n)             // the remaining n - k elements

কেন ঠিক — প্রমাণ। অক্ষর দিয়ে লিখি: X^R মানে X উল্টো। যেকোনো দুই অংশের জন্য (XY)^R = Y^RX^R (শেষটি প্রথমে আসে, প্রতিটি অংশ উল্টো), আর (X^R)^R = X. তাহলে প্রথম ধাপে AB → B^RA^R; দ্বিতীয় ধাপে প্রথম k ঘর, অর্থাৎ B^R, উল্টে হয় B; তৃতীয় ধাপে A^R উল্টে A. ফল BA — ঠিক যা চেয়েছিলাম। সময়: তিনটি reverse মিলে ⌊n/2⌋ + ⌊k/2⌋ + ⌊(n − k)/2⌋ ≤ n swap, তাই Θ(n); বাড়তি জায়গা O(1). বাঁয়ে ঘোরাতে একই কৌশল, শুধু ক্রম বদলে: আগে প্রথম k, তারপর বাকিটা, শেষে পুরোটা।

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

int swaps = 0;
void rev(vector<int>& a, int lo, int hi) {        // reverse a[lo..hi-1]
    for (--hi; lo < hi; ++lo, --hi) { swap(a[lo], a[hi]); ++swaps; }
}

void show(const string& label, const vector<int>& a) {
    cout << label;
    for (int x : a) cout << ' ' << x;
    cout << '\n';
}

void rotateRight(vector<int>& a, int k, bool trace) {
    int n = (int)a.size();
    if (n == 0) return;
    k %= n;                                        // k = 10, n = 7 -> 3
    rev(a, 0, n); if (trace) show("reverse all   :", a);
    rev(a, 0, k); if (trace) show("reverse [0,k) :", a);
    rev(a, k, n); if (trace) show("reverse [k,n) :", a);
}

int main() {
    vector<int> a{1, 2, 3, 4, 5, 6, 7};
    show("start         :", a);
    rotateRight(a, 3, true);
    cout << "swaps = " << swaps << " (never more than n = 7)\n";
    vector<int> b{1, 2, 3, 4, 5, 6, 7};
    rotateRight(b, 10, false);
    show("k = 10        :", b);
}

start         : 1 2 3 4 5 6 7
reverse all   : 7 6 5 4 3 2 1
reverse [0,k) : 5 6 7 4 3 2 1
reverse [k,n) : 5 6 7 1 2 3 4
swaps = 6 (never more than n = 7)
k = 10        : 5 6 7 1 2 3 4

swaps = 0

def rev(a, lo, hi):                      # reverse a[lo..hi-1]
    global swaps
    hi -= 1
    while lo < hi:
        a[lo], a[hi] = a[hi], a[lo]
        swaps += 1
        lo += 1
        hi -= 1

def show(label, a):
    print(label, *a)

def rotate_right(a, k, trace):
    n = len(a)
    if n == 0:
        return
    k %= n                               # k = 10, n = 7 -> 3
    rev(a, 0, n)
    if trace: show("reverse all   :", a)
    rev(a, 0, k)
    if trace: show("reverse [0,k) :", a)
    rev(a, k, n)
    if trace: show("reverse [k,n) :", a)

a = [1, 2, 3, 4, 5, 6, 7]
show("start         :", a)
rotate_right(a, 3, True)
print(f"swaps = {swaps} (never more than n = 7)")
b = [1, 2, 3, 4, 5, 6, 7]
rotate_right(b, 10, False)
show("k = 10        :", b)

start         : 1 2 3 4 5 6 7
reverse all   : 7 6 5 4 3 2 1
reverse [0,k) : 5 6 7 4 3 2 1
reverse [k,n) : 5 6 7 1 2 3 4
swaps = 6 (never more than n = 7)
k = 10        : 5 6 7 1 2 3 4

৯ · আরও ক্লাসিক — max, second max, duplicate বাদ আর Kadane

সবচেয়ে বড় আর দ্বিতীয় বড় — এক পাসে

সবচেয়ে বড় মান খুঁজতে n − 1 টি তুলনা লাগে, আর এর কমে সম্ভব নয় — প্রতিটি “পরাজিত” উপাদানকে অন্তত একবার কারও কাছে হারতে হবে, আর n − 1 জন পরাজিত। দ্বিতীয় বড় মান? সাধারণ ভুল: sort করে a[n-2] নেওয়া — Θ(n log n), আর duplicate থাকলে ([9, 9, 4]) ভুল উত্তর 9. এক পাসের সমাধান:

// largest and second largest DISTINCT values (LLONG_MIN = "none yet")
long long mx = LLONG_MIN, second = LLONG_MIN;
for (int x : a) {
    if (x > mx) { second = mx; mx = x; }          // new champion: old one drops to 2nd
    else if (x < mx && x > second) second = x;   // x < mx skips duplicates of mx
}

সময় Θ(n), বাড়তি জায়গা O(1). x < mx শর্তটিই duplicate সামলায়; “distinct নয়, সাধারণ দ্বিতীয় অবস্থান” চাইলে শর্তটি x > second করলেই হয়। সব উপাদান সমান হলে second থেকে যায় LLONG_MIN — উত্তর নেই, সেটি আলাদা করে জানাতে হবে।

Sorted array থেকে duplicate বাদ — in-place

[1 1 2 3 3 3 4] থেকে [1 2 3 4] চাই, নতুন array ছাড়া। Sorted হওয়ায় একই মানগুলো পাশাপাশি থাকে। দুটি index: r (read) প্রতিটি উপাদান পড়ে, w (write) পরের distinct মান কোথায় লেখা হবে তা মনে রাখে।

// a is sorted; keeps the distinct values in a[0..w-1], returns w
int dedup(vector<int>& a) {
    if (a.empty()) return 0;
    int w = 1;                                   // a[0] is always kept
    for (int r = 1; r < (int)a.size(); ++r)
        if (a[r] != a[w - 1]) a[w++] = a[r];     // new value: keep it
    return w;                                    // then a.resize(w) if you like
}

শুদ্ধতার যুক্তি (loop invariant, পর্ব ০৩): প্রতিটি ঘুর্ণনের শুরুতে a[0..w−1]-এ আছে a[0..r−1]-এর সব distinct মান, ছোট থেকে বড় ক্রমে, প্রতিটি একবার। শুরুতে (r = 1, w = 1) এটি সত্য। a[r] যদি a[w−1]-এর সমান হয়, এটি পুরোনো মান (sorted, তাই সমান মান শুধু শেষ রাখা মানের সমান হতে পারে) — বাদ। আলাদা হলে এটি নতুন এবং বড় — a[w]-এ লেখা হয়। w ≤ r সবসময়, তাই লেখা কখনো না-পড়া ঘর মুছে দেয় না। লুপ শেষে r = n, তাই a[0..w−1] = সব distinct মান। সময় Θ(n), বাড়তি O(1). Array sorted না হলে এই কোড ভুল ([1 2 1] থেকে [1 2 1]) — তখন আগে sort, বা hash set (পর্ব ৩২)।

Kadane — সবচেয়ে বড় যোগফলের subarray

একটি দোকানের ৯ দিনের লাভ-ক্ষতি (হাজার টাকায়): [−2, 1, −3, 4, −1, 2, 1, −5, 4]. টানা কোন কয়েক দিনে মোট লাভ সবচেয়ে বেশি? এটি maximum subarray problem. সব (l, r) জোড়া চেষ্টা করলে Θ(n²) (প্রতিটির যোগফল চলতে চলতে হিসাব করে), প্রতিবার নতুন করে যোগ করলে Θ(n³). Divide and conquer দিয়ে Θ(n log n) হয়। কিন্তু Θ(n)-এর একটি সুন্দর সমাধান আছে — Kadane's algorithm.

মূল প্রশ্নটি একটু বদলে নিন: “index i-তে শেষ হওয়া সেরা যোগফল কত?” একে বলি cur(i). i-তে শেষ হওয়া subarray হয় শুধু a[i] নিজে, নয়তো (i − 1)-এ শেষ হওয়া কোনো subarray-এর সাথে a[i] জুড়ে। দ্বিতীয় ক্ষেত্রে সেরাটি অবশ্যই cur(i − 1) + a[i]. তাই:

সহজ ভাষায়: আগের যোগফল ঋণাত্মক হলে সেটি বোঝা — ফেলে দিয়ে নতুন করে শুরু করুন। চলুন ধাপে ধাপে দেখি:

long long kadane(const vector<int>& a) {     // a must be non-empty
    long long cur = a[0], best = a[0];
    for (size_t i = 1; i < a.size(); ++i) {
        cur = max<long long>(a[i], cur + a[i]);   // extend, or start fresh at i
        best = max(best, cur);
    }
    return best;
}

কেন ঠিক: সর্বোচ্চ subarray-টি কোনো না কোনো index r-এ শেষ হয়, তাই উত্তর = সব r-এর জন্য “r-এ শেষ হওয়া সেরা”-র সর্বোচ্চ। আর cur(r) যে সত্যিই r-এ শেষ হওয়া সেরা, তা induction-এ প্রমাণ হয় (ওপরের দুই-ক্ষেত্রের যুক্তি)। লক্ষ করুন, শুরু a[0] দিয়ে, 0 দিয়ে নয় — সব সংখ্যা ঋণাত্মক হলে ([−3, −1, −2]) সঠিক উত্তর −1, অথচ cur = best = 0 দিয়ে শুরু করলে ভুল উত্তর 0 আসে (খালি subarray অনুমোদিত না হলে)। এই যে “i-তে শেষ হওয়া সেরা উত্তর” — আগের উপসমস্যার উত্তর থেকে পরেরটি গড়া — এটিই dynamic programming-এর ভাষা। পর্ব ৫২-তে ঠিক এই চোখ দিয়ে Kadane-কে আবার দেখবেন।

১০ · AI-এর যুগে array — এক লাইনের কোডের লুকানো খরচ

Array-এর সমস্যা AI খুব দ্রুত সমাধান করে — rotate, dedup, Kadane প্রায় মুখস্থের মতো লিখে দেয়। কিন্তু array-এর ভুলগুলো সাধারণত ছোট ইনপুটে দেখা দেয় না: k > n, খালি array, সব-ঋণাত্মক সংখ্যা, এক লাইনের Python যা ভেতরে Θ(n) কপি করে, বা লুপের ভেতরে erase. AI প্রায়ই সময়ের দাবিও ভুল করে — “list.insert(0, x) O(1)” বা “slicing দিয়ে rotate, O(1) জায়গা”।

Array-এ AI সাধারণত যেসব ভুল করে

AI-এর (বা নিজের) array কোড যাচাইয়ের চেকলিস্ট

• খালি array, এক উপাদান আর দুই উপাদান দিয়ে চালিয়েছি
• লুপের ভেতরের প্রতিটি লাইব্রেরি কলের (insert, erase, slice, in) খরচ জেনে মোট complexity হিসাব করেছি
• n = 4 বা 5-এ হাতে array-এর অবস্থা ধাপে ধাপে trace করেছি (dry run)
• লুপ চলাকালীন vector বদলালে iterator/reference অচল হচ্ছে কি না দেখেছি
• সীমার মান যাচাই করেছি: i < n না i <= n, k % n, সব-ঋণাত্মক ইনপুট
• ছোট এলোমেলো ইনপুটে একটি সরল brute force সমাধানের সাথে মিলিয়ে stress testing করেছি