২ - পয়েন্টার টেকনিক (Two Pointer Technique)

কোন অ্যারেতে (সর্টেড) সাধারনত জোড়ায় জোড়ায় ভ্যালু খুঁজে বের করার একটি এফিশিয়েন্ট টেকনিক হল ২-পয়েন্টার। আমরা মূলত, কোন সর্টেড অ্যারেতে ২ বা তার বেশি জোড় বের করবো এমনভাবে, যেন তারা কোন কন্ডিশন মেনে চলে। যেমনঃ এমন ১ জোড়া ভ্যালু বের কর যাদের যোগফল X এর সমান হয়, অথবা বিয়োগফল, বা গুনফল ইত্যাদি।
প্রথমে একটি প্রবলেম নিয়ে আলোচনা করা যাক। আমাদের একটি সর্টেড (ছোট থেকে বড়) অ্যারে দেয়া আছে। এখান থেকে এমন একটি জোড়া বের করতে হবে, যাতে তাদের যোগফল X এর সমান হয়। এবং জোড়ার ২ টির ইন্ডেক্স একই হওয়া যাবেনা। আমরা কোড করলে অনেকটা এভাবে ২ টি লুপ চালায়ে করে ফেলবোঃ

এর কপ্লেক্সিটি O(n*(n-1)) যা অনেক বেশি। আমাদের আরও ভালো এপ্রোচ লাগবে। এখন দেখা যাক এই প্রব্লেমটার জন্য ২-পয়েন্টার কিভাবে কাজ করবেঃ

আমরা প্রথমে ২ টি পয়েন্টার সেট করবো। একটি হবে প্রথম ভ্যালুর জন্য, অপরটি হবে দ্বিতীয় ভ্যালুর জন্য। আমরা প্রত্যেকবার চেক করবো X এর সাথে ভ্যালু ২ টির যোগফল মিলে যাচ্ছে কিনা। যদি যোগফল X এর চেয়ে কম হয়, তাহলে আমরা প্রথম পয়েন্টারকে ডানদিকে বাড়াবো। যদি যোগফল X এর চেয়ে বেশি হয়, তাহলে আমরা দ্বিতীয় পয়েন্টারকে বামদিকে কমাবো। অনেকটা বাইনারি সার্চ এর মত কাজ করবে এই ২- পয়েন্টার। এবং আমাদের কন্ডিশন অনুযায়ী প্রথম এবং দ্বিতীয় ভ্যালুর ইনডেক্স সেইম হওয়া যাবেনা। ২ পয়েন্টার এর প্রথমটিকে আমরা 0 (এখানে অ্যারের প্রথম ইনডেক্স 0 ধরে ) এবং পরের পয়েন্টারকে আমরা অ্যারের শেষ ইনডেক্স দিয়ে ইনিশিয়ালাইজ করবো। কোডঃ

এর কমপ্লেক্সিটি হবে O(n)। এখন কিছু ভ্যারিয়েশন দেখা যাকঃ

১ম প্রব্লেম

২ টি সর্টেড অ্যারে(ভিন্ন ভিন্ন সাইজ) থেকে আমাদের এমন ২ টি এলেমেন্ট নিতে হবে (প্রত্যেক অ্যারে থেকে ১ টি), যাতে তাদের যোগফল X এর সমান বা ছোট (ম্যাক্সিমাম যোগফল, অর্থাৎ X এর কাছাকাছি হয়)।

আমরা প্রথম অ্যারেতে একটি পয়েন্টার এবং দ্বিতীয় অ্যারেতে আরেকটি পয়েন্টার সেট করবো। এখন প্রতিবার আমরা চেক করবো X এর সমান অথবা আমাদের ম্যাক্সিমাম সাম X এর কাছাকাছি কিনা, যদি না হয়, আমরা ইনডেক্স আপডেট করবো। এখন যদি সাম X এর চেয়ে কম হয়, তাহলে আমরা প্রথম অ্যারের ইনডেক্স বাড়াবো, নাহলে দ্বিতীয় অ্যারের ইনডেক্স বাড়াবো। এখানে প্রথম পয়েন্টারকে অ্যারের প্রথম ইনডেক্স এবং পরের পয়েন্টারকে অ্যারের শেষ ইনডেক্স দিয়ে ইনিশিয়ালাইজ করবো। কোডঃ

