1.1 Two Pointers

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

sorted array/string, "pair with sum X", compare from both ends, palindrome, in-place / O(1) space, remove duplicates, partition

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

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

Statement (Demo): Given an integer array height where each value is the height of a vertical bar, compute how much rain water is trapped between the bars. Example: [0,1,0,2,1,0,1,3,2,1,2,1] → 6 | ⚡ n ≤ 2×10⁴, 0 ≤ height[i] ≤ 10⁵

Approach: The water above cell i is min(leftMax, rightMax) - height[i]. Run a pointer from each end and always advance the side with the smaller height — the smaller side's max is the bottleneck, no matter how tall the other side is.

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) (a monotonic stack also works — see 4.1)

Demo · Trapping Rain Waterplan · দিন ০৩৬ LC 42

নোট · ফাঁকা

My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে

প্রবলেম

3Sumplan · দিন ০০১🔥 Must-doLC 15
Statement: Given an integer array nums, find every unique triplet of distinct indices whose values sum to 0. No duplicate triplets.
Example: [-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]] | ⚡ n ≤ 3000
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Container With Most Waterplan · দিন ০১৮🔥 Must-doLC 11
Statement: There are n vertical lines; line i has height height[i]. Pick two lines that, together with the x-axis, hold the most water.
Example: [1,8,6,2,5,4,8,3,7] → 49 | ⚡ n ≤ 10⁵
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Two Sum II (Sorted Array)plan · দিন ০৩১ LC 167
Statement: Given a 1-indexed sorted array numbers, return the indices of the two numbers that add up to target. You may not use the same element twice; use O(1) extra space.
Example: numbers=[2,7,11,15], target=9 → [1,2] | ⚡ n ≤ 3×10⁴
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Valid Palindromeplan · দিন ০২৯🔥 Must-doLC 125
Statement: Given a string s, keep only alphanumeric characters, lowercase them, and decide whether the result is a palindrome.
Example: "A man, a plan, a canal: Panama" → true | ⚡ len ≤ 2×10⁵
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Remove Duplicates from Sorted ArrayLC 26
Statement: Given a sorted integer array nums, keep the unique elements in place (no extra array) and return their count k.
Example: [1,1,2] → k=2, nums=[1,2,_] | ⚡ n ≤ 3×10⁴
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Sort Colorsplan · দিন ০৩৭ LC 75
(three pointers / Dutch flag)
Statement: Given an array nums of 0s, 1s and 2s, sort it in place so all 0s come first, then 1s, then 2s. No built-in sort.
Example: [2,0,2,1,1,0] → [0,0,1,1,2,2] | ⚡ n ≤ 300
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Merge Sorted ArrayLC 88
(merge from the back)
Statement: Given two sorted arrays nums1 (size m+n) and nums2 (size n), merge them into nums1 in place.
Example: nums1=[1,2,3,0,0,0], m=3, nums2=[2,5,6], n=3 → [1,2,2,3,5,6] | ⚡ m,n ≤ 200
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Reverse StringLC 344
Statement: Given a character array s, reverse it in place with O(1) extra memory.
Example: ['h','e','l','l','o'] → ['o','l','l','e','h'] | ⚡ n ≤ 10⁵
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে