বিশেষ করে codeforces এর অনেক প্রবলেম এর ট্যাগে দেখা যায় "two pointer" ট্যাগ করা আছে । স্বাভাবিক ভাবেই যেহেতু পয়েন্টার কথাটা আছে নামের সাথে আমি অনেকটা সময় ধরে ভাবতাম এই প্রবলেমগুলা হয়তো পয়েন্টার ব্যাবহার করে করা হয় । অনেকটা ছয় অন্ধের হাতি দেখা গল্পের মত । পরে কোডফরসেস এর একটা কমেন্ট এ একজন এর এক্সপ্লেনেশন দেখি । এরপর একদিন বুয়েট ওনিয়ন টিমের সাকিব ভাইয়াকেও জিজ্ঞাসা করছিলাম এই জিনিসটা কি । ভাইয়া একটা প্রবলেম দিয়ে এর সলুশ্যন বলছিলেন কিভাবে হচ্ছে , এই ট্যাকনিক টাই two pointer । এইখানে বলে রাখা ভাল অনেক এর এই ট্যাকনিকে স্লাইডিং উইন্ডো ( যেহেতু একটা বাউন্ডারির মধ্যে কাজ করতে হয় এবং বাউন্ডারিটা একটা রেঞ্জ এর মধ্যে উত্তর দেয় তাই ) বলা হয় , দুইটা আসলে একই জিনিস । two pointer সম্পর্কে আরও কিছু বলার আগে আমরা একটা প্রবলেম দেখি ।
আমাদের বলা হল আমাদের কাছে দুইটা সর্টেট array আছে , আমাদের বলতে হবে এই দুইটা array থেকে একটা একটা ভ্যালু নিয়ে আমরা কতভাবে একটা নাম্বার M বানাতে পারি যাদের কোন মধ্যে কোন ডুপলিকেট ভ্যালু নেই ।
যদি আমরা একটু Naive Method দেখি -
এইখানে আমরা inner এবং outer for loop এর দুইটা relation এর মাধ্যমে খুব সহজে Ans বের করে দিতে পারি ।
আমরা এইখানে N পর্যন্ত দুইটা লুপ চাল্লাচ্ছি । তাই আমাদের টোটাল রানটাইম হয়ে যাচ্ছে O( N ^ 2 ) । আমরা যদি একটু Modification করি আমরা এইটা কমিয়ে O(N) এ নিয়ে আসতে পারি । আমরা দুইটা পয়েন্ট নেই ।
Say low and high । low পয়েন্ট করতেছে আমাদের A array এরটার starting point কে এবং high পয়েন্ট করতেছে আমাদের B array এর ending পজিশনটাকে ।
Observation number one ::
আমরা যদি দেখি A[low] + B[high] > M তাহলে আমরা একটা জিনিস সিউর ভাবে বলতে পারব । আমাদের অবশ্যই B এর ভ্যালু কমাতে হবে । কারণ যেহেতু A[low] হচ্ছে A এর সবথেকে ছোট ভ্যালু সুতরাং তাকে আর কমিয়ে কখনই B[high] এর সাথে add করে M বানানো যাবে না ।
Observation number two :::
আমরা যদি দেখি A[low] + B[high] < M তাহলে আমাদের অবশ্যই low এর ভ্যালু বাড়াতে হবে । কারণ high হচ্ছে B এর সবথেকে বড় ভ্যালু এর থেকে বড় ভ্যালু নাই । high থেকে আমরা কোন ভ্যালু বাড়াতে পারছি না । তাই অবশ্যই আমাদের এখন low থেকে বাড়াতে হবে ।
এইখানে একটা খটকা লাগতে পারে Observation one এ যেহেতু A[] array তে left to right যাওয়া হচ্ছে current low ভ্যালু মানে low যাকে right now point করছে A[] array তে তার থেকেও তো কম ভ্যালু আমার array তে থাকতে পারে । আমরা নিচের কোডটা একটু ভাল মত খেয়াল করলেই দেখতে পাব যে যদি থেকে থাকে এবং তার সাথে যদি high B[] array এর এড যদি M এর সমান হয় তাহলে তা আগেই Ans এর সাথে এড হয়ে আসবে । একদমই একই কাজ হচ্ছে B[] array তেও । এইখানে আমরা condition দিয়ে দুইটা পয়েন্টকে নিয়ন্ত্রণ করছি ।
এইখানে আমরা low and high দুইটা পয়েন্ট merge করে আগাচ্ছি । এই ধরনের ট্যানিক এ প্রবলেম সল্ভ করাই হচ্ছে two pointer method .আমাদের বলা হল আমাদের কাছে দুইটা সর্টেট array আছে , আমাদের বলতে হবে এই দুইটা array থেকে একটা একটা ভ্যালু নিয়ে আমরা কতভাবে একটা নাম্বার M বানাতে পারি যাদের কোন মধ্যে কোন ডুপলিকেট ভ্যালু নেই ।
যদি আমরা একটু Naive Method দেখি -
এইখানে আমরা inner এবং outer for loop এর দুইটা relation এর মাধ্যমে খুব সহজে Ans বের করে দিতে পারি ।
আমরা এইখানে N পর্যন্ত দুইটা লুপ চাল্লাচ্ছি । তাই আমাদের টোটাল রানটাইম হয়ে যাচ্ছে O( N ^ 2 ) । আমরা যদি একটু Modification করি আমরা এইটা কমিয়ে O(N) এ নিয়ে আসতে পারি । আমরা দুইটা পয়েন্ট নেই ।
Say low and high । low পয়েন্ট করতেছে আমাদের A array এরটার starting point কে এবং high পয়েন্ট করতেছে আমাদের B array এর ending পজিশনটাকে ।
Observation number one ::
আমরা যদি দেখি A[low] + B[high] > M তাহলে আমরা একটা জিনিস সিউর ভাবে বলতে পারব । আমাদের অবশ্যই B এর ভ্যালু কমাতে হবে । কারণ যেহেতু A[low] হচ্ছে A এর সবথেকে ছোট ভ্যালু সুতরাং তাকে আর কমিয়ে কখনই B[high] এর সাথে add করে M বানানো যাবে না ।
Observation number two :::
আমরা যদি দেখি A[low] + B[high] < M তাহলে আমাদের অবশ্যই low এর ভ্যালু বাড়াতে হবে । কারণ high হচ্ছে B এর সবথেকে বড় ভ্যালু এর থেকে বড় ভ্যালু নাই । high থেকে আমরা কোন ভ্যালু বাড়াতে পারছি না । তাই অবশ্যই আমাদের এখন low থেকে বাড়াতে হবে ।
এইখানে একটা খটকা লাগতে পারে Observation one এ যেহেতু A[] array তে left to right যাওয়া হচ্ছে current low ভ্যালু মানে low যাকে right now point করছে A[] array তে তার থেকেও তো কম ভ্যালু আমার array তে থাকতে পারে । আমরা নিচের কোডটা একটু ভাল মত খেয়াল করলেই দেখতে পাব যে যদি থেকে থাকে এবং তার সাথে যদি high B[] array এর এড যদি M এর সমান হয় তাহলে তা আগেই Ans এর সাথে এড হয়ে আসবে । একদমই একই কাজ হচ্ছে B[] array তেও । এইখানে আমরা condition দিয়ে দুইটা পয়েন্টকে নিয়ন্ত্রণ করছি ।
এখন আমরা আরেকটা প্রবলেম এর মাধ্যমে two pointer এর মাধ্যমে কিভাবে প্রবলেম সল্ভ করা হয় এইটা দেখব ।
problem এইখানে আমাকে N টা নাম্বার দেওয়া থাকবে এবং একটা ভ্যালু দেওয়া থাকবে say S । আমাকে minimum length এর consecutive sub sequence বের করতে হয়ে যাতে এই consecutive sub sequence এর sum, S এর থেকে বড় বা সমান হয় ।
এই প্রবলেম অনেক এপ্ররোচে আমাদের করা যাবে মনে হইতে পারে । কিন্ত o(n) runtime আনা ব্যাতিত্ব এই প্রবলেম সল্ভ হবে না । o(n) runtime আমরা two pointer ট্যাকনিক এর মাধ্যমে আনতে পারি ।
একই ভাবে আগের প্রবলেম এর মত এইখানে আমরা দুইটা পয়েন্ট নিব । low , high । প্রাথমিক ভাবে দুইটা পয়েন্ট এই given number array এর starting point indicate করে । যতক্ষণ পর্যন্ত না low থেকে high এর sum , M এর ভ্যালু ক্রস না করে আমরা high এর ভ্যালু বাড়াইয়া যাব । যখনই ক্রস করবে বা সমান হবে তখনই আমরা current length check করব ( high - low + 1 ) যদি minimum ans update করা যায় তাহলে update করব । যখনই sum এর ভ্যালু M এর থেকে বড় হয়ে যাবে তখন আমরা low এর ভ্যালু বাড়ানো সাথে সাথে sum এর ভ্যালু ও adjust করতে থাকব ।
কোডটা দেখলে ব্যাপারটা ক্লিয়ার হয়ে যাবে
এখন যদি আমরা এই কোডটার রান টাইম দেখি । কোডটা high = 0 থেকে high < len পর্যন্ত চলছে । মানে O(n) এ ।
two pointer এর আরো একটা problem হচ্ছে এইটা । এইখানে আমাদের given array দেওয়া হ্য়নি । আমাদের given formula দিয়ে input ready করে নিতে হবে । এইটা বাদে almost same প্রবলেম হিসাবে মিলে যাচ্ছে আগের প্রবলেমটার সাথে ।
two pointer এর আরো প্রবলেম আইডি এইখানে কমেন্ট জানালে আমি এড করে দিতে পারব । বা কোন ট্যাকনিক কমেন্ট এ দিলে সবাই জানতে পারবে ।
Happy coding :)
Practice Problem :: 1 , 2 .
প্রথম কোডে if( A[i] + B[j]==M ) ans++; হওয়ার কথা না?
ReplyDeleteহুম , ধন্যবাদ :)
Deleteভাইয়া,
ReplyDeleteযদি, N = 6, M = 6,
A = [1, 2, 3, 4, 5, 6] and
B = [1, 2, 3, 5, 5, 6] হয় তাহলে কি two pointer ঠিকঠাক কাজ করবে?
আপনি অ্যালগরিদমের(কোডের) ১৪ তম লাইনে low++ করে দিয়েছেন। অর্থাৎ A[0]( = 1) এর জন্য শুধু B[4] ব্যবহার হবে এবং low = 1 হয়ে যাবে কিন্তু A[0] এর জন্য A[0] + A[3] == 6(M) হয় যেকারনে কোড সঠিক ভাবে কাজ করার কথা না !!!
ভাইয়া আমার বুঝতে ভূল হতে পারে। কাইন্ডলি জানাবেন। :)
আমার মনে হয় আপনি প্রবলেমটা একটু বুঝতে ভুল করেছেন । এইখানে আমাদের দুইটা array থেকে অবশ্যই একটা একটা value নিয়ে চেক করতে হবে । কোন একটা array থেকে না দুইটা array থেকেই ।
Deleteস্যরি ভাইয়া আমি টাইপ করতে ভূল করেছি, আমি বলতে চেয়েছিঃ
Delete"....হবে এবং low = 1 হয়ে যাবে কিন্তু A[0] এর জন্য A[0] + B[3] == 6(M) হয় যেকারনে কোড সঠিক ভাবে কাজ করার কথা না !!!...."
"আমাদের বলা হল আমাদের কাছে দুইটা সর্টেট array আছে , আমাদের বলতে হবে এই দুইটা array থেকে একটা একটা ভ্যালু নিয়ে আমরা কতভাবে একটা নাম্বার M বানাতে পারি যাদের কোন মধ্যে কোন ডুপলিকেট ভ্যালু নেই ।" লাস্ট পয়েন্ট টা হয়তো মিস করে গেছেন , যদি ডুপ্লিকেট থাকে তাহলে আমাদের while এর condition এ চেক করতে হবে এই যা :)
Deleteধন্যবাদ !!!
Deleteoshadharon vaia . Thanks basic idea pelam lekhata pore .
ReplyDeleteভাইয়া, দ্বিতীয় কোডটাতে while(high<=n) এবং high-low+1 এর পরিবর্তে high-low হবে। অন্যথায়
ReplyDelete5 11
1 2 3 4 5
এর জন্য কাজ করবে না মনে হচ্ছে।
আমি এই প্রব্লেম টা O(n^2) লুপ চালিয়ে করছি । আমার মতেও এইটা টাইম লিমিট খাওয়ার কথা । কিন্তু Ac হয়ে গেছে । আমার কোডের লিঙ্ক https://gist.github.com/Prime38/692115ac2f8dd20718a72e3b93202d41 ।চাইলে দেখতে পারেন ।
ReplyDeleteTwo Pointer Technique কি শুধু সর্টেট ডাটা দেওয়া থাকলে এপ্লাই করা হয়??? নাকি যে কোন array হলেই এপ্লাই করা হয়?
ReplyDeleteযে কোন array এর মধ্যে এপ্লাই করা যায় ।
ReplyDeleteThanks Vaiya.
ReplyDeleteMany Many Thanks.
ReplyDeleteভাল লাগল ভাই।
ReplyDeleteIn the second code there should be a condition that if (sum >= S && low == hi) then ans = 1 and break the while loop.
ReplyDeleteI can't see any need of this condition.Can you please provide a test case for which author's code give wrong output?
Delete5 2
Delete2 2 2 2 2
or
4 1
1 1 1 1
kono akta problem two pointer use kore solve kora lagbe eita amra kivabe bujbo vai?
ReplyDeleteবেসিকটা ক্লিয়ার করার জন্যে ধন্যবাদ
ReplyDelete