টু পয়েন্টার (Two Pointers)

ধরুন আপনার কাছে অনেকগুলো সংখ্যার একটা সারি বা অ্যারে আছে, আর আপনাকে এমন দুটো সংখ্যা খুঁজে বের করতে হবে, যাদের যোগফল একটা নির্দিষ্ট টার্গেটের সমান। বোকা বা সাধারণ মাথায় চিন্তা করলে আমরা কী করি? বাম হাতের একটা আঙুল প্রথম সংখ্যার উপর রাখি, তারপর ডান হাতের আঙুল দিয়ে বাকি সবগুলোর সাথে মিলিয়ে দেখি। এরপর বাম হাতের আঙুল দ্বিতীয় সংখ্যায় নিয়ে যাই, আবার চেক করি। এভাবে ডাবল লুপ (nested loop) চালালে সময় লাগে O(n²)।

টু পয়েন্টার (Two Pointers) টেকনিক হলো এমন একটা চালাক বা স্মার্ট পদ্ধতি, যেখানে অ্যারের ভেতর একই সাথে দুইটা ভেরিয়েবল (যাদের আমরা পয়েন্টার বা আঙুল বলি) সরিয়ে সরিয়ে একদম এক চান্সেই বা ওয়ান-পাসেই (One pass) — অর্থাৎ মাত্র O(n) সময়ে — কাজটা করে ফেলা যায়।

প্যাটার্ন ১: দুই মাথা থেকে আসা (Converging Pointers)

এটা হলো সবচেয়ে পরিচিত ও কমন টু-পয়েন্টার প্যাটার্ন। এই পদ্ধতিতে একটা আঙুল বা পয়েন্টার রাখা হয় সাজানেন (sorted) অ্যারের একদম শুরুতে (left = 0), আর অন্য আঙুল রাখা হয় একদম শেষে (right = n - 1)।

ধরুন [১, ২, ৩, ৪, ৬, ৮, ৯] অ্যারে থেকে এমন দুটো সংখ্যা খুঁজতে চাই যাদের যোগফল ১০:

• প্রথমে চেক করুন: left (১) + right (৯) = ১০। পেয়ে গেছি!
• যদি যোগফল ১০-এর চেয়ে ছোট হতো (ধরুন টার্গেট ১২), তাহলে আমরা left পয়েন্টারটাকে এক ঘর ডানে বা সামনে নিতাম, যাতে একটা বড় সংখ্যা পাওয়া যায়।
• যদি যোগফল ১০-এর চেয়ে বড় হতো (ধরুন টার্গেট ৮), তাহলে আমরা right পয়েন্টারটাকে এক ঘর বামে বা পেছনে আনতাম, যাতে একটা ছোট সংখ্যা পাওয়া যায়।

যেহেতু অ্যারেটা ছোট থেকে বড় সাজানেন থাকে, তাই আপনি সবসময় কনফিডেন্টলি বুঝতে পারবেন যে কখন কোন পয়েন্টারটা সরাতে হবে।

প্যাটার্ন ২: কচ্ছপ ও খরগোশ (Slow and Fast Pointers)

এই পদ্ধতিতে দুটো পয়েন্টারই এক জায়গা থেকে দৌড় শুরু করে, কিন্তু তাদের দৌড়ানোর স্পিড বা গতি থাকে আলাদা। ধরুন "খরগোশ" (fast pointer) এক লাফে ২ ঘর যায়, আর "কচ্ছপ" (slow pointer) প্রতিবার মাত্র ১ ঘর যায়।

লিংকড লিস্টের (Linked list) দুনিয়ায় এটা খুব ফেমাস একটা ট্রিক। এটা দিয়ে যা যা করা যায়:

• ঠিক মাঝখানের পয়েন্টটা খুঁজে বের করা: যখন খরগোশ লাফাতে লাফাতে একদম শেষ মাথায় পৌঁছাবে, তখন কচ্ছপ ঠিক মাঝরাস্তায় বা লিস্টের ঠিক ৫০% জায়গায় থাকবে!
• চক্র বা সাইকেল (Cycle) ধরা: যদি লিস্টের শেষে কোনো গোল চক্র বা লুপ থাকে, তবে খরগোশ এক সময় ঘুরতে ঘুরতে পেছন থেকে এসে কচ্ছপকে ধরে ফেলবে বা একই জায়গায় মিলিত হবে (ফ্লয়েডের সাইকেল ডিটেকশন দেখুন)।

প্যাটার্ন ৩: একই দিকে হাঁটা (Same Direction)

কখনো কখনো দুটো পয়েন্টার একই স্পিডে হাঁটে, কিন্তু তাদের মধ্যে নির্দিষ্ট একটা দূরত্ব বা গ্যাপ থাকে (যেমন স্লাইডিং উইন্ডো)। আবার ধরুন একটা লিস্ট থেকে ডুপ্লিকেট (duplicate) বা একই জিনিস ডিলিট করতে হবে: তখন ফাস্ট পয়েন্টার শুধু সামনে পড়ে পড়ে যায়, আর স্লো পয়েন্টার শুধু ইউনিক বা নতুন ডেটা পেলে তবেই জায়গা মতো রাইট (write) করে বা লেখে।