May 28, 2026

Two Pointers

Overview

Two-pointer algorithms coordinate two indices so a single pass replaces a nested search. The pointers may move toward each other from opposite ends, advance at different speeds, or partition an array into regions. The technique is especially useful for sorted arrays, palindrome checks, pair searches, and in-place rearrangement.

The key is proving which candidates can be discarded after each comparison. When the input is sorted, a comparison often tells you exactly which pointer must move. The two-pointer scan usually runs in O(n). If the input must be sorted first, sorting costs O(n log n), making the overall time complexity O(n log n).

Templates

Set left = 0 and right = n - 1.
While left < right, evaluate the pair (values[left], values[right]).
If the pair is the answer, record or return it.
If the current value is too small, increment left.
If it is too large, decrement right.
Ensure every branch moves at least one pointer.

public class TwoPointersTemplate {
	public static boolean hasPairWithSum(int[] sorted, int target) {
		int left = 0;
		int right = sorted.length - 1;

		while (left < right) {
			long sum = (long) sorted[left] + sorted[right];

			if (sum == target) {
				return true;
			}
			if (sum < target) {
				left++;
			} else {
				right--;
			}
		}

		return false;
	}
}

def has_pair_with_sum(sorted_values: list[int], target: int) -> bool:
	left = 0
	right = len(sorted_values) - 1

	while left < right:
		total = sorted_values[left] + sorted_values[right]

		if total == target:
			return True
		if total < target:
			left += 1
		else:
			right -= 1

	return False

Problems

125. Valid Palindrome

Ignore punctuation and letter case, then decide whether a string reads the same in both directions. Move inward from both ends, skipping non-alphanumeric characters before comparing the next pair. The solution runs in O(n) time and uses O(1) extra space.

class Solution {
	public boolean isPalindrome(String s) {
		int left = 0;
		int right = s.length() - 1;

		while (left < right) {
			while (left < right &&
				!Character.isLetterOrDigit(s.charAt(left))) {
				left++;
			}
			while (left < right &&
				!Character.isLetterOrDigit(s.charAt(right))) {
				right--;
			}

			if (Character.toLowerCase(s.charAt(left)) !=
				Character.toLowerCase(s.charAt(right))) {
				return false;
			}

			left++;
			right--;
		}

		return true;
	}
}

class Solution:
	def isPalindrome(self, s: str) -> bool:
		left = 0
		right = len(s) - 1

		while left < right:
			while left < right and not s[left].isalnum():
				left += 1
			while left < right and not s[right].isalnum():
				right -= 1

			if s[left].lower() != s[right].lower():
				return False

			left += 1
			right -= 1

		return True

11. Container With Most Water

Choose two heights that hold the most water. The area is limited by the shorter side, so after measuring a pair, moving the taller side cannot improve that limiting height. Move the shorter side inward and keep the best area found.

class Solution {
	public int maxArea(int[] height) {
		int left = 0;
		int right = height.length - 1;
		int best = 0;

		while (left < right) {
			int width = right - left;
			int level = Math.min(height[left], height[right]);
			best = Math.max(best, width * level);

			if (height[left] <= height[right]) {
				left++;
			} else {
				right--;
			}
		}

		return best;
	}
}

from typing import List

class Solution:
	def maxArea(self, height: List[int]) -> int:
		left = 0
		right = len(height) - 1
		best = 0

		while left < right:
			width = right - left
			level = min(height[left], height[right])
			best = max(best, width * level)

			if height[left] <= height[right]:
				left += 1
			else:
				right -= 1

		return best

15. 3Sum

