DSA · Lesson 3 of 20 · 3 min
Arrays and Strings: Core Techniques
This is how you turn an O(n²) brute-force solution into the O(n) answer they're looking for.
The Two-Pointer Pattern
The goal of the two-pointer pattern is to process a sequence from two ends at once to avoid a nested loop. Instead of comparing every element with every other element (O(n²)), you use two indices to explore the array in a single pass (O(n)).
There are two main variations. The first uses pointers that start at opposite ends and move toward each other. The second uses two pointers that start at the beginning but move at different speeds, often called the "fast and slow pointer" pattern.
This lesson focuses on the first: converging pointers. It's a simple, powerful technique for a specific set of problems.
How to Find a Target Sum in a Sorted Array
A classic interview question is: given a sorted array, find two numbers that add up to a target. A naive approach uses a nested loop, checking every pair. That's O(n²), and you'll be asked to do better.
The two-pointer approach is O(n). Start with one pointer (left) at the beginning and another (right) at the end.
At each step, calculate the sum. If it equals the target, you're done. If the sum is too small, you need a larger number, so you increment left. If it's too large, you need a smaller number, so you decrement right. The loop continues as long as left < right.
function findPairWithSum(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
const currentSum = arr[left] + arr[right];
if (currentSum === target) {
// Found the pair
return [arr[left], arr[right]];
} else if (currentSum < target) {
// Sum is too small, need a larger number.
left++;
} else {
// Sum is too large, need a smaller number.
right--;
}
}
// No pair found
return null;
}
The trap: This logic only works because the array is sorted. If arr were unsorted, incrementing left wouldn't guarantee a larger value, and the directed search would fail. For unsorted arrays, you'll typically use a hash map.
The time complexity is O(n) because in the worst case, each pointer travels towards the other, making a single pass through the array. The space complexity is O(1) because you only use a few variables to store the pointers and sum.
How to Spot a Two-Pointer Problem
You can't use this pattern everywhere, but it's a perfect fit for a specific class of problems.
Look for questions involving a sorted array (or a string) where you need to find a pair, check for a palindrome, or perform an in-place reversal. Keywords to watch for: "sorted array," "pair with sum," "palindrome," "reverse in-place," "remove duplicates from sorted array."
In an interview, state the O(n²) brute-force solution first. Say, "I could use a nested loop, but that would be O(n²). Since the array is sorted, we can optimize this to O(n) with a two-pointer approach." This shows you identify performance trade-offs and aren't just reciting a memorized algorithm.
Be mindful of the loop condition. while (left < right) is standard for finding pairs. Using left <= right might cause an infinite loop or incorrect logic if the pointers stop on the same element and the conditions aren't met to move them.
Visualizing the Pointer Logic
This flowchart shows the decision-making process inside the while loop for the target sum problem. The pointers left and right are adjusted based on how the currentSum compares to the target.
Try it
Implement a function isPalindrome(s: string) that returns true if a string is a palindrome, ignoring non-alphanumeric characters and case. Use two pointers starting from the ends and moving inwards. For a guided challenge, try solving Valid Palindrome or Two Sum II - Input Array Is Sorted.
Next: We'll cover Objects and Hash Maps in JavaScript, which unlock efficient solutions for when your input isn't sorted.
Lock it in — apply this lesson under interview conditions.