স্লাইডিং উইন্ডো ম্যাক্সিমাম প্রবলেম সলভ করার সহজ গাইড

হ্যালো! আজকের এই ভিডিওতে আমরা ডাটা স্ট্রাকচার এবং অ্যালগরিদমের (DSA) একটি বেশ গুরুত্বপূর্ণ এবং একটু কঠিন লেভেলের প্রবলেম নিয়ে কথা বলবো, যার নাম হলো Sliding Window Maximum। এটি লিটকোড (LeetCode)-এর ২৩৯ নম্বর সমস্যা। সহজ করে বললে, আমাদের একটা বড় নাম্বারের লিস্ট দেওয়া থাকবে এবং একটা উইন্ডো সাইজ 'k' দেওয়া থাকবে। আমাদের কাজ হলো, ওই সাইজের সবকটি সাব-অ্যারের (ছোট ছোট অংশ) মধ্যে সবচেয়ে বড় নাম্বারটি খুঁজে বের করা।

---

১. স্লাইডিং উইন্ডো ম্যাক্সিমাম কী? (Introduction)

এই টপিকটি বোঝার আগে কল্পনা করুন আপনার কাছে এক সারি নাম্বার আছে। 'k' হলো একটি ফ্রেম বা জানালার মতো। ধরুন k=৩, তার মানে আপনি একবারে ৩টি নাম্বার দেখতে পাবেন। আপনি এই জানালাটি বাম থেকে ডানে সরাবেন (স্লাইড করবেন) এবং প্রতিবার ওই জানালার ভেতরে থাকা সবচেয়ে বড় সংখ্যাটি খাতায় লিখবেন। সবশেষে যে লিস্টটি পাবেন, সেটাই আপনার উত্তর।

---

২. উদাহরণের মাধ্যমে কনসেপ্ট ক্লিয়ার করা (Concept Details)

ভিডিও রেফারেন্স: [01:04]

ধরা যাক একটি অ্যারে আছে: [1, 3, -1, -3, 5, 3, 6, 7] এবং জানালার সাইজ k = 3।

• প্রথম জানালা: [1, 3, -1] -> বড় সংখ্যা: 3

• জানলা এক ধাপ সরালে: [3, -1, -3] -> বড় সংখ্যা: 3

• পরের ধাপ: [-1, -3, 5] -> বড় সংখ্যা: 5

• পরের ধাপ: [-3, 5, 3] -> বড় সংখ্যা: 5

• পরের ধাপ: [5, 3, 6] -> বড় সংখ্যা: 6

• শেষ ধাপ: [3, 6, 7] -> বড় সংখ্যা: 7

তাহলে আমাদের আউটপুট হবে: [3, 3, 5, 5, 6, 7]।

সহজ ভাষায় ব্যাখ্যা: এখানে Sliding Window বলতে বোঝানো হচ্ছে একটা নির্দিষ্ট সীমানার মধ্যে ডাটা দেখা। আর Maximum মানে হলো সেই সীমানার সবথেকে বড় মান।

---

৩. সাধারণ সমাধান বনাম উন্নত সমাধান (Brute Force vs Optimal)

ভিডিও রেফারেন্স: [02:11]

• সাধারণ পদ্ধতি (Brute Force): আমরা যদি প্রতিবার লুপ চালিয়ে বড় সংখ্যা খুঁজি, তবে সময় অনেক বেশি লাগবে (Time Complexity: O(n∗k))। বড় ডাটার ক্ষেত্রে এই পদ্ধতি ফেল করবে।

• উন্নত পদ্ধতি (Optimal Solution): আমরা Deque (Double Ended Queue) ব্যবহার করবো। এর মাধ্যমে আমরা মাত্র একবার পুরো লিস্টটি দেখেই (Time Complexity: O(n)) উত্তর বের করতে পারবো।

কঠিন শব্দের ব্যাখ্যা:

• Deque (ডি-কিউ): এটি এমন এক ধরনের লাইন (Queue), যেখানে আপনি সামনে এবং পিছনে—উভয় দিক দিয়েই ডাটা ঢোকাতে বা বের করতে পারেন।

---

৪. ডি-কিউ (Deque) ব্যবহারের লজিক

ভিডিও রেফারেন্স: [04:40]

আমরা ডি-কিউতে ভ্যালু না রেখে ভ্যালুর ইনডেক্স (অবস্থান) রাখবো। আমাদের দুটি নিয়ম মানতে হবে: ১. জানালার বাইরে চলে যাওয়া ইনডেক্সগুলোকে সামনে থেকে বের করে দিতে হবে। ২. নতুন কোনো বড় সংখ্যা এলে, তার চেয়ে ছোট সব সংখ্যাকে ডি-কিউয়ের পিছন থেকে বের করে দিতে হবে। কারণ, ছোট সংখ্যাগুলো আর কখনোই ম্যাক্সিমাম হতে পারবে না।

---

৫. কোডিং সমাধান (C++ Code Snippet)

নিচে ভিডিওতে দেখানো সমাধানটি সহজভাবে দেওয়া হলো:

C++

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq; // ইনডেক্স রাখার জন্য
    vector<int> result;

    for (int i = 0; i < nums.size(); i++) {
        // ১. উইন্ডোর বাইরের ইনডেক্স বের করে দাও
        if (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // ২. নতুন সংখ্যার চেয়ে ছোট সংখ্যাগুলো পিছন থেকে সরাও
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back();
        }

        // ৩. বর্তমান ইনডেক্স যোগ করো
        dq.push_back(i);

        // ৪. প্রথম উইন্ডো পূর্ণ হলে রেজাল্টে ম্যাক্সিমাম ভ্যালু নাও
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    return result;
} 

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

• dq.pop_front(): জানালা সামনে এগিয়ে গেলে পেছনের পুরনো ডাটা মুছে ফেলার জন্য।

• dq.pop_back(): নতুন শক্তিশালী (বড়) সংখ্যা এলে দুর্বল (ছোট) সংখ্যাগুলোকে লাইন থেকে সরিয়ে দেওয়ার জন্য।

• nums[dq.front()]: লাইনের একদম সামনে সবসময় জানালার সবথেকে বড় সংখ্যাটি থাকে।

---

৬. আমার বিশ্লেষণ ও শেষ কথা (Analysis & Perception)

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

বাস্তবতা ও সম্ভাবনা: ১. টাইম কমপ্লেক্সিটি: O(n), যা অত্যন্ত দ্রুত। ২. স্পেস কমপ্লেক্সিটি: O(k), কারণ ডি-কিউতে বড়জোর জানালার সমান ডাটা থাকে। ৩. বিকল্প: আপনি চাইলে 'Priority Queue' বা 'Heap' ব্যবহার করতে পারেন, কিন্তু সে ক্ষেত্রে সময় কিছুটা বেশি (O(nlogk)) লাগবে। তাই Deque-ই সেরা।

পরামর্শ: আপনি যদি বিগিনার হন, তবে প্রথমে হাতে-কলমে ড্রাই-রান (খাতায় কোড পরীক্ষা) করুন। ইনডেক্স কীভাবে ডি-কিউ থেকে সরছে তা বুঝতে পারলে পুরো বিষয় স্লাইডিং উইন্ডোর মতো আপনার মাথায় পরিষ্কার হয়ে যাবে। এই টেকনিকটি স্টক মার্কেট ডাটা বা রিয়েল-টাইম সেন্সর ডাটা প্রসেসিংয়ে খুব কাজে লাগে।

[

L81. Sliding Window Maximum | Queue

Shradha Khapra · 87K views

](http://www.youtube.com/watch?v=XwG5cozqfaM)