Two Pointers

Overview

The two pointers technique uses two indices to traverse a string (or array) simultaneously, often reducing time complexity from O(n²) to O(n). Unlike sliding window where pointers maintain a contiguous segment, two pointers can move independently or from opposite ends, making it versatile for different problem types.

The most common pattern is palindrome checking: one pointer starts at the beginning, another at the end, and they move toward each other while comparing characters. This elegant approach eliminates the need for string reversal or extra space.

!Two pointers on a palindrome

Common Patterns

Pattern 1: Two Pointers from Opposite Ends

Start with left = 0 and right = s.length - 1. Move them toward each other while checking a condition.

Example: Valid Palindrome

function isPalindrome(s: string): boolean {
let left = 0;
let right = s.length - 1;

while (left < right) {
// Skip non-alphanumeric characters
while (left < right && !/[a-zA-Z0-9]/.test(s[left])) {
left++;
}
while (left < right && !/[a-zA-Z0-9]/.test(s[right])) {
right--;
}

// Compare characters (case-insensitive)
if (s[left].toLowerCase() !== s[right].toLowerCase()) {
return false;
}

left++;
right--;
}

return true;
}

Time: O(n), Space: O(1)

Pattern 2: Two Pointers Moving in Same Direction

Both pointers start at the beginning (or end) and move forward together, but at different speeds or conditions.

Example: Remove Duplicates from Sorted Array

function removeDuplicates(nums: number[]): number {
if (nums.length === 0) return 0;

let write = 0; // Position to write next unique element

for (let read = 1; read < nums.length; read++) {
if (nums[read] !== nums[write]) {
write++;
nums[write] = nums[read];
}
}

return write + 1; // Length of unique elements
}

Time: O(n), Space: O(1)

Pattern 3: Expand Around Center (Palindrome Substrings)

For each position (or pair), expand outward while characters match. Used to find palindromic substrings.

Example: Longest Palindromic Substring

function longestPalindrome(s: string): string {
let start = 0;
let maxLen = 0;

function expandAroundCenter(left: number, right: number) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
const len = right - left - 1;
if (len > maxLen) {
maxLen = len;
start = left + 1;
}
}

for (let i = 0; i < s.length; i++) {
expandAroundCenter(i, i); // Odd length palindromes
expandAroundCenter(i, i + 1); // Even length palindromes
}

return s.substring(start, start + maxLen);
}

Time: O(n²), Space: O(1)

When to Use Two Pointers

Use two pointers when you see these signals:

• "Palindrome" — Check if string reads the same forward and backward
• "Compare from both ends" — Need to check or process from start and end simultaneously
• "Remove duplicates" — In-place removal while maintaining order
• "Pair sum" — Finding pairs that sum to a target (on sorted data)
• "Reverse string" — Swap characters from both ends
• "Valid parentheses" — Matching opening and closing brackets

Key distinction: If the problem asks for a contiguous substring with a condition, use sliding window. If you need to compare or process from both ends, use two pointers.

Template (Opposite Ends)

function twoPointersTemplate(s: string): boolean {
let left = 0;
let right = s.length - 1;

while (left < right) {
// Skip irrelevant characters if needed
while (left < right && /* skip condition */) {
left++;
}
while (left < right && /* skip condition */) {
right--;
}

// Check condition
if (/* comparison fails */) {
return false;
}

left++;
right--;
}

return true;
}

Common Variations

Variation 1: Backspace String Compare

Simulate typing with backspaces by processing from the end:

function backspaceCompare(s: string, t: string): boolean {
let i = s.length - 1;
let j = t.length - 1;

while (i >= 0 || j >= 0) {
// Process backspaces in s
let skipS = 0;
while (i >= 0 && (s[i] === '#' || skipS > 0)) {
if (s[i] === '#') skipS++;
else skipS--;
i--;
}

// Process backspaces in t
let skipT = 0;
while (j >= 0 && (t[j] === '#' || skipT > 0)) {
if (t[j] === '#') skipT++;
else skipT--;
j--;
}

// Compare characters
if (i >= 0 && j >= 0 && s[i] !== t[j]) {
return false;
}
if ((i >= 0) !== (j >= 0)) {
return false;
}

i--;
j--;
}

return true;
}

Variation 2: Valid Parentheses

Use a stack, but two pointers can work for simple cases:

function isValid(s: string): boolean {
const stack: string[] = [];
const pairs: Record = {
')': '(',
'}': '{',
']': '['
};

for (const char of s) {
if (pairs[char]) {
// Closing bracket
if (stack.length === 0 || stack.pop() !== pairs[char]) {
return false;
}
} else {
// Opening bracket
stack.push(char);
}
}

return stack.length === 0;
}

Time and Space Complexity

• Time: O(n) for most two-pointer problems — each element is visited at most once
• Space: O(1) — only using a few variables, no extra data structures

Practice Tips

1. Identify the pattern — Opposite ends or same direction?
2. Handle edge cases — Empty string, single character, all same characters
3. Skip irrelevant characters — Non-alphanumeric, spaces, etc.
4. Normalize early — Convert to lowercase if case-insensitive comparison is needed
5. Watch for off-by-one errors — Be careful with left < right vs left <= right

The markdown you provided is actually mostly correct! The issue might be that the table header and separator rows need to be on separate lines, which they are. However, let me give you a cleaner, more robust version:

Two Pointers vs Sliding Window

💡 Remember: If you need a contiguous substring satisfying a condition, think sliding window. If you need to compare or process from both ends, think two pointers.

Related Concepts

• Sliding Window — Similar technique but maintains a contiguous window
• Array Two Pointers — Same pattern applies to sorted arrays (two sum, etc.)
• String Manipulation — Often combined with string operations

Mastering two pointers will help you efficiently solve palindrome, comparison, and in-place manipulation problems in coding interviews.