২য় প্রব্লেম

একটি ভিন্ন ভিন্ন (distinct) এলেমেন্ট এর অ্যারে থেকে এমন একটি ট্রিপলেট (তিন টি এলেমেনট এর জোড়া) বের করতে হবে, যাদের যোগফল শুন্য হবে।

২ জোড়ার জন্য আমরা যেভাবে করতাম, এটাও একইভাবে হবে, খালি এক্সট্রা একটি ভ্যালুর জন্য আমরা আগেই একটি ভ্যালু নিয়ে নিব। প্রথমে অ্যারেকে সর্ট করে ফেলবো। এরপরে আমরা আগের মতন যেভাবে জোড়া বের করতাম, একইভাবে এখানেও সেই কাজ করবো। এখানে আমরা একটি ইনডেক্স কে ফিক্সড করে, বাকি ইনডেক্স এর মাঝে ২ টি পয়েন্টার ঠিক আগের মতন করে সেট করবো। কোড দেখা যাকঃ

এখন এভাবে আমরা যেকোন একটি ট্রিপলেট পেলেই প্রোগ্রাম স্টপ করপে দিচ্ছি। যদি আমাদের বলা হয় যে এরকম যত ট্রিপলেট আছে তাদের দেখাও, তাহলে উপরের কোড এ সামান্য একটু পরিবর্তন করলেই আমরা সব ট্রিপলেট পেয়ে যাবো। আমরা লাইন ২১ এ রিটার্ন না করে, l++ এবং r-- করে দিবো। তাহলেই কাজ হয়ে যাচ্ছে।

৩য় প্রব্লেম

আমাদের যদি কোন ট্রিপলেট বের করতে বলে, যাদের যোগফল X এর সমান হবে, আমরা সেইম উপরের টেকনিক অনুযায়ী বের করে ফেলতে পারবো।

৪র্থ প্রব্লেম

এমন ট্রিপলেট বের কর, যাতে যেকোন ২ টির যোগফল, তৃতীয় টির সমান হবে।
এই সমস্যাটিও হুবহু আগের মতই কাজ করবে। আমরা প্রথমে একটি এলেমেন্টকে সেট করবো, এরপরে বাকি ২ টি এলেমেন্ট বের করবো যাতে তাদের সাম, সেট করা এলেমেন্ট এর সমান হয়। কোডঃ

২ - পয়েন্টারের প্রব্লেমগুলিতে আমরা ইনডেক্স কে একেকভাবে সেট করতে পারি, এটা আসলে যে কোড লিখছে তার উপর নির্ভর করে। তবে মূল আইডিয়া ঠিক থাকলে প্রব্লেম এর ফাইনাল আউটপুট সবসময় একই আসবে।

প্র্যাকটিস প্রব্লেম (Practice Problems)

• Leetcode: valid-palindrome
• Leetcode: rotate-array
• Leetcode: two-sum-ii-input-array-is-sorted
• Codeforces: wrath
• Codeforces: strange game on matrix
• Codeforces: bersu ball
• Codeforces: guess a number
• Spoj: roommate agreement
• Spoj: audition

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

প্রোগ্রামিং কন্টেস্টে আমাদের অনেক সময় ৩ বা ৪ বা এরচেয়েও বেশি লুপ এর কোড লিখতে হয়। ব্যাসিকালি ব্রুটফোর্স যাকে বলে। এখন আমরা যেই টেকনিক দেখবো, এটি এরকম একাধিক লুপ এর প্রব্লেমকে কম সময়ে সল্ভ করে দিতে পারবে।

