Minimum Stack Problem

Minimum Stack সমস্যাটি একটি অত্যন্ত পরিচিত সমস্যা। আমি এমনও শুনেছি software engineering এর job এর coding interview তে এই সমস্যা সমাধান করতে দেওয়া হয়েছে। এই সমস্যা এবং এর সমস্যা নিয়ে আমরা এখন আলোচনা করব। 

নাম শুনেই আমরা অনুমান করতে পারতেছি যে এটি একটি stack data structure সংক্রান্ত সমস্যা । এই সমস্যায় আমাকে একটি stack দেওয়া থাকবে। এর সাথে আমাদেরকে দুই ধরনের operation এবং দুই ধরনের query দেওয়া হবে। দুই ধরনের operation গুলো হল push ও pop. Push operation এর মাধ্যমে আমাকে stack এ একটি integer push করতে হবে আর pop operation এর মাধ্যমে আমাকে stack এর উপর থেকে একটি integer তুলে নিতে হবে। আবার দুই ধরনের query এর মধ্যে একটি হচ্ছে আমাদেরকে বলতে হবে stack এ আপাতত সবার উপরে থাকা integer এর value কত এবং অপরটি হচ্ছে আপাতত stack এ থাকা integer গুলোর মধ্যে সব থেকে ছোট integer এর value কত । আরেকটি ব্যাপার হচ্ছে আমাদের memory complexity অবশ্যই O(n) হতে হবে। 

আমরা STL stack ব্যবহার করে খুব সহজেই উপরের দুইটি operation এবং প্রথম query এর সমাধান করতে পারি । এখন বাকি থাকে তাহলে দ্বিতীয় ধরনের query. এর জন্য আমরা যেটি করব যে, stack এ আমারা pair<int,int> type এর data রাখবো যেখানে প্রথম integer হচ্ছে stack এ আমরা যেসব element push বা pop করতেছি, আর দ্বিতীয় integer হচ্ছে ওই position থেকে শুরু করে আপাতত stack এর নিচের দিকে শেষ পর্যন্ত যেসকল integer আছে তাদের মধ্যে সব থেকে ছোট integer টি । অর্থাৎ আমরা দ্বিতীয় ধরনের query এর answer হবে  আপাতত stack এর উপরে যে pair of integer আছে তার মধ্যে দ্বিতীয়টি। এটি বের করার জন্য আমাদেরকে শুধু element stack এ push করার সময় current integer এর সাথে আপাতত stack এ থাকা element গুলোর মধ্যে mininum টি কে তুলনা করলেই হচ্ছে । ফলে প্রতি operation এবং প্রতি query এর জন্য আমাদের time complexity হচ্ছে O(1). আর total program এর memory complexity হচ্ছে O(n). 

LeetCode এর Min Stack problem টি same problem. 

