Easy Peasy, Lemon Squeezy

সাবটাস্ক 2 এর জন্যঃ
সাবটাস্ক 1 এর জন্য একটা অ্যারে রেখে মিনিমাম এবং ম্যাক্সিমাম বের করার জন্য পুরা অ্যারে ট্রাভার্স করা যেতে পারে। ওর্স্ট কেস কমপ্লেক্সিটি O(n2)।

সাবটাস্ক 2 এর জন্যঃ
সাবটাস্ক 2 এর জন্য একটা মাল্টিসেট রেখে লগ ফ্যাক্টরে অ্যাড অথবা ইরেজ করা যেতে পারে। যেহেতু সেট অলরেডি সর্ট অবস্থায় থাকে, তাই মিনিমাম এবং ম্যাক্সিমাম O(1) এ বের করা যায়। সুতরাং এটার জন্য ওর্স্ট কেস কমপ্লেক্সিটি O(n log(n)).

সাবটাস্ক 3 এর জন্যঃ
যেহেতু রিমুভ অপারেশন শুধু ব্যাক থেকে, আমাদের ম্যাক্সিমাম বের করার সময় ছোট এবং মিনিমাম বের করার জন্য বড় এলিমেন্ট গুলা কনসিডার না করলেও চলে। কীভাবে?
ধরে নেয়া যাক, আমাদের অ্যারে A = [5]। তখন 1, 2 3, 4, 5 ইত্যাদি অ্যাড করলে এদের ম্যাক্সিমাম এর উপর কোনো ইফেক্ট থাকে না। এখনও ম্যাক্সিমাম 5, যতক্ষণ না আমাদের অ্যারে এর শেষ থেকে 5 রিমুভ করা লাগছে। সুতরাং আমরা নতুন আসা এলিমেন্ট শেষে অ্যাড করার পরিবর্তে বর্তমান ম্যাক্সিমাম অর্থাৎ 5 অ্যাড করতে পারি। এখন যদি আমাদের 5 এর থেকে বড় ভ্যালু আসে, আমরা এখন থেকে সেই বড় ভ্যালুটি অ্যাড করা শুরু করবো। উদাহরণস্বরূপঃ আমাদের [5, 1, 2, 3, 4, 5, 7] একটার পর আরেকটা অ্যাড করতে হবে। তখন আমাদের ম্যাক্সিমাম এর অ্যারে হবে [5, 5, 5, 5, 5, 7]। ম্যাক্সিমাম পেতে আমাদের শুধু অ্যারে এর লাস্ট এলিমেন্ট চেক করা লাগবে।

মিনিমাম এর জন্যেই আমাদের একই কাজ করতে হবে। ধরে নেয়া যাক আমাদের অ্যারে A = [2]। তখন থেকে 2, 3, 4, 5 অ্যাড করাতে মিনিমাম এর উপর কোনো ইফেক্ট নেই। এখনও মিনিমাম 2, যতক্ষণ না আমরা এটাকে ব্যাক থেকে রিমুভ করছি। সুতরাং আমরা নতুন এলিমেন্ট অ্যাড না করে বর্তমান মিনিমাম, অর্থাৎ 2 অ্যাড করতে থাকবো। এখন যদি 2 এর থেকে ছোট কোনো এলিমেন্ট আসে, আমরা তখন থেকে সেই ছোট ভ্যালুটি অ্যাড করতে থাকবো। উদাহরণস্বরূপঃ আমাদের [2, 3, 4, 5, 1] একটার পর আরেকটা অ্যাড করতে হবে। তাহলে তখন আমাদের মিনিমাম অ্যারে হবে [2, 2, 2, 2, 1]। মিনিমাম পেতেও অ্যারে এর শুধুমাত্র শেষ এলিমেন্টটি চেক করা লাগবে।

এটা করার জন্য আমাদের এমন একটা ডেটা স্ট্রাকচার লাগবে যেটা শেষ থেকে O(1) এ অ্যাড অথবা রিমুভ করতে পারে। আমরা এটার জন্য স্ট্যাক ইউজ করতে পারি। মিনিমাম আর ম্যাক্সিমাম এর জন্য আমাদের দুইটা আলাদা স্ট্যাক লাগবে। যেহেতু মিনিমাম / ম্যাক্সিমামও O(1) এ বের করা যায়, তাই প্রবলেমটি আমরা ইনপুট টাইমে সল্ভ করতে পারি।