Two pointers ও sliding window: উদাহরণসহ প্যাটার্ন

অনেক array ও string সমস্যা subarray, substring বা জোড়া নিয়ে। Brute-force সব সম্ভাবনা O(n²) বা খারাপ সময়ে দেখে। দুটি কৌশল প্রায়ই তা O(n)-এ নামায়: two pointers ও sliding window।

কৌশল ১: two pointers

Nested loop এড়াতে data-র মধ্য দিয়ে চলা দুটি index ব্যবহার করুন। দুটি প্রচলিত আকার আছে।

দুই প্রান্ত থেকে ভেতরে

Sorted array-তে বা প্রতিসাম্য যাচাইয়ে ভালো কাজ করে।

সমস্যা: sorted array-তে যোগফল target এমন দুটি সংখ্যা খুঁজুন।

function twoSumSorted(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;      // বড় যোগফল দরকার
    else right--;                  // ছোট যোগফল দরকার
  }
  return [];
}
// সময় O(n), space O(1)

Array sorted বলে প্রতিটি ধাপ নিরাপদে একটি প্রার্থী বাদ দেয়। তাই এটি কাজ করে।

সমস্যা: string কি palindrome (অ-অক্ষর উপেক্ষা করে)? দুই প্রান্ত থেকে ভেতরে সরে তুলনা করুন।

অন্যান্য ব্যবহার: সবচেয়ে বেশি পানির container, 3Sum (sort, একটি সংখ্যা স্থির, বাকিতে two pointers), in-place উল্টানো।

একই দিকে: slow ও fast

দুটি pointer ভিন্ন গতি বা ভূমিকায় সামনে এগোয়।

সমস্যা: sorted array থেকে in-place ডুপ্লিকেট সরান।

function removeDuplicates(nums) {
  if (nums.length === 0) return 0;
  let write = 1;
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[read - 1]) nums[write++] = nums[read];
  }
  return write;     // অনন্য অংশের দৈর্ঘ্য
}
// সময় O(n), space O(1)

Read pointer scan করে; write pointer চিহ্নিত করে পরের রাখা মান কোথায় যাবে। একই ধারণা শূন্য শেষে সরায় বা মান filter করে।

Linked list-এ fast ও slow: একটি pointer দ্বিগুণ দ্রুত চালালে মাঝখান পাওয়া যায় এবং cycle শনাক্ত হয় (Floyd-এর algorithm)।

কৌশল ২: sliding window

Window হলো array বা string-এর একটি ধারাবাহিক পরিসর। ডানে নতুন element যোগ করে ও বামের পুরোনোটি সরিয়ে একটি চলমান মান হালনাগাদ করে এটি সরান, সব নতুন করে হিসাব না করে।

নির্দিষ্ট আকারের window

সমস্যা: আকার k এর যেকোনো subarray-র সর্বোচ্চ যোগফল।

function maxSumK(nums, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];
  let best = sum;
  for (let i = k; i < nums.length; i++) {
    sum += nums[i] - nums[i - k];     // নতুনটি যোগ, পুরোনোটি বাদ
    best = Math.max(best, sum);
  }
  return best;
}
// সময় O(n), space O(1)

পরিবর্তনশীল আকারের window

Window ডানে বাড়ে, এবং নিয়ম ভাঙলেই বাম থেকে সংকুচিত হয়।

সমস্যা: পুনরাবৃত্তিহীন অক্ষরের দীর্ঘতম substring-এর দৈর্ঘ্য।

function longestUnique(s) {
  const lastSeen = new Map();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (lastSeen.has(ch) && lastSeen.get(ch) >= left) {
      left = lastSeen.get(ch) + 1;       // পুনরাবৃত্তি টপকে লাফ
    }
    lastSeen.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}
// সময় O(n), space O(min(n, বর্ণমালা))

পরিবর্তনশীল window-এর সাধারণ টেমপ্লেট:

left = 0
for right in range(n):
    window state-এ item[right] যোগ করুন
    while window অবৈধ:
        window state থেকে item[left] সরান
        left += 1
    window [left..right] দিয়ে উত্তর হালনাগাদ করুন

আরও সমস্যা: যোগফল অন্তত S এমন ক্ষুদ্রতম subarray (ধনাত্মক সংখ্যা), সর্বোচ্চ K ভিন্ন অক্ষরের দীর্ঘতম substring, ক্ষুদ্রতম window substring, string-এ permutation।

কখন কোনটি

সমস্যার ইঙ্গিত	সম্ভাব্য কৌশল
Sorted array, জোড়া বা তিনটি খোঁজা	দুই প্রান্ত থেকে two pointers
In-place বদল, সরানো বা ভাগ করা	Read/write pointer
Linked list-এর মাঝ বা cycle	Fast ও slow pointer
আকার বা শর্তসহ ধারাবাহিক subarray বা substring	Sliding window
সম্ভবত ঋণাত্মক সংখ্যাসহ subarray যোগফল	Prefix sum + hash map (window ব্যর্থ হতে পারে)

সংকোচনের নিয়মসহ sliding window একটি একমুখী (monotonic) শর্তের ওপর নির্ভর করে: element যোগ করলে window-এর অবস্থা এক দিকেই সরতে থাকে। ঋণাত্মক সংখ্যায় তা ভাঙতে পারে।

সাধারণ ভুল

• Window-এর প্রান্তে off-by-one ভুল। right অন্তর্ভুক্ত কি না ঠিক করুন এবং ছোট ক্ষেত্র হাতে test করুন।
• left সরানোর সময় window state হালনাগাদ ভুলে যাওয়া।
• Data ধারাবাহিক না হলেও window ব্যবহার (তখন hash map, DP বা sorting ভাবুন)।
• ফাঁকা ইনপুট, বা array-র চেয়ে বড় k না সামলানো।

অনুশীলনের সমস্যা

Valid Palindrome, Two Sum II (sorted), 3Sum, Container With Most Water, Remove Duplicates from Sorted Array, Best Time to Buy and Sell Stock, Longest Substring Without Repeating Characters, Minimum Window Substring।

মূল কথা: সমস্যা sorted data-র জোড়া বা ধারাবাহিক পরিসর নিয়ে হলে two pointers বা sliding window চেষ্টা করুন। দুটিরই লক্ষ্য প্রতিটি element ধ্রুবকবার দেখা, ফলে O(n)।

---

Interview প্রস্তুতি ও DSA সিরিজ, পর্ব ১ (মূল প্যাটার্ন): 3 নম্বর (মোট 5)। আগের লেখা: Array ও hash map: interview-এর অবশ্যজ্ঞাতব্য প্যাটার্ন.