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

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

	#include <bits/stdc++.h>
	using namespace std;
	int a[101010];
	int main()
	{
	int n, x;
	cin >> n >> x;
	for(int i = 0; i < n; i++)cin >> a[i];
	for(int i = 0; i < n; i++)
	{
	for(int j = i+1; j < n; j++)
	{
	if(a[i] + a[j] == x)
	{
	cout << a[i] << ", " << a[j] << endl;
	return 0;
	}
	}
	}
	cout << "There are no values" << endl;
	return 0;
	}

view raw two_pointer_naive.cpp hosted with ❤ by GitHub

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

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

	#include <bits/stdc++.h>
	using namespace std;
	int a[101010];
	void two_pointer(int n, int x)
	{
	int i = 0;
	int j = n - 1;
	while(i < j)
	{
	if(a[i] + a[j] == x)
	{
	cout << a[i] << ", " << a[j] << endl;
	return;
	}
	else if(a[i] + a[j] < x)i++;
	else j--;
	}
	cout << "There are no values" << endl;
	}
	int main()
	{
	int n,x;
	cin >> n >> x;
	for(int i = 0; i < n; i++)cin >> a[i];
	two_pointer(n, x);
	return 0;
	}

view raw two_pointer.cpp hosted with ❤ by GitHub

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

১ম প্রব্লেম

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

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

	#include <bits/stdc++.h>
	using namespace std;
	int a[101010];
	int b[101010];
	void two_pointer(int first_size, int second_size, int x)
	{
	int maximum = 9999999999;
	int first_index,last_index;
	int l = 0, r = second_size-1;
	while(l < first_size && r >= 0)
	{
	int sum = a[l] + b[r];
	if(abs(sum - x) < maximum)
	{
	first_index = l;
	last_index = r;
	maximum = sum - x;
	}
	if(a[l] + b[r] < x)l++;
	else r--;
	}
	cout << "Closest pair = " << a[first_index] << ", " << b[last_index] << endl;
	}
	int main()
	{
	int first_size, second_size, x;
	cin >> first_size >> second_size >> x;
	for(int i = 0; i < first_size; i++)cin >> a[i];
	for(int i = 0; i < second_size; i++)cin >> b[i];
	two_pointer(first_size, second_size, x);
	return 0;
	}

view raw tp_closest_pair.cpp hosted with ❤ by GitHub

২য় প্রব্লেম

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

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

	#include <bits/stdc++.h>
	using namespace std;
	int a[101010];
	void two_pointer_triplet(int n)
	{
	sort(a, a+n);
	for(int i = 0; i < n-1; i++)
	{
	int l = i+1;
	int r = n-1;
	int val = a[i];
	while(l < r)
	{
	if(val + a[l] + a[r] == 0)
	{
	cout<< "Triplet : " << val << "," << a[l] << "," << a[r] << endl;
	return;
	}
	else if(val + a[l] + a[r] < 0)l++;
	else r--;
	}
	}
	cout << "No triplet found" << endl;
	}
	int main()
	{
	int n;
	cin >> n;
	for(int i = 0; i < n; i++)cin >> a[i];
	two_pointer_triplet(n);
	return 0;
	}

view raw tp_triplet.cpp hosted with ❤ by GitHub

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

৩য় প্রব্লেম

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

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

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

	#include <bits/stdc++.h>
	using namespace std;
	int a[101010];
	void two_pointer_triplet_sum(int n)
	{
	sort(a, a+n);
	for(int i = n-1; i >= 0; i--)
	{
	int l = 0;
	int r = i-1;
	int val = a[i];
	while(l < r)
	{
	if(a[l] + a[r] == val)
	{
	cout<< "Triplet : " << val << "," << a[l] << "," << a[r] << endl;
	return;
	}
	else if(val > a[l] + a[r])l++;
	else r--;
	}
	}
	cout << "No triplet found" << endl;
	}
	int main()
	{
	int n;
	cin >> n;
	for(int i = 0; i < n; i++)cin >> a[i];
	two_pointer_triplet_sum(n);
	return 0;
	}

view raw tp_triplet_sum.cpp hosted with ❤ by GitHub

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

প্র্যাকটিস প্রব্লেম (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