স্লাইডিং উইন্ডো সমস্যার বিভিন্ন রূপ আছে। কিন্তু তাদের সবারই একটি কমন বৈশিষ্ট আছে : একটি সাব-অ্যারেকে (আমরা একে 'উইন্ডো' বলে থাকি, যা স্ট্যাটিক বা ডাইনামিক দৈর্ঘ্য থাকতে পারে) আমরা  n সংখ্যক উপাদানগুলির অ্যারে এর বাম থেকে ডান দিকে লিনিয়ারভাবে সরায়ে কিছু কম্পিউট করার চেষ্টা করবো। এভাবে উইন্ডো স্লাইড করার টেকনিক কেই স্লাইডিং উইন্ডো বলে। স্লাইডিং উইন্ডোর অনেক রকম ভ্যারিয়েশন আছে। যেমন ঃ 

1. একটি অ্যারের মাঝে ফিক্সড সাইজের কোন সাব-অ্যারের ম্যাক্সিমাম সামেশন বের করা। যেমন ঃ অ্যারে  A = {10, 40, 10, 30, 20} এবং উইন্ডো সাইজ w = 3 হলে, মাক্সিমাম সামেশন = 40+10+30 = 80.
   
2. একটি অ্যারের মাঝে ফিক্সড সাইজের সকল সাব-অ্যারের ম্যাক্সিমাম অথবা মিনিমাম সংখ্যা বের করা। যেমন ঃ
   অ্যারে A = {0, 5, 5, 3, 10, 0, 4} , n = 7 এবং উইন্ডো সাইজ w = 3, হলে এখানে n-w+1 = 5 টি ভিন্ন ভিন্ন সাব-অ্যারে আছে যাদের সাইজ = 3; {0, 5, 5}, {5, 5, 3}, {5, 3, 10}, {3, 10, 0}, {10, 0, 4}. এবং আমরা এদের ম্যাক্সিমাম সংখ্যা বের করতে চাইলে এগুলি হবে ঃ 5, 5, 10, 10, 10 প্রতি সাব-অ্যারের জন্যে।
   
3. একটি অ্যারের মাঝে এমন মিনিমাম দৈর্ঘ্যের সাব-অ্যারে বের কর, যার এলেমেন্ট এর সাম, নির্দিষ্ট কোন সাম S থেকে বড়/ সমান/ ছোট হয়। যেমন ঃ অ্যারে A = {5, 1, 2, 3, 4, 2} এবং S = 7 হলে,
   মিনিমাম দৈর্ঘ্য == 7 : 2,  {5, 1, 2, 3, 4, 2}
   মিনিমাম দৈর্ঘ্য > 7 : 3,  {5, 1, 2, 3, 4, 2} , {5, 1, 2, 3, 4, 2}, {5, 1, 2, 3, 4, 2}
   মিনিমাম দৈর্ঘ্য < 7 : 1,  {5, 1, 2, 3, 4, 2} ; যেকোনটাই হতে পারে।
   
4. একটি অ্যারের মাঝে এমন মিনিমাম দৈর্ঘ্যের সাব-অ্যারে বের কর যাতে  [ 1 to w ] পর্যন্ত সকল সংখ্যা কমপক্ষে একবার করে হলেও থাকবে। যেমনঃ A = {1, 2, 3, 7, 1, 12, 9, 11, 9, 6, 3, 7, 5, 4, 5, 3, 1, 10} এবং w = 4, আমরা 13 length এর একটি সাব-অ্যারে পাবো, যাতে 1, 2, 3, 4 আছে। এই সেইম অ্যারের জন্যে যদি w = 3 হয়, তাহলে A = {1, 2, 3, 7, 1, 12, 9, 11, 9, 6, 3, 7, 5, 4, 5, 3, 1, 10} আমরা 3 length এর একটি সাব-অ্যারে পাবো। 

সলুশন (Solution)
উপরের প্রবেল্মগুলি আমরা নরমালি বারে বারে লুপ চালায়ে সল্ভ করতে পারবো তখনি, যখন রেঞ্জ কম হবে, যা আমাদের given time এর মাঝে সল্ভ করা সম্ভব হয়। আমরা ব্রুটফোর্স এর ব্যাপারগুলি বাদ দিয়ে সরাসরি আমাদের স্লাইডিং উইন্ডো টেকনিক এ চলে আসি, যা কিনা O (n) সময়ে সল্ভ করতে সক্ষম।

১ম টেকনিক (First Technique):

আমরা প্রথমে উইন্ডো তে আমাদের প্রথম w টি ইন্টিজার ইন্সার্ট করে দিলাম এবং এদের সাম বের করে তাকে curr_sum ভ্যারিয়েবল এ রাখলাম। এরপরে আমরা স্লাইড করে করে আগাবো। আমরা ডান পাশে একটি একটি করে এলেমেন্ট উইন্ডো তে ইন্সার্ট করবো এবং বাম দিক থেকে একটি করে সরায়ে দিব, ফলে আমাদের উইন্ডোর সাইজ সেইম থাকবে।এলেমেন্ট ইন্সার্ট এর সময় আমরা চেক রাখবো যে এখন আমরা ম্যাক্সিমাম সাম পেলাম কিনা। প্রতিবার ইন্সার্ট করার সময় আমাদের নতুন সাম হবে curr_sum + inserted_element - removed_element. এভাবে আমরা পুরো অ্যারেকে স্লাইড করে রেসাল্ট পাবো।

২য় টেকনিক (Second Technique):

যদি n এর মান অনেক বড় হয়, সকল সাব-অ্যারের মাক্স/মিন বের করা একটু কঠিন হবে। এজন্য আমরা deque (double ended queue) ব্যবহার করবো। এখন আমাদের উইন্ডো হবে আমাদের deque টি। আমরা deque কে ascending order ( ছোট থেকে বড় ) এ সাজাবো ( যদি মিন বের করতে চাই)। deque এর প্রথম দিকে আমাদের মিনিমাম এলেমেন্ট গুলি থাকবে। কিন্তু এভাবে কাজ করতে গেলে একটি বড় প্রব্লেম হল, আমাদের মূল অ্যারের ইন্ডেক্সগুলি উল্টাপাল্টা হয়ে যাবে, এজন্য আমাদের ইন্ডেক্স এর ট্র্যাক রাখতে হবে যাতে আমরা বুঝতে পারি যে, এলেমেন্ট উইন্ডো তে আছে কি নাই। নিচের একটি স্যাম্পল কোড দেয়া হল ঃ

৩য় টেকনিক (Third Technique):

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

৪র্থ টেকনিক (Fourth Technique):

আমরা এমন একটি উইন্ডো মেইন্টেইন করবো যা কিনা 1 to w সকল সংখ্যা যদি না পাই, উইন্ডো সাইজ বারাতে থাকবে, নাহলে সাইজ কমাতে থাকবে। আমরা মিনিমাম উইন্ডো সাইজের ট্র্যাক রাখবো। 1 to w সকল এলেমেন্ট পেয়ে গেলাম কিনা এটি আমরা নরমাল একটি ফ্রিকুয়েন্সি কাউন্টের মাধ্যমে করতে পারি। যখন সকল এলেমেন্ট এর কাউন্ট >0 হবে, তখন আমরা আমাদের মিনিমাম উইন্ডো সাইজ রিটার্ন করে দিবো।

প্র্যাক্টিস প্রব্লেম (Practice Problems): 

• Uva 1121 (Subsequence)
• Uva 11536 (Smallest-Sub-Array)
• LeetCode 239 (Sliding Window Maximum)
• HackerRank (The Maximum Subarray)
• Spoj (KOIREP - Representatives)
• Codeforces (Bear and Square Grid)