Saturday, June 13, 2015

two pointer

বিশেষ করে 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 .

এখন আমরা আরেকটা প্রবলেম এর মাধ্যমে 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 .

20 comments:

  1. প্রথম কোডে if( A[i] + B[j]==M ) ans++; হওয়ার কথা না?

    ReplyDelete
  2. ভাইয়া,
    যদি, 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) হয় যেকারনে কোড সঠিক ভাবে কাজ করার কথা না !!!
    ভাইয়া আমার বুঝতে ভূল হতে পারে। কাইন্ডলি জানাবেন। :)

    ReplyDelete
    Replies
    1. আমার মনে হয় আপনি প্রবলেমটা একটু বুঝতে ভুল করেছেন । এইখানে আমাদের দুইটা array থেকে অবশ্যই একটা একটা value নিয়ে চেক করতে হবে । কোন একটা array থেকে না দুইটা array থেকেই ।

      Delete
    2. স্যরি ভাইয়া আমি টাইপ করতে ভূল করেছি, আমি বলতে চেয়েছিঃ
      "....হবে এবং low = 1 হয়ে যাবে কিন্তু A[0] এর জন্য A[0] + B[3] == 6(M) হয় যেকারনে কোড সঠিক ভাবে কাজ করার কথা না !!!...."

      Delete
    3. "আমাদের বলা হল আমাদের কাছে দুইটা সর্টেট array আছে , আমাদের বলতে হবে এই দুইটা array থেকে একটা একটা ভ্যালু নিয়ে আমরা কতভাবে একটা নাম্বার M বানাতে পারি যাদের কোন মধ্যে কোন ডুপলিকেট ভ্যালু নেই ।" লাস্ট পয়েন্ট টা হয়তো মিস করে গেছেন , যদি ডুপ্লিকেট থাকে তাহলে আমাদের while এর condition এ চেক করতে হবে এই যা :)

      Delete
  3. oshadharon vaia . Thanks basic idea pelam lekhata pore .

    ReplyDelete
  4. ভাইয়া, দ্বিতীয় কোডটাতে while(high<=n) এবং high-low+1 এর পরিবর্তে high-low হবে। অন্যথায়
    5 11
    1 2 3 4 5
    এর জন্য কাজ করবে না মনে হচ্ছে।

    ReplyDelete
  5. আমি এই প্রব্লেম টা O(n^2) লুপ চালিয়ে করছি । আমার মতেও এইটা টাইম লিমিট খাওয়ার কথা । কিন্তু Ac হয়ে গেছে । আমার কোডের লিঙ্ক https://gist.github.com/Prime38/692115ac2f8dd20718a72e3b93202d41 ।চাইলে দেখতে পারেন ।

    ReplyDelete
  6. Two Pointer Technique কি শুধু সর্টেট ডাটা দেওয়া থাকলে এপ্লাই করা হয়??? নাকি যে কোন array হলেই এপ্লাই করা হয়?

    ReplyDelete
  7. যে কোন array এর মধ্যে এপ্লাই করা যায় ।

    ReplyDelete
  8. ভাল লাগল ভাই।

    ReplyDelete
  9. In the second code there should be a condition that if (sum >= S && low == hi) then ans = 1 and break the while loop.

    ReplyDelete
    Replies
    1. I can't see any need of this condition.Can you please provide a test case for which author's code give wrong output?

      Delete
  10. kono akta problem two pointer use kore solve kora lagbe eita amra kivabe bujbo vai?

    ReplyDelete
  11. বেসিকটা ক্লিয়ার করার জন্যে ধন্যবাদ

    ReplyDelete