হিস্টোগ্রামে সবথেকে বড় আয়তক্ষেত্র বা রেকট্যাঙ্গেল বের করার সহজ উপায়

সবাইকে স্বাগতম! আজকের এই আলোচনায় আমরা একটি দারুণ মজার এবং গুরুত্বপূর্ণ সমস্যা সমাধান করব। যার নাম হলো 'Largest Rectangle in Histogram'। এটি লিটকোড (LeetCode) এর একটি হার্ড লেভেলের সমস্যা (Problem #84)। আমরা শিখব কীভাবে ডেটা স্ট্রাকচার ব্যবহার করে খুব সহজে এবং কম সময়ে এই বড় আয়তক্ষেত্রটির ক্ষেত্রফল (Area) বের করা যায়।

সমস্যাটি কী? (Introduction)

হিস্তোগ্রাম হলো এক ধরণের গ্রাফ যেখানে অনেকগুলো বার (Bars) পাশাপাশি থাকে। আমাদের কাছে প্রতিটি বারের উচ্চতা (Height) দেওয়া থাকবে। আমাদের কাজ হলো এমন একটি আয়তক্ষেত্র বা রেকট্যাঙ্গেল খুঁজে বের করা যা এই হিস্তোগ্রামের ভেতরে তৈরি করা যায় এবং যার ক্ষেত্রফল হবে সবথেকে বেশি।

এখানে আমরা মূল ভিডিও রেফারেন্স হিসেবে ব্যবহার করছি: Largest Rectangle in Histogram | Best Solution & Code [00:22]

---

১. ব্রুট ফোর্স বনাম অপ্টিমাল সলিউশন (Approaches)

যেকোনো প্রবলেম সলভ করার দুটি উপায় থাকে।

• ব্রুট ফোর্স (Brute Force): সব কয়টি সম্ভাব্য রেকট্যাঙ্গেল চেক করা। এতে সময় অনেক বেশি লাগে (O(n²))। [03:05]

• অপ্টিমাল সলিউশন (Optimal Solution): আমরা এখানে Stack ডেটা স্ট্রাকচার ব্যবহার করব যাতে একবার লুপ চালিয়েই কাজ শেষ করা যায় (O(n))। [03:32]

সহজ ভাষায় ব্যাখ্যা:

• ব্রুট ফোর্স: ধরুন একটি বড় বাজারের সব দোকান ঘুরে সেরা দাম খুঁজছেন। এতে সময় বেশি লাগে।

• অপ্টিমাল (Stack): আপনার কাছে একটি স্মার্ট লিস্ট আছে যা দেখে আপনি মুহূর্তেই সিদ্ধান্ত নিতে পারছেন।

---

২. মূল আইডিয়া: প্রতিটি বারের জন্য সর্বোচ্চ এলাকা (The Logic)

ভিডিওতে শ্রদ্ধা আপু বুঝিয়েছেন যে, আমরা যদি ধরে নেই যে প্রতিটি বারকে (Bar) তার পুরো উচ্চতায় রেখে আমরা একটি রেকট্যাঙ্গেল বানাব, তবে সেই রেকট্যাঙ্গেলটি ডানে আর বামে কতদূর যেতে পারবে? [04:04]

একটি বার ডানে বা বামে ততক্ষণ পর্যন্ত বাড়তে পারে যতক্ষণ না সে নিজের চেয়ে ছোট কোনো বার পায়।

• Left Smaller (L): বাম দিকে প্রথম ছোট বারের ইনডেক্স। [10:11]

• Right Smaller (R): ডান দিকে প্রথম ছোট বারের ইনডেক্স। [10:11]

সূত্র (Formula): Width (চওড়া) = Right Smaller Index - Left Smaller Index - 1 Area (ক্ষেত্রফল) = Height * Width [11:04]

---

৩. স্ট্যাক ব্যবহার করে সমাধান (Using Stack)

আমাদের দুটি প্রধান কাজ করতে হবে: ১. Next Smaller Element (Right): ডানে ছোট বার খোঁজা। [12:31] ২. Previous Smaller Element (Left): বামে ছোট বার খোঁজা। [21:08]

সহজ ভাষায় 'Stack' কী? স্ট্যাক হলো অনেকটা থালার ওপর থালা সাজিয়ে রাখার মতো। আপনি সবশেষে যে থালাটি রাখবেন, সেটিই সবার আগে সরাতে পারবেন (LIFO - Last In First Out)।

ভিডিও রেফারেন্স: [18:19] (সুইডো কোড এবং লজিক)

---

৪. কোডিং অংশ (Coding Snippet)

নিচে C++ এ এই সমস্যার সমাধান দেওয়া হলো। কোডটি দেখলে বুঝতে পারবেন কীভাবে স্ট্যাক ব্যবহার করে ইনডেক্সগুলো খুঁজে বের করা হচ্ছে।

C++

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    vector<int> left(n), right(n);
    stack<int> s;

    // ডান দিকের ছোট বারের ইনডেক্স বের করা (Right Smaller)
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() && heights[s.top()] >= heights[i]) {
            s.pop();
        }
        if (s.empty()) right[i] = n; // যদি ছোট কিছু না থাকে, তবে বাউন্ডারি হবে n
        else right[i] = s.top();
        s.push(i);
    }

    // স্ট্যাক খালি করে বাম দিকের জন্য তৈরি করা
    while (!s.empty()) s.pop();

    // বাম দিকের ছোট বারের ইনডেক্স বের করা (Left Smaller)
    for (int i = 0; i < n; i++) {
        while (!s.empty() && heights[s.top()] >= heights[i]) {
            s.pop();
        }
        if (s.empty()) left[i] = -1; // যদি ছোট কিছু না থাকে, তবে বাউন্ডারি -1
        else left[i] = s.top();
        s.push(i);
    }

    int maxArea = 0;
    for (int i = 0; i < n; i++) {
        int width = right[i] - left[i] - 1;
        int area = heights[i] * width;
        maxArea = max(maxArea, area);
    }
    return maxArea;
} 

