The Two Pointer technique uses two indices that move through the data structure (usually from opposite ends or same direction) to solve problems efficiently, often reducing O(n²) to O(n).
// Pattern 1: Opposite ends (sorted array)
let left = 0, right = arr.length - 1;
while (left < right) {
// process arr[left] and arr[right]
// move left++ or right-- based on condition
}
// Pattern 2: Same direction (fast/slow)
let slow = 0;
for (let fast = 0; fast < arr.length; fast++) {
// process and advance slow conditionally
}
Common uses: pair sum, removing duplicates, partitioning, palindrome checking.
Use two pointers at opposite ends. If sum is too small, move left pointer right. If too large, move right pointer left.
function pairWithSum(arr, target) {
let left = 0, right = arr.length - 1;
while (left < right) {
const sum = arr[left] + arr[right];
if (sum === target) return [left, right];
if (sum < target) left++;
else right--;
}
return [-1, -1];
}
// pairWithSum([1, 3, 5, 7, 9], 10) => [0, 4] (1+9)
Time: O(n) | Space: O(1)
Use a slow pointer to track the position of unique elements and a fast pointer to scan through the array.
function removeDuplicates(arr) {
if (arr.length === 0) return 0;
let slow = 0;
for (let fast = 1; fast < arr.length; fast++) {
if (arr[fast] !== arr[slow]) {
slow++;
arr[slow] = arr[fast];
}
}
return slow + 1; // length of unique portion
}
// removeDuplicates([1,1,2,2,3,4,4]) => 4, arr=[1,2,3,4,...]
Time: O(n) | Space: O(1)
Find two lines that together with the x-axis form a container holding the most water. Use two pointers at the ends and move the shorter line inward.
function maxArea(heights) {
let left = 0, right = heights.length - 1, max = 0;
while (left < right) {
const area = Math.min(heights[left], heights[right]) * (right - left);
max = Math.max(max, area);
if (heights[left] < heights[right]) left++;
else right--;
}
return max;
}
// maxArea([1,8,6,2,5,4,8,3,7]) => 49
Time: O(n) | Space: O(1)
Find all unique triplets that sum to zero. Sort the array, fix one element, and use two pointers for the remaining pair.
function threeSum(nums) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i-1]) continue;
let lo = i + 1, hi = nums.length - 1;
while (lo < hi) {
const sum = nums[i] + nums[lo] + nums[hi];
if (sum === 0) {
result.push([nums[i], nums[lo], nums[hi]]);
while (nums[lo] === nums[lo+1]) lo++;
while (nums[hi] === nums[hi-1]) hi--;
lo++; hi--;
} else if (sum < 0) lo++;
else hi--;
}
}
return result;
}
Time: O(n²) | Space: O(1) excluding output
Calculate water trapped between bars. Use two pointers tracking the max height from each side. Water at each position = min(leftMax, rightMax) - height.
function trap(height) {
let left = 0, right = height.length - 1;
let leftMax = 0, rightMax = 0, water = 0;
while (left < right) {
if (height[left] < height[right]) {
leftMax = Math.max(leftMax, height[left]);
water += leftMax - height[left];
left++;
} else {
rightMax = Math.max(rightMax, height[right]);
water += rightMax - height[right];
right--;
}
}
return water;
}
// trap([0,1,0,2,1,0,1,3,2,1,2,1]) => 6
Time: O(n) | Space: O(1)
Use three pointers: low (boundary of 0s), mid (current), high (boundary of 2s). Process elements and swap into correct regions.
function sortColors(nums) {
let low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] === 0) {
[nums[low], nums[mid]] = [nums[mid], nums[low]];
low++; mid++;
} else if (nums[mid] === 1) {
mid++;
} else {
[nums[mid], nums[high]] = [nums[high], nums[mid]];
high--;
}
}
return nums;
}
// sortColors([2,0,2,1,1,0]) => [0,0,1,1,2,2]
Time: O(n) single pass | Space: O(1)
Given two sorted arrays where the first has enough space, merge from the end using two pointers to avoid shifting elements.
function merge(nums1, m, nums2, n) {
let i = m - 1, j = n - 1, k = m + n - 1;
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
else nums1[k--] = nums2[j--];
}
while (j >= 0) nums1[k--] = nums2[j--];
return nums1;
}
// nums1 = [1,3,5,0,0,0], m=3
// nums2 = [2,4,6], n=3
// merge => [1,2,3,4,5,6]
Time: O(m + n) | Space: O(1)
Use two pointers, one for each array. If elements match, add to result and advance both. Otherwise, advance the pointer with the smaller element.
function intersection(a, b) {
let i = 0, j = 0;
const result = [];
while (i < a.length && j < b.length) {
if (a[i] === b[j]) {
result.push(a[i]);
i++; j++;
} else if (a[i] < b[j]) {
i++;
} else {
j++;
}
}
return result;
}
// intersection([1,2,3,4], [2,4,6]) => [2, 4]
Time: O(m + n) | Space: O(min(m, n))
Use two pointers from opposite ends, skip non-alphanumeric characters, and compare in a case-insensitive manner.
function isPalindrome(s) {
let left = 0, right = s.length - 1;
while (left < right) {
while (left < right && !isAlphaNum(s[left])) left++;
while (left < right && !isAlphaNum(s[right])) right--;
if (s[left].toLowerCase() !== s[right].toLowerCase())
return false;
left++;
right--;
}
return true;
}
function isAlphaNum(c) {
return /[a-zA-Z0-9]/.test(c);
}
// isPalindrome("A man, a plan, a canal: Panama") => true
Time: O(n) | Space: O(1)
Sort the array. Fix one element, then use two pointers on the remainder. Skip duplicate values to avoid duplicate triplets.
function threeSum(nums) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i-1]) continue; // skip duplicate i
let l = i + 1, r = nums.length - 1;
while (l < r) {
const sum = nums[i] + nums[l] + nums[r];
if (sum === 0) {
result.push([nums[i], nums[l], nums[r]]);
while (l < r && nums[l] === nums[l+1]) l++;
while (l < r && nums[r] === nums[r-1]) r--;
l++; r--;
} else if (sum < 0) l++;
else r--;
}
}
return result;
}
// Input: [-1,0,1,2,-1,-4] => Output: [[-1,-1,2],[-1,0,1]]
// Input: [0,0,0] => Output: [[0,0,0]]
// Input: [] => Output: []
Time: O(n²) | Space: O(1) excluding output
Start with left at 0 and right at end. Move the pointer with the shorter height inward (since moving the taller one can only decrease or maintain area).
function maxArea(height) {
let left = 0, right = height.length - 1, maxWater = 0;
while (left < right) {
const h = Math.min(height[left], height[right]);
const w = right - left;
maxWater = Math.max(maxWater, h * w);
if (height[left] < height[right]) left++;
else right--;
}
return maxWater;
}
// Input: [1,8,6,2,5,4,8,3,7] => Output: 49 (bars at index 1 and 8)
// Input: [1,1] => Output: 1
// Input: [4,3,2,1,4] => Output: 16
Time: O(n) | Space: O(1)
Use slow/fast pointers to find the middle, split the list, recursively sort both halves, then merge. This is merge sort for linked lists.
function sortList(head) {
if (!head || !head.next) return head;
// Two pointers to find middle
let slow = head, fast = head.next;
while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
const mid = slow.next;
slow.next = null; // split
return merge(sortList(head), sortList(mid));
}
function merge(l1, l2) {
const dummy = {};
let curr = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
else { curr.next = l2; l2 = l2.next; }
curr = curr.next;
}
curr.next = l1 || l2;
return dummy.next;
}
// Input: 4->2->1->3 => Output: 1->2->3->4
// Input: -1->5->3->4->0 => Output: -1->0->3->4->5
Time: O(n log n) | Space: O(log n)
Use a slow pointer for the write position and a fast pointer for reading. When fast finds a new value, write it to slow's position and advance slow.
function removeDuplicates(nums) {
let slow = 0;
for (let fast = 1; fast < nums.length; fast++) {
if (nums[fast] !== nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1; // length of unique elements
}
// Input: [1,1,2] => Output: 2, nums=[1,2,_]
// Input: [0,0,1,1,1,2,3] => Output: 4, nums=[0,1,2,3,_,_,_]
Time: O(n) | Space: O(1)
Scan the array tracking the last index of each target element. When both have been seen at least once, update minimum distance.
function minDistance(arr, x, y) {
let lastX = -1, lastY = -1, minDist = Infinity;
for (let i = 0; i < arr.length; i++) {
if (arr[i] === x) {
lastX = i;
if (lastY !== -1) minDist = Math.min(minDist, Math.abs(lastX - lastY));
} else if (arr[i] === y) {
lastY = i;
if (lastX !== -1) minDist = Math.min(minDist, Math.abs(lastX - lastY));
}
}
return minDist;
}
// Input: [3,5,4,2,6,5,6,6,5,4,8,3], x=3, y=6 => Output: 4
// Input: [1,2,3,4,5,6,7], x=2, y=6 => Output: 4
Time: O(n) | Space: O(1)
Use the Lomuto or Hoare partition scheme. Lomuto uses one pointer from left; Hoare uses two pointers moving opposite directions — more efficient in practice.
// Hoare partition (more efficient, fewer swaps on average)
function hoarePartition(arr, lo, hi) {
const pivot = arr[Math.floor((lo + hi) / 2)];
let i = lo - 1, j = hi + 1;
while (true) {
do i++; while (arr[i] < pivot);
do j--; while (arr[j] > pivot);
if (i >= j) return j; // partition index
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
// Input: arr=[3,2,1,5,6,4], lo=0, hi=5
// After: elements ≤ pivot on left, > pivot on right
// Lomuto partition ensures pivot is exactly at position p:
// [lo..p-1] <= pivot, arr[p] = pivot, [p+1..hi] > pivot
Time: O(n) per call | Space: O(1)
Use two pointers to linearly check matching prefixes and suffixes. The remaining unmatched middle portions need operations. For more complex edits, see edit distance DP.
function minOpsToEqualize(s, t) {
// Count matching prefix
let l = 0;
while (l < s.length && l < t.length && s[l] === t[l]) l++;
// Count matching suffix
let r1 = s.length - 1, r2 = t.length - 1;
while (r1 >= l && r2 >= l && s[r1] === t[r2]) { r1--; r2--; }
// Remaining characters that need to change
const needChange = Math.max(r1 - l + 1, r2 - l + 1);
return needChange;
}
// Input: s="abc", t="adc" => Output: 1 (change 'b' to 'd')
// Input: s="abc", t="xy" => Output: 3
Time: O(n) | Space: O(1)
Count distinct characters in the string. Use two pointers to find the minimum window that contains all distinct chars. Shrink from left when all are covered, expand right otherwise.
function smallestWindowDistinctChars(s) {
const distinct = new Set(s).size;
const freq = new Map();
let have = 0, left = 0, minLen = Infinity, minStart = 0;
for (let right = 0; right < s.length; right++) {
freq.set(s[right], (freq.get(s[right]) || 0) + 1);
if (freq.get(s[right]) === 1) have++;
while (have === distinct) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minStart = left;
}
freq.set(s[left], freq.get(s[left]) - 1);
if (freq.get(s[left]) === 0) have--;
left++;
}
}
return minLen === Infinity ? '' : s.slice(minStart, minStart + minLen);
}
// Input: "aabcbcdbca" => Output: "dbca"
// Input: "aaab" => Output: "ab"
Time: O(n) | Space: O(k) distinct chars
Use slow/fast pointers. The slow pointer marks the next write position. The fast pointer scans; write elements that are not the target value.
function removeElement(nums, val) {
let slow = 0;
for (let fast = 0; fast < nums.length; fast++) {
if (nums[fast] !== val) {
nums[slow] = nums[fast];
slow++;
}
}
return slow; // new length
}
// Input: nums=[3,2,2,3], val=3 => Output: 2, nums=[2,2,_,_]
// Input: nums=[0,1,2,2,3,0,4,2], val=2 => Output: 5, nums=[0,1,3,0,4,_,_,_]
Time: O(n) | Space: O(1)
Sort the array. Use two pointers: if the difference equals target, record the pair; if smaller, advance left; if larger, advance right.
function pairsWithDiff(arr, target) {
arr.sort((a, b) => a - b);
const result = [];
let l = 0, r = 1;
while (r < arr.length) {
const diff = arr[r] - arr[l];
if (diff === target) {
result.push([arr[l], arr[r]]);
l++; r++;
} else if (diff < target) r++;
else l++;
if (l === r) r++;
}
return result;
}
// Input: arr=[5,20,3,2,50,80], target=78 => Output: [[2,80]]
// Input: arr=[1,8,30,40,100], target=60 => Output: [[40,100]]
Time: O(n log n) | Space: O(1)
Maintain current sum: either extend previous subarray or start fresh. Track maximum seen. O(n) single pass with O(1) space.
function maxSubArray(nums) {
let maxSum = nums[0], currSum = nums[0];
for (let i = 1; i < nums.length; i++) {
currSum = Math.max(nums[i], currSum + nums[i]);
maxSum = Math.max(maxSum, currSum);
}
return maxSum;
}
// Input: [-2,1,-3,4,-1,2,1,-5,4] => Output: 6 (subarray [4,-1,2,1])
// Input: [1] => Output: 1
// Input: [5,4,-1,7,8] => Output: 23
Time: O(n) | Space: O(1)
Use a fixed-size sliding window of length p. Compare frequency maps of the window and pattern. Slide by one, updating counts, and record matches.
function findAnagrams(s, p) {
const result = [];
const pFreq = new Array(26).fill(0);
const wFreq = new Array(26).fill(0);
const A = 'a'.charCodeAt(0);
for (const c of p) pFreq[c.charCodeAt(0) - A]++;
for (let i = 0; i < s.length; i++) {
wFreq[s[i].charCodeAt(0) - A]++;
if (i >= p.length) wFreq[s[i - p.length].charCodeAt(0) - A]--;
if (wFreq.join('') === pFreq.join('')) result.push(i - p.length + 1);
}
return result;
}
// Input: s="cbaebabacd", p="abc" => Output: [0,6]
// Input: s="abab", p="ab" => Output: [0,1,2]
Time: O(n × 26) ≈ O(n) | Space: O(1)
Two-pointer sliding window: expand right, count zeros; when count exceeds K, shrink from left until count ≤ K again. Track maximum window length.
function longestOnes(nums, k) {
let left = 0, zeros = 0, best = 0;
for (let right = 0; right < nums.length; right++) {
if (nums[right] === 0) zeros++;
while (zeros > k) {
if (nums[left] === 0) zeros--;
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
// Input: nums=[1,1,1,0,0,0,1,1,1,1,0], k=2 => Output: 6
// Input: nums=[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k=3 => Output: 10
Time: O(n) | Space: O(1)