টু পয়েন্টার হলো এমন একটি সমস্যা সমাধানের উপায় যেখানে আমরা দুইটি পয়েন্টার ব্যবহার করে কম রানটাইমে সমস্যার সমাধান করি। এখানে পয়েন্টার মানে শুধু c/c++ এর পয়েন্টার বুঝায় না, এখানে পয়েন্টার মানে বুঝায় যেকোনো দুইটি ভ্যারিয়েবল যা অ্যারে বা লিস্ট এর দুইটি ইলিমেন্টকে নির্দেশ করে। এই লিখায় আমরা দেখবো টু পয়েন্টার কি, কিভাবে কাজ করে এবং কি ধরনের সমস্যার সমাধান এই টেকনিক দিয়ে করা যায়।
Two pointer technique Bangla tutorial
শুরুতেই একটি উদাহরণ বিবেচনা করা যাক। ধরেন আপনাকে সাইজের একটি অ্যারে দেয়া আছে। এখান থেকে আপনাকে একজোড়া সংখ্যা বের করতে হবে যাদের যোগফল হবে। এই সমস্যা আমরা যদি ব্রুট ফোর্স মেথডে সমাধান করার চেষ্টা করি তাহলে আমরা দুটি লুপ ব্যবহার করতে পারি নেস্টেড ভাবে। এই পদ্ধতি নিচের এলগরিদমের মত করে কাজ করবে।
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | #include <bits/stdc++.h> using namespace std; int main(){ int x=13; int array[]={2,4,5,1,6,3,7,8}; for(int i=0;i<8;i++){ for(int j=i+1;j<8;j++){ if(array[i]+array[j]==x){ cout<<i<<" এবং "<<j<<" আমাদের জোড়া\n"; return 0; } } } } |
এই সমস্যা সমাধানে ব্রুট ফোর্স এর সুবিধা হলো অ্যারে সর্ট করার দরকার নেই। কিন্তু সমস্যা গুরুতর। এই সমাধানের টাইম কমপ্লেক্সিটি । সুতরাং এর মান বড় হলে আমাদের ব্রুট ফোর্স কাজ করবে না।
টু পয়েন্টার টেকনিকের মাধ্যমে সমাধান
এই সমস্যাটি আমরা টু পয়েন্টার টেকনিকে সমাধান করতে পারবো। যদি সর্টেড অ্যারে ইনপুট দেয়া হয় তাহলে কমপ্লেক্সিটি , নয়তো আমাদের সর্ট করে নিতে হবে। সেক্ষেত্রে । চলুন দেখি কিভাবে টু পয়েন্টার দিয়ে আমরা কাজটি করতে পারি। চলুন ধাপে ধাপে আমরা দেখি কিভাবে করবো।
ধাপ 0ঃ যদি অ্যারেটি সর্টেড না হয় তাহলে সর্ট করে নেই।
ধাপ ১ঃ টু পয়েন্টার টেকনিকে সমস্যা সমাধানের জন্য প্রথমে আমাদের দুইটা পয়েন্টার লাগবে অ্যারের দুইটি ইনডেক্স নির্দেশ করার জন্য। এই দুইটি ইনডেক্স নেয়ার পদ্ধতি পুরোপুরি সমস্যার উপর নির্ভর করে। এই সমস্যার জন্য আমরা ২টি পয়েন্টারের একটি নিবো ইন্ডেক্স এ আরেকটি তম ইন্ডেক্স এ।
ধাপ ২ঃ আমাদের পয়েন্টার গুলোকে সরানোর জন্য স্ট্রেটেজি দরকার। চলুন আমরা আমাদের স্ট্রেটেজি নির্ধারণ করি। ধরেন আমাদের এই অ্যারেটি এমন, এবং । দুটি পয়েন্টার নিলাম। এখন লক্ষ করি, যদি আমরা কে স্থির রেখে থেকে করি, তাহলে । যেহেতু অ্যারেটি সর্টেড, তাই এর মান বাড়ালে যোগফল বাড়বে এবং এর মান হ্রাস করলে যোগফল কমে যাবে।
সুতরাং আমাদের স্ট্রাটেজিটি হলো, যদি হয় তবে এর মান বাড়াবো (যেহেতু মান x এর কম আছে এবং আমাদের x এর কাছাকাছি যেতে হবে) নতুবা এর মান কমাবো। এই বাড়ানো কমানো ততক্ষণ চলবে যতক্ষণ অথবা না হয়। এর ফলে আমরা অপটিমালি আমাদের সল্যুশন পেয়ে যাবো। চলুন কোড করে ফেলি,
Two pointer technique: Problem solution visualization
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | #include <bits/stdc++.h> using namespace std; int main(){ int x=13; int array[]={1,2,3,4,5,6,7,8}; int l=0,r=7; while(l!=r){ if(array[l]+array[r]>x){ r--; }else if(array[l]+array[r]<x){ l++; }else{ cout<<array[l]<<" এবং "<<array[r]<<" আমাদের সল্যুশন\n"; break; } } } |
এই পদ্ধতিটির টাইম কমপ্লেক্সিটি কারণ আমরা একটি লুপেই অ্যারেটির উপর ঘুরেছি।
উপরের সমস্যা খেয়াল করলে দেখতে পারি যে, অ্যারেটি সর্টেড হবার জন্য আমাদের সিন্ধান্ত নিতে সুবিধা হয়েছে। এমন ভাবে টু পয়েন্টার মেথডের আরও কিছু ভেরিয়েশন রয়েছে। যেমন দুইটি পয়েন্টারকেই একই জায়গা থেকে শুরু করা। এই ভেরিয়েশন নিয়ে আমরা পরের লিখা গুলোতে আলোচনা করবো।
আরও জানতে এই লিখা পড়তে পারেন।