(Problem Link : https://leetcode.com/problems/min-stack/ ).

আমরা নিজেরা উপরের idea ব্যবহার করে এই problem এর কোড লিখার চেষ্টা করব। আমি আমার solution কোডটি এখানে দিয়ে দিচ্ছি, কিন্তু আমরা সেটি দেখার আগে অবশ্যই নিজেরা চেষ্টা করব। 

#include<bits/stdc++.h> using namespace std; class MinStack { public:     /** initialize your data structure here. */     stack<pair<int,int> >stk;     int mn;     MinStack() {              }          void push(int x) {         if(!stk.empty())mn = min(stk.top().second,x);         else mn = x;         stk.push({x,mn});     }          void pop() {         stk.pop();     }          int top(){         return stk.top().first;     }          int getMin() {         return stk.top().second;     } }; /**  * Your MinStack object will be instantiated and called as such:  * MinStack* obj = new MinStack();  * obj->push(x);  * obj->pop();  * int param_3 = obj->top();  * int param_4 = obj->getMin();  */

Stack

Stack একটি linear data structure. ধরা যাক আমাদের কাছে কিছু plate আছে এবং এই plate গুলোকে আমরা একটির ওপর আরেকটি রেখে একটি স্তম্ভের মতো বানালাম । এখন স্তম্ভ বানানোর সময় আমরা যে plate টিকে সবার আগে নিয়েছিলাম সেটি সবার নিচে আছে, তাই না? হ্যাঁ । আবার যে plate টিকে ২য় বারে নিয়েছিলাম, সেটি নিচের দিক থেকে ২য় স্থানে আছে । এভাবে সর্বশেষ যে plate টি নিয়েছিলাম সেটি সবার উপরে আছে। এখন এই স্তম্ভের ওপর থেকে যদি আমরা একটি একটি করে plate সরিয়ে নেই, তবে সবার শেষে যেটি রেখেছিলাম সেটি আমরা সবার প্রথমে সরিয়ে নিবো, এরপর দ্বিতীয় সর্বশেষ যেটি রেখেছিলাম সেটি এবং এভাবে সবশেষে যেটি সবার প্রথমে রেখেছিলাম সেটি সরিয়ে নিবো । অর্থাৎ পুরো ব্যপারটি যা দাঁড়ালো সেটি হল - Last in, First out. আমরা যেটিকে শেষে রাখবো সেটিকে সবার আগে সরাবো। 

আমাদের stack data structure টি ঠিক একই ভাবে কাজ করে। Stack এ আমরা যে element সবার আগে push করব, pop বা তুলে নেওয়ার সময় ঠিক উপরের মত সেটি সবার পরে বের হবে। 

Stack data structure সম্পর্কিত সমস্যা সমাধানের জন্য আমরা STL এর stack ব্যবহার করব। এখানের যে function গুলা সবথেকে বেশি দরকার হয় সেগুলা হল push(), pop(), top(), size(), empty(). 

push() : push() ব্যবহার করে আমরা stack এর মধ্যে element রাখি। যেমন: আমরা যদি stack এ পর্যায়ক্রমে 10, 15, 3 এই তিনটি integer কে push করি, তবে সবার নিচে 10 এবং সবার উপরে 3 থাকবে যেটা অনেকটা নিচের ছবির মতো -

pop() : pop() ব্যবহার করে আমরা stack থেকে আপাতত সবার উপরে থাকা element কে তুলে নিতে পারি। যেমন উপরের stack এ আপাতত সবার উপরের element টি হল 3. এখন এই stack এর জন্য যদি আমরা pop() call করি, তবে এটি stack থেকে সবার উপরের element কে তুলে নিবে। ফলে stack এর মধ্যে আর দুইটি element অবশিষ্ট থাকবে। ব্যাপারটি আরও ভালো করে বুঝার জন্য আমরা নিচে ছবিটি লক্ষ করি। 

top() : top() ব্যবহার করে আমরা stack এ আপাতত সবার উপরে কোন element টি আছে সেটি জানতে পারব । যেমন আপাতত উপরে stack এ দুইটি element এর মধ্যে সবার উপরে আছে 15. তাই আমরা যদি top() call করি তবে return value হিসেবে আমরা 15 পাবো। এখানে একটি বিষয় লক্ষণীয় top() function টি শুধু সবার উপরের element কে নির্দেশ (indicate) করবে, pop() এর মত তুলে নিবে না, অর্থাৎ top() call করার পর stack এর কোন পরিবর্তন হবে না। 

size() : এই function আমাদের একটি integer value return করবে যেটি নির্দেশ করে আপাতত stack এ কতগুলো element আছে। যেমন আপাতত উপরের stack এ দুইটি element আছে, তাই এর size হবে 2.

empty() : যদি আমাদের stack এ কোন element না থাকে, তবে এই function টি true return করবে, অন্যথায় false return korbe. যেমন আপাতত উপরের stack এ দুইটি element আছে, তাই এর জন্য empty() call করলে return value হিসেবে আমরা false পাবো।

আমরা যদি উপরের ধাপ গুলোর coding implementation করি, তবে যেমন টা হবে :

#include<bits/stdc++.h> using namespace std; int main(){     stack<int>stk;     stk.push(10);     stk.push(15);     stk.push(3);     stk.pop();     int Top_element = stk.top();     int size_of_stack = stk.size();     bool b = stk.empty(); }