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 কোডটি এখানে দিয়ে দিচ্ছি, কিন্তু আমরা সেটি দেখার আগে অবশ্যই নিজেরা চেষ্টা করব।
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন