নেক্সট গ্রেটার এলিমেন্ট II: সার্কুলার অ্যারে এবং স্ট্যাকের জাদু

আজকের ক্লাসে আমরা ডেটা স্ট্রাকচার এবং অ্যালগরিদমের (DSA) একটি খুব জনপ্রিয় এবং গুরুত্বপূর্ণ সমস্যা নিয়ে আলোচনা করব, যার নাম Next Greater Element II। এটি লিটকোডের (LeetCode) ৫০০ নম্বর সমস্যা। যারা ইতিমধ্যে সাধারণ "Next Greater Element" সমাধান করেছেন, তাদের জন্য এটি বোঝা আরও সহজ হবে। মূলত একটি সাধারণ অ্যারেকে কীভাবে সার্কুলার বা বৃত্তাকার উপায়ে চিন্তা করে বড় সংখ্যা খুঁজে বের করা যায়, তা-ই এখানে শিখব।

---

১. সার্কুলার অ্যারে এবং সমস্যার মূল ধারণা (Introduction)

সাধারণত একটি অ্যারেতে আমরা বাম থেকে ডানে সংখ্যা খুঁজি। কিন্তু সার্কুলার অ্যারে (Circular Array) মানে হলো, অ্যারের শেষ এলিমেন্টটির পর আবার প্রথম এলিমেন্টটি শুরু হবে। অনেকটা ঘড়ির কাঁটার মতো!

ভিডিও রেফারেন্স: L73. Next Greater Element - II | Stack & Queue

উদাহরণ: ধরুন আমাদের কাছে একটি অ্যারে আছে: [1, 2, 1]

• 1-এর জন্য পরের বড় সংখ্যা হলো 2 [01:48]।

• 2-এর জন্য ডানে কোনো বড় সংখ্যা নেই। কিন্তু যেহেতু এটা সার্কুলার, তাই আমরা আবার শুরুতে ফিরে গিয়ে দেখব। শুরুতে আছে 1, যা 2-এর চেয়ে বড় নয়। তাই এর উত্তর হবে -1।

• শেষ 1-এর জন্য ডানে কিছু নেই, কিন্তু শুরুতে ফিরে গেলে আমরা 2 পাই, যা 1-এর চেয়ে বড়। তাই উত্তর হবে 2 [02:13]।

---

২. সমাধানের বুদ্ধি: ডাবল অ্যারে না বানিয়েও সমাধান (Optimized Approach)

সবচেয়ে সহজ উপায় হতে পারত অ্যারেকে দুইবার লিখে ফেলা (যেমন [1, 2, 1, 1, 2, 1])। কিন্তু এতে মেমোরি বেশি খরচ হয়। এর বদলে আমরা একটি মজার ট্রিক ব্যবহার করব—আমরা লুপ চালাব 2 * n বার এবং ইনডেক্স ঠিক রাখতে Modulo (%) অপারেটর ব্যবহার করব [10:01]।

সহজ কথায় ব্যাখ্যা:

• Modulo (%): এটি ভাগশেষ বের করার একটি উপায়। ধরুন অ্যারের সাইজ ৫। আপনি যদি ৬ নম্বর ইনডেক্স খোঁজেন, তবে 6 % 5 = 1 হবে। অর্থাৎ এটি আপনাকে আবার ঘুরিয়ে ১ নম্বর ইনডেক্সে নিয়ে আসবে। একেই বলে সার্কুলার নেভিগেশন।

আমরা এখানে স্ট্যাক (Stack) ব্যবহার করব। স্ট্যাকে আমরা সংখ্যার ইনডেক্স জমা রাখব এবং পিছন দিক থেকে লুপ চালানো শুরু করব যাতে ডানদিকের বড় সংখ্যাগুলো সহজেই ট্র্যাক করা যায় [07:36]।

---

৩. কোডিং সমাধান (Coding Implementation)

নিচে সহজভাবে জাভাস্ক্রিপ্ট/সি++ স্টাইলে কোডটি দেওয়া হলো:

C++

vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1); // শুরুতে সবগুলোকে -1 ধরে নিলাম
    stack<int> s;

    // আমরা লুপ চালাব ২ বার (2*n-1 থেকে শুরু করে ০ পর্যন্ত)
    for (int i = 2 * n - 1; i >= 0; i--) {
        // যতক্ষণ স্ট্যাকের উপরের সংখ্যাটি বর্তমান সংখ্যার চেয়ে ছোট বা সমান
        while (!s.empty() && nums[s.top()] <= nums[i % n]) {
            s.pop(); // ছোট সংখ্যাগুলোকে সরিয়ে দাও [00:15:20]
        }
        
        // যদি i আমাদের আসল অ্যারের রেঞ্জে থাকে (i < n)
        if (i < n) {
            if (!s.empty()) {
                res[i] = nums[s.top()]; // স্ট্যাকের টপ-ই হলো পরের বড় সংখ্যা
            }
        }
        
        // বর্তমান ইনডেক্সটি স্ট্যাকে রাখছি
        s.push(i % n); [00:18:43]
    }
    return res;
} 

কোডের ব্যাখ্যা:

• 2 * n - 1 থেকে লুপ: এর মানে হলো আমরা অ্যারেকে দুইবার মনে মনে কল্পনা করছি। প্রথমবার স্ট্যাক তৈরি করার জন্য এবং দ্বিতীয়বার আসল উত্তর পাওয়ার জন্য।

• s.pop(): যদি আমরা এমন কোনো সংখ্যা পাই যা বর্তমান সংখ্যার চেয়ে ছোট, তবে সে আমাদের কোনো কাজে আসবে না, তাই তাকে বের করে দিচ্ছি। কারণ আমরা "বড়" সংখ্যা খুঁজছি।

• i % n: এটি নিশ্চিত করে যে আমরা সবসময় অ্যারের সীমার মধ্যেই থাকব [10:07]।

---

৪. কঠিন শব্দের সহজ মানে (Glossary)

• Stack (স্ট্যাক): এটি একটি ডেটা স্ট্রাকচার যেখানে শেষ ঢোকানো জিনিসটি আগে বের হয় (LIFO - Last In First Out)। যেমন একটার ওপর একটা প্লেট সাজিয়ে রাখা।

• Dry Run (ড্রাই রান): কোড লেখার আগে খাতা-কলমে পরীক্ষা করে দেখা যে সেটি কীভাবে কাজ করবে [03:19]।

• Time Complexity (টাইম কমপ্লেক্সিটি): একটি কোড কত দ্রুত চলে। এখানে এর মান O(n), কারণ আমরা প্রতিটা এলিমেন্টকে সর্বোচ্চ দুইবার দেখছি [19:30]।

---

৫. আমার বিশ্লেষণ ও মতামত (Final Analysis & Suggestions)

সারাংশ: কন্টেন্ট ক্রিয়েটর (শ্রদ্ধা খাপরা) এখানে বোঝাতে চেয়েছেন যে, সার্কুলার অ্যারের সমস্যা দেখে ভয় পাওয়ার কিছু নেই। আপনি যদি লুপের সীমানা বাড়িয়ে দেন এবং মডুলো ব্যবহার করেন, তবে এটি একটি সাধারণ লিনিয়ার অ্যারে সমস্যার মতোই সমাধান করা সম্ভব।

বাস্তব জীবনের সাথে মিল: এই অ্যালগরিদমটি অনেকটা স্টোক মার্কেট বা তাপমাত্রার ওঠানামা বিশ্লেষণের মতো। যেমন, আজকের চেয়ে বেশি গরম কবে পড়বে তা জানার জন্য আমরা সামনের দিনগুলো দেখি। যদি শীতকাল শেষ হয়ে যায়, আমরা আবার আগামী বছরের গরমকালের ডেটা দেখি।

বিকল্প বুদ্ধি: যদি স্ট্যাক ব্যবহার করতে কঠিন লাগে, তবে সাধারণ দুইবার লুপ চালিয়ে (Brute Force) করা যায়, কিন্তু সেটি বড় ডেটার ক্ষেত্রে অনেক ধীর হয়ে যাবে (O(n2))। তাই ইন্টারভিউতে সবসময় এই স্ট্যাক বা O(n) পদ্ধতি ব্যবহার করাই বুদ্ধিমানের কাজ [03:13]।

পরামর্শ: যারা নতুন শিখছেন, তারা প্রথমে সাধারণ "Next Greater Element I" সমাধান করুন। এরপর এই সার্কুলার ভার্সনটি ট্রাই করুন। স্ট্যাকের ধারণা পরিষ্কার থাকলে এটি পানির মতো সহজ মনে হবে!

[

L73. Next Greater Element - II | Stack & Queue

Shradha Khapra · 42K views

](http://www.youtube.com/watch?v=If--3pm9K3U)