কোডটির কাজ:

• প্রথম for লুপটি প্রতিটি বারের জন্য তার ঠিক ডান দিকে থাকা ছোট বারের অবস্থান খুঁজে বের করে। [25:13]

• দ্বিতীয় for লুপটি বাম দিকের জন্য একই কাজ করে। [26:00]

• সবশেষে, প্রতিটি বারের জন্য সম্ভাব্য ক্ষেত্রফল বের করে সবথেকে বড়টি (maxArea) রিটার্ন করা হয়। [27:15]

---

৫. আমার বিশ্লেষণ ও মতামত (Analysis and Thinking)

এই প্রবলেমটি সমাধানের মূল চাবিকাঠি হলো বাউন্ডারি বোঝা। অনেক সময় আমরা সরাসরি স্ট্যাকের কথা চিন্তা করি না, কিন্তু লজিক্যালি চিন্তা করলে দেখা যায় আমাদের শুধু ডানে আর বামে ছোট বারটি খুঁজে বের করতে হবে।

বাস্তব জীবনের উদাহরণ: ধরুন আপনি একটি ভিড়ের মধ্যে দাঁড়িয়ে আছেন এবং দুই হাত দুই দিকে প্রসারিত করতে চান। আপনি হাত ততদূরই নিতে পারবেন যতক্ষণ না আপনার চেয়ে লম্বা কেউ বা দেয়াল আপনার সামনে পড়ছে। এখানে বারগুলো হলো সেই দেয়াল।

বিকল্প উপায়: ভিডিওতে দেখানো হয়েছে আলাদা দুটি লুপ চালিয়ে বাম এবং ডানের ছোট ইনডেক্স বের করা। তবে একটি মাত্র লুপ এবং একটি স্ট্যাক ব্যবহার করেও এটি সমাধান করা সম্ভব, যাকে বলা হয় 'Single Pass' সলিউশন। তবে শেখার শুরুতে ভিডিওতে দেখানো পদ্ধতিটিই (Double Pass) সবথেকে সহজবোধ্য। [31:07]

পরামর্শ: কোডটি মুখস্থ না করে খাতায় কলমে 'Dry Run' করুন (মানে ইনপুট নিয়ে এক ধাপ এক ধাপ করে নিজে হিসেব করুন)। এতে কনসেপ্ট একদম পরিষ্কার হয়ে যাবে। [31:22]

[

Largest Rectangle in Histogram | Best Solution & Code

Shradha Khapra · 59K views

](http://www.youtube.com/watch?v=ysy1o-QEj3k)