DSA Patterns Made Simple · Arrays and Strings: The Six Core Patterns
Two Pointers
Walk inward from both ends, or move a slow and a fast index through the same array. Perfect for sorted arrays, palindromes and in-place clean-ups, with O(1) extra space.
The problem
Valid Palindrome: does "A man, a plan, a canal: Panama" read the same forwards and backwards, ignoring case and punctuation?
You could build a cleaned, reversed copy and compare. But a person checks a palindrome by looking at the first and last letters, then moving inward. Two fingers, no copy.
How to spot it
- The input is sorted, or sorting it doesn't break the problem
- "Pair / triplet that sums to…" in a sorted array
- Palindromes, reversing in place
- "Remove duplicates / move zeros in place"
- Comparing from both ends (container with most water)
The idea
Keep two indexes and move them according to a rule, never going backwards. Two common shapes:
- Opposite ends:
leftstarts at 0,rightat the end. Compare, then move one or both inward. In a sorted array, if the sum is too small, moveleftup (bigger numbers); if too big, moverightdown. - Same direction (slow/fast):
fastscans every item;slowmarks where the next "kept" item goes. Used to clean an array in place.
Each pointer moves at most n times, so it's O(n) with O(1) extra space.
The template
left, right = 0, len(arr) - 1
while left < right:
if condition_met(arr[left], arr[right]):
return answer
if need_bigger:
left += 1
else:
right -= 1
let left = 0, right = arr.length - 1;
while (left < right) {
if (conditionMet(arr[left], arr[right])) return answer;
if (needBigger) left++;
else right--;
}
Worked example
Opposite-ends pointers for a palindrome and for a pair sum in a sorted array, and same-direction pointers to move zeros to the end.
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
if not s[left].isalnum():
left += 1
elif not s[right].isalnum():
right -= 1
elif s[left].lower() != s[right].lower():
return False
else:
left += 1
right -= 1
return True
def pair_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
total = nums[left] + nums[right]
if total == target:
return [left, right]
if total < target:
left += 1 # need a bigger sum
else:
right -= 1 # need a smaller sum
return []
def move_zeros(nums):
slow = 0 # where the next non-zero goes
for fast in range(len(nums)):
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
return nums
print("palindrome?", is_palindrome("A man, a plan, a canal: Panama"))
print("palindrome?", is_palindrome("race a car"))
print("pair summing to 10:", pair_sum_sorted([1, 3, 4, 6, 8, 11], 10))
print("zeros moved:", move_zeros([0, 1, 0, 3, 12]))
Output
palindrome? True palindrome? False pair summing to 10: [2, 3] zeros moved: [1, 3, 12, 0, 0]
const isAlnum = (c) => /[a-z0-9]/i.test(c);
function isPalindrome(s) {
let left = 0, right = s.length - 1;
while (left < right) {
if (!isAlnum(s[left])) left++;
else if (!isAlnum(s[right])) right--;
else if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
else { left++; right--; }
}
return true;
}
function pairSumSorted(nums, target) {
let left = 0, right = nums.length - 1;
while (left < right) {
const total = nums[left] + nums[right];
if (total === target) return [left, right];
if (total < target) left++; // need a bigger sum
else right--; // need a smaller sum
}
return [];
}
function moveZeros(nums) {
let slow = 0; // where the next non-zero goes
for (let fast = 0; fast < nums.length; fast++) {
if (nums[fast] !== 0) {
[nums[slow], nums[fast]] = [nums[fast], nums[slow]];
slow++;
}
}
return nums;
}
const show = (v) => typeof v === "boolean" ? (v ? "True" : "False") : JSON.stringify(v).replaceAll(",", ", ");
console.log("palindrome?", show(isPalindrome("A man, a plan, a canal: Panama")));
console.log("palindrome?", show(isPalindrome("race a car")));
console.log("pair summing to 10:", show(pairSumSorted([1, 3, 4, 6, 8, 11], 10)));
console.log("zeros moved:", show(moveZeros([0, 1, 0, 3, 12])));
Output
palindrome? True palindrome? False pair summing to 10: [2, 3] zeros moved: [1, 3, 12, 0, 0]
Why does moving left up work for the sorted pair sum? If nums[left] + nums[right] is too small, then nums[left] plus any number to the left of right is even smaller, so nums[left] can never be part of the answer. Each move safely rules out one number.
Common mistakes
- Using two pointers on unsorted data for pair sums. Either sort first (O(n log n), and you lose original positions) or use the hash map pattern.
left <= rightvsleft < right. For pairs you need two different items, so stop when they meet.- Forgetting to skip duplicates in 3Sum, which produces repeated triplets.
- Infinite loops: every branch of the loop must move at least one pointer.
Practice
- Valid Palindrome (easy)
- Container With Most Water (medium): always move the shorter wall inward.
- 3Sum (medium): sort, fix one number, then run the pair-sum pointers on the rest.
Key points
- Opposite ends for sorted pairs and palindromes; slow/fast for in-place clean-ups.
- Each step rules something out for good, so the total is O(n) time, O(1) space.
- Sorted input is the strongest hint.
- Make sure every loop branch moves a pointer.
Practice questions
Why does the two-pointer pair sum need a sorted array?
Answer
The rule 'sum too small → move left up, too big → move right down' relies on order: moving left up is guaranteed to increase the sum and moving right down to decrease it. Without sorting, a move tells you nothing.
How does 3Sum use two pointers?
Answer
Sort the array, then for each index i run the two-pointer pair search on the part after i for target −nums[i]. Skip equal values of i and of the pointers to avoid duplicate triplets. Total O(n²).
Open in the app to mark lessons complete, take notes and track your progress.