Return every unique triplet whose sum is zero. Sort the array, fix one value, and solve the remaining two-sum problem with inward-moving pointers. Skip equal values at all three positions to prevent duplicate triplets. Sorting dominates the space behavior, and the runtime is O(n²).

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
	public List<List<Integer>> threeSum(int[] nums) {
		int N = nums.length;
		Arrays.sort(nums);
		List<List<Integer>> res = new ArrayList<>();

		for (int k = 0; k < N - 2; k++) {
			if (k > 0 && nums[k] == nums[k - 1]) {
				continue;
			}

			int i = k + 1;
			int j = N - 1;

			while (i < j) {
				int sum = nums[k] + nums[i] + nums[j];

				if (sum == 0) {
					res.add(List.of(
						nums[k],
						nums[i],
						nums[j]
					));
					i++;
					j--;

					while (i < j && nums[i] == nums[i - 1]) {
						i++;
					}
					while (i < j && nums[j] == nums[j + 1]) {
						j--;
					}
				} else if (sum < 0) {
					i++;
				} else {
					j--;
				}
			}
		}

		return res;
	}
}

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        N = len(nums)
        nums.sort()
        res = []

        for k in range(N-2):
            if k > 0 and nums[k] == nums[k-1]:
                continue

            i, j = k+1, N-1
            target = -nums[k]
            while i < j:
                if nums[i] + nums[j] < target:
                    i += 1
                elif nums[i] + nums[j] > target:
                    j -= 1
                else:
                    res.append([nums[i], nums[j], nums[k]])
                    while i < j and nums[i] == nums[i+1]:
                        i += 1
                    while i < j and nums[j] == nums[j-1]:
                        j -= 1
                    i += 1
                    j -= 1

        return res

42. Trapping Rain Water

Water above a position is limited by the smaller maximum wall on its left and right. Move the pointer with the smaller current wall, because that side already has a known limiting boundary, and accumulate the difference between its running maximum and current height.

class Solution {
	public int trap(int[] height) {
		int left = 0;
		int right = height.length - 1;
		int leftMax = 0;
		int rightMax = 0;
		int res = 0;

		while (left < right) {
			if (height[left] <= height[right]) {
				leftMax = Math.max(leftMax, height[left]);
				res += leftMax - height[left];
				left++;
			} else {
				rightMax = Math.max(rightMax, height[right]);
				res += rightMax - height[right];
				right--;
			}
		}

		return res;
	}
}

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        left_max, right_max = 0, 0
        left, right = 0, len(height) - 1
        res = 0

        while left < right:
            if height[left] < height[right]:
                left_max = max(left_max, height[left])
                res += left_max - height[left]
                left += 1
            else:
                right_max = max(right_max, height[right])
                res += right_max - height[right]
                right -= 1

        return res

75. Sort Colors

Sort values 0, 1, and 2 in place. The Dutch national flag algorithm maintains a completed zero region, an unexplored region, and a completed two region. Swapping a two does not advance the scanning pointer because the incoming value has not been classified yet.

class Solution {
	public void sortColors(int[] nums) {
		int left = 0;
		int mid = 0;
		int right = nums.length - 1;

		while (mid <= right) {
			if (nums[mid] == 0) {
				swap(nums, left, mid);
				left++;
				mid++;
			} else if (nums[mid] == 2) {
				swap(nums, mid, right);
				right--;
			} else {
				mid++;
			}
		}
	}

	private void swap(int[] nums, int first, int second) {
		int temporary = nums[first];
		nums[first] = nums[second];
		nums[second] = temporary;
	}
}

from typing import List

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        # keep three pointers, left, mid, right
        # left: position of next 0 swap
        # right: position of next 2 swap
        # mid: current element
        left, mid, right = 0, 0, len(nums) - 1

        while mid <= right:
            if nums[mid] == 0:
                nums[mid], nums[left] = nums[left], nums[mid]
                left += 1
                mid += 1
            elif nums[mid] == 2:
                nums[mid], nums[right] = nums[right], nums[mid]
                right -= 1
                # Do NOT increment mid here
                # because the swapped-in value at mid is unknown
            else: # nums[mid] == 1
                mid += 1

611. Valid Triangle Number

Count index triplets whose side lengths can form a triangle. After sorting, fix the longest side at i, then use left and right over the smaller sides. If nums[left] + nums[right] > nums[i], every value from left through right - 1 also forms a valid triangle with those two larger sides, so add right - left at once. Sorting costs O(n log n), and the two-pointer scans take O(n²) overall.

import java.util.Arrays;

class Solution {
    public int triangleNumber(int[] nums) {
        int N = nums.length;
        int res = 0;
        Arrays.sort(nums);

        for (int i = N - 1; i >= 2; i--) {
            int left = 0;
            int right = i - 1;

            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    res += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }

        return res;
    }
}

from typing import List

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        N = len(nums)
        res = 0
        nums.sort()

        for i in range(N-1, 1, -1):
            left, right = 0, i-1
            while left < right:
                if nums[left] + nums[right] > nums[i]:
                    res += right - left
                    right -= 1
                else:
                    left += 1

        return res