স্লাইডিং উইন্ডো (Sliding Window)

"সাব-অ্যারে" মানে হলো একটা অ্যারের ভেতর থেকে টানা বা সিরিয়ালি নেওয়া কয়েকটা উপাদান। ধরুন, আপনাকে একটা অ্যারে থেকে পরপর থাকা ৩টা সংখ্যার সবচেয়ে বড় যোগফল (max sum) বের করতে বলা হলো। বোকা মাথায় আমরা কী করব? প্রতিটা ৩টা সংখ্যার গ্রুপ আলাদা আলাদা করে চেক করব। ইনডেক্স ০ থেকে শুরু করে ০-১-২ দেখব। তারপর ইনডেক্স ১ থেকে ১-২-৩ দেখব। তারপর ২ থেকে ২-৩-৪। খেয়াল করে দেখুন, মাঝখানের সংখ্যাগুলো বারবার খামোখা ক্যালকুলেট করা হচ্ছে! এতে সময় লাগবে O(n*k)।

স্লাইডিং উইন্ডো (Sliding Window) ট্রিকটা আপনাকে এই বারবার একই কাজ করা থেকে বাঁচায়। কল্পনা করুন, আপনি একটা ফিজিক্যাল ছবির ফ্রেম বা "জানালা" (window) প্রথম ৩টা সংখ্যার ওপর বসিয়েছেন। এবার জানালাটাকে যখন এক ঘর সামনে সরাবেন, তখন পুরো ফ্রেমের ভেতরের সবকিছু নতুন করে যোগ করার কোনো দরকার নেই। আপনি শুধু জানালা থেকে বামদিকে যে সংখ্যাটা বেরিয়ে গেল তা বিয়োগ করবেন, আর ডানদিক দিয়ে নতুন যে সংখ্যাটা জানালার ফ্রেমে ঢুকল তা যোগ করবেন। ব্যস! এর ফলে পুরো প্রসেসটা চোখের পলকে O(n) স্পিডে শেষ হয়ে যাবে!

প্যাটার্ন ১: ফিক্সড-সাইজ উইন্ডো (Fixed-size Window)

এই প্যাটার্নটা তখনই ব্যবহার করা হয় যখন প্রশ্নের মধ্যেই জানালার সাইজ বা k বলে দেওয়া থাকে (যেমন: "টানা k-টা সংখ্যার সবচেয়ে বড় যোগফল বের করুন")।

1. প্রথমে k সাইজের প্রথম জানালার যোগফল বা রেজাল্ট বের করুন।
2. এটাকে আপাতত আপনার সবচেয়ে ভালো/ম্যাক্সিমাম রেজাল্ট হিসেবে সেভ করে রাখুন।
3. এবার k থেকে শুরু করে অ্যারের শেষ পর্যন্ত একটা লুপ ঘোরান।
4. প্রতি ধাপে, আগের রেজাল্টের সাথে শুধু নতুন ঢোকা সংখ্যাটা (arr[i]) যোগ করুন এবং পেছনে ফেলে আসা সংখ্যাটা (arr[i-k]) বিয়োগ করুন। এরপর চেক করুন নতুন রেজাল্টটা আগের ম্যাক্সিমামের চেয়ে বড় কি না।

প্যাটার্ন ২: ডায়নামিক-সাইজ উইন্ডো (Dynamically-sized Window)

সবসময় জানালার সাইজ ফিক্সড থাকে না। হয়তো প্রশ্ন করা হলো: "সবচেয়ে ছোট সেই সাব-অ্যারেটা খুঁজে বের করুন, যার যোগফল S-এর সমান বা বড়"। এখানে জানালাটা রবারের মতো বড়-ছোট (accordion) হতে পারে।

এক্ষেত্রেও আমরা left আর right নামে দুটো পয়েন্টার ব্যবহার করি:

• প্রথমে right পয়েন্টারটাকে সামনে এগিয়ে জানালাটাকে বড় করতে থাকুন, আর প্রতিটা নতুন সংখ্যাকে টোটাল যোগফলের সাথে মেলাতে থাকুন।
• যখন এই চলতি যোগফলটা আপনার শর্ত পূরণ করবে (যেমন: >= S), তখন left পয়েন্টারটাকে ডানে সরিয়ে জানালাটাকে যতটা সম্ভব ছোট করার চেষ্টা করুন (আর বামের জায়গাগুলো বিয়োগ করে দিন)। প্রতিবার ছোট করার সময় উইন্ডোর সাইজটা বা দৈর্ঘ্য সেভ করে রাখুন।
• বাম দিক থেকে সরাতে সরাতে যখন শর্তটা ভেঙে যাবে, তখন আবার right পয়েন্টারটাকে ডানে সরিয়ে জানালা বড় করা শুরু করুন।

যদেবেন এখানে একটা for লুপের ভেতর আরেকটা while লুপ চলে, তবুও left আর right দুটো পয়েন্টারই সবসময় শুধু সামনের দিকে এগিয়ে যায় (কখনো পেছনে ফেরে না)। মানে প্রতিটা সংখ্যা জীবনে সর্বোচ্চ দুবার প্রসেস হয়। তাই এর স্পিড O(n)-ই থাকে! এই কনসেপ্টটা টু পয়েন্টার (Two Pointer) টেকনিকের সাথে গভীরভাবে সম্পর্কিত।