1.1 Two Pointers

চিনবেন কীভাবে

sorted array/string, "pair with sum X", দুই প্রান্ত থেকে তুলনা, palindrome, in-place / O(1) space, remove duplicates, partition

Demo · approach · কোড — আগে নিজে চেষ্টা, আটকালে খুলুন

Demo: Trapping Rain Water — LC 42 (Hard — Amazon/Google/Meta High)

Statement (Demo): height নামের একটা integer array দেওয়া যেখানে প্রতিটা মান একটা উল্লম্ব বারের উচ্চতা। বারগুলোর মাঝে বৃষ্টির পানি কতটুকু আটকে থাকবে তার মোট পরিমাণ বের করুন। উদাহরণ: [0,1,0,2,1,0,1,3,2,1,2,1] → 6 | ⚡ n ≤ 2×10⁴, 0 ≤ height[i] ≤ 10⁵

Approach: প্রতিটা ঘরে পানি জমে min(leftMax, rightMax) - height[i]। দুই প্রান্ত থেকে pointer চালান — যেদিকের height ছোট সেদিকটা আগান, কারণ ছোট দিকের max-ই bottleneck, অন্য পাশে যত বড়ই থাকুক পানির উচ্চতা এই দিকেই আটকে।

function trap(height) {
  let l = 0,
    r = height.length - 1;
  let leftMax = 0,
    rightMax = 0,
    water = 0;
  while (l < r) {
    if (height[l] < height[r]) {
      leftMax = Math.max(leftMax, height[l]);
      water += leftMax - height[l];
      l++;
    } else {
      rightMax = Math.max(rightMax, height[r]);
      water += rightMax - height[r];
      r--;
    }
  }
  return water;
}

Complexity: Time O(n), Space O(1) (monotonic stack দিয়েও হয় — দেখুন 4.1)

প্রবলেম

3Sumplan · দিন ০০৫ LC 15
Statement: integer array nums দেওয়া — তিনটা আলাদা index-এর সংখ্যা খুঁজুন যাদের যোগফল 0। Duplicate triplet ছাড়া সব unique triplet return করুন।
উদাহরণ: [-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]] | ⚡ n ≤ 3000
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Container With Most Waterplan · দিন ০০৮ LC 11
Statement: nটা উল্লম্ব রেখা আছে, i-তম রেখার উচ্চতা height[i]। দুটো রেখা বেছে নিন যাতে তারা x-axis সহ সবচেয়ে বেশি পানি ধরতে পারে।
উদাহরণ: [1,8,6,2,5,4,8,3,7] → 49 | ⚡ n ≤ 10⁵
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Two Sum II (Sorted Array)plan · দিন ০০৪ LC 167
Statement: 1-indexed sorted array numbers দেওয়া — দুটো সংখ্যার index বের করুন যাদের যোগফল target। একই element দুবার ব্যবহার করা যাবে না, O(1) extra space।
উদাহরণ: numbers=[2,7,11,15], target=9 → [1,2] | ⚡ n ≤ 3×10⁴
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Valid Palindromeplan · দিন ০০৩ LC 125
Statement: string s দেওয়া — শুধু alphanumeric character রেখে lowercase-এ নামিয়ে palindrome কিনা বলুন।
উদাহরণ: "A man, a plan, a canal: Panama" → true | ⚡ len ≤ 2×10⁵
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Remove Duplicates from Sorted ArrayLC 26
Statement: sorted integer array nums দেওয়া — in-place unique element রাখুন (extra array নয়) এবং unique element-এর সংখ্যা k return করুন।
উদাহরণ: [1,1,2] → k=2, nums=[1,2,_] | ⚡ n ≤ 3×10⁴
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Sort ColorsLC 75
(তিন pointer / Dutch flag)
Statement: 0, 1, 2 সম্বলিত array nums দেওয়া — in-place sort করুন যাতে সব 0 আগে, তারপর 1, তারপর 2। Built-in sort ব্যবহার করা যাবে না।
উদাহরণ: [2,0,2,1,1,0] → [0,0,1,1,2,2] | ⚡ n ≤ 300
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Merge Sorted ArrayLC 88
(পেছন থেকে merge)
Statement: দুটো sorted array nums1 (size m+n) ও nums2 (size n) দেওয়া — nums1-এ in-place merge করুন।
উদাহরণ: nums1=[1,2,3,0,0,0], m=3, nums2=[2,5,6], n=3 → [1,2,2,3,5,6] | ⚡ m,n ≤ 200
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Reverse StringLC 344
Statement: character array s দেওয়া — in-place reverse করুন। O(1) extra memory ব্যবহার করতে হবে।
উদাহরণ: ['h','e','l','l','o'] → ['o','l','l','e','h'] | ⚡ n ≤ 10⁵
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন