Imagine you’re adjusting a rubber band on a number line. You can stretch it by moving the right end, or shrink it by moving the left end. The key insight: you never need to move backwards. This “monotonic” property is what makes two pointers O(n) instead of O(n²).
Use for: Sorted arrays, finding pairs with target sum, palindromes.
Copy
// Template: Two Sum in Sorted Arraypair<int, int> twoSumSorted(vector<int>& arr, int target) { int left = 0, right = arr.size() - 1; while (left < right) { int sum = arr[left] + arr[right]; if (sum == target) { return {left, right}; } else if (sum < target) { left++; // Need larger sum } else { right--; // Need smaller sum } } return {-1, -1}; // Not found}
Why It Works: The array is sorted. If current sum is too small, moving left pointer right increases it. If too large, moving right pointer left decreases it. We never miss the answer because we exhaustively check all “promising” pairs.
Use for: Removing duplicates, cycle detection, partitioning.
Copy
// Template: Remove Duplicates from Sorted Arrayint removeDuplicates(vector<int>& arr) { if (arr.empty()) return 0; int slow = 0; // Position to write next unique element for (int fast = 1; fast < arr.size(); fast++) { if (arr[fast] != arr[slow]) { slow++; arr[slow] = arr[fast]; } } return slow + 1; // Length of unique portion}
Use for: Subarray with sum/product condition, longest/shortest subarray.
Copy
// Template: Smallest Subarray with Sum >= Targetint minSubarrayLen(int target, vector<int>& nums) { int left = 0, sum = 0; int minLen = INT_MAX; for (int right = 0; right < nums.size(); right++) { sum += nums[right]; // Expand window while (sum >= target) { // Shrink while valid minLen = min(minLen, right - left + 1); sum -= nums[left]; left++; } } return minLen == INT_MAX ? 0 : minLen;}
Signal: “Find max/min/count in every window of size K”
Copy
// Maximum sum of subarray of size Kint maxSumSubarray(vector<int>& arr, int k) { int n = arr.size(); if (n < k) return -1; // Compute first window int windowSum = 0; for (int i = 0; i < k; i++) { windowSum += arr[i]; } int maxSum = windowSum; // Slide the window for (int i = k; i < n; i++) { windowSum += arr[i] - arr[i - k]; // Add new, remove old maxSum = max(maxSum, windowSum); } return maxSum;}
Signal: “Find longest/shortest subarray where condition holds”
Copy
// Longest substring with at most K distinct charactersint longestWithKDistinct(string& s, int k) { unordered_map<char, int> charCount; int left = 0, maxLen = 0; for (int right = 0; right < s.size(); right++) { charCount[s[right]]++; // Shrink window while invalid while (charCount.size() > k) { charCount[s[left]]--; if (charCount[s[left]] == 0) { charCount.erase(s[left]); } left++; } maxLen = max(maxLen, right - left + 1); } return maxLen;}
Problem: Find all triplets that sum to zero.Approach: Fix one element, use two pointers for the remaining two.
Copy
vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); i++) { // Skip duplicates for first element if (i > 0 && nums[i] == nums[i-1]) continue; int target = -nums[i]; int left = i + 1, right = nums.size() - 1; while (left < right) { int sum = nums[left] + nums[right]; if (sum == target) { result.push_back({nums[i], nums[left], nums[right]}); // Skip duplicates while (left < right && nums[left] == nums[left+1]) left++; while (left < right && nums[right] == nums[right-1]) right--; left++; right--; } else if (sum < target) { left++; } else { right--; } } } return result;}
Problem: Given heights, find two lines that form container with most water.Insight: Start from ends. The limiting factor is the shorter line. Moving the shorter line might find a taller one; moving the taller can’t help.
Copy
int maxArea(vector<int>& height) { int left = 0, right = height.size() - 1; int maxWater = 0; while (left < right) { int h = min(height[left], height[right]); int w = right - left; maxWater = max(maxWater, h * w); // Move the shorter line if (height[left] < height[right]) { left++; } else { right--; } } return maxWater;}
Is array sorted (or can be sorted)?├── Yes: Do you need pairs?│ ├── Yes → Two Pointers (converging)│ └── No: Subarray condition?│ ├── Yes → Sliding Window│ └── No → Consider other techniques└── No: Is sorting acceptable? ├── Yes → Sort first, then two pointers └── No: Can problem be reformulated? ├── Yes → Prefix sum + hashmap └── No → Likely different pattern
