Using Two Pointers Pattern
1. Understanding Two Pointers Technique
The Two Pointers technique is a powerful algorithmic pattern used to solve problems efficiently by maintaining two pointers (indices) that traverse through data structures like arrays or linked lists.
| Pointer Type | Description | Use Cases |
|---|---|---|
| Left Pointer | Starts at the beginning of the array or list. | Used in sliding window, searching for pairs, etc. |
| Right Pointer | Starts at the end of the array or list. | Used in reverse traversal, finding pairs with specific sum, etc. |
Example: Finding a Pair with Target Sum
function twoSum(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
const currentSum = arr[left] + arr[right];
if (currentSum === target) {
return [left, right];
} else if (currentSum < target) {
left++;
} else {
right--;
}
}
return [];
}
// Example usage:
const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target)); // [0, 1]
Note: The array must be sorted for this approach to work correctly.
Key Advantages
- Efficient time complexity: O(n) for sorted arrays.
- Space complexity is O(1), making it memory-efficient.
- Simplifies problems involving pairs or subarrays.
2. Solving Pair Sum Problems
| Problem Type | Description | Solution Approach | Time Complexity |
|---|---|---|---|
| Two Sum | Find two numbers in a sorted array that sum to a target value. | Use two pointers: one at start, one at end. Move pointers based on sum comparison. | O(n) |
| Three Sum | Find three numbers in an array that sum to zero. | Sort the array. Fix one element and use two pointers for the remaining elements. | O(n^2) |
| Two Sum II (Sorted Array) | Given a sorted array, find two elements that sum to a target. | Use two pointers from both ends to efficiently search for the pair. | O(n) |
Example: Two Sum in Sorted Array
function twoSum(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const sum = nums[left] + nums[right];
if (sum === target) {
return [left, right];
} else if (sum < target) {
left++;
} else {
right--;
}
}
return [];
}Example: Three Sum
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 left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
Note: For the "Three Sum" problem, sorting the array first allows us to use two pointers efficiently. Duplicate handling ensures we don't return repeated triplets.
3. Removing Duplicates In-Place
| Property | Description | Usage |
|---|---|---|
| Two Pointers | Use two pointers to traverse the array from both ends | For in-place removal of duplicates |
| Slow Pointer | Points to the last unique element | Used to place next unique element |
| Fast Pointer | Traverses the array to find unique elements | Compares with slow pointer to detect duplicates |
Example: Remove Duplicates from Sorted Array
function removeDuplicates(nums) {
if (nums.length === 0) return 0;
let slow = 0;
for (let fast = 1; fast < nums.length; fast++) {
if (nums[fast] !== nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}
// Example usage:
const nums = [1, 1, 2, 2, 3];
const length = removeDuplicates(nums);
console.log(length); // Output: 3
console.log(nums.slice(0, length)); // Output: [1, 2, 3]
Note: The function modifies the array in-place and returns the new length. Elements beyond the returned length are not relevant.
4. Squaring Sorted Arrays
The "Squaring Sorted Arrays" problem involves taking a sorted array of integers and returning a new array with the squares of each number, also sorted in ascending order. This is a common application of the two pointers technique.
| Input | Output | Description |
|---|---|---|
| arr | [1, 4, 9, 16] |
Sorted array of integers |
Example: Squaring Sorted Arrays
const squaringSortedArray = (arr) => {
const result = new Array(arr.length);
let left = 0;
let right = arr.length - 1;
let index = arr.length - 1;
while (left <= right) {
const leftSquare = arr[left] * arr[left];
const rightSquare = arr[right] * arr[right];
if (leftSquare > rightSquare) {
result[index] = leftSquare;
left++;
} else {
result[index] = rightSquare;
right--;
}
index--;
}
return result;
};
// Example usage:
console.log(squaringSortedArray([-4, -1, 0, 3, 10])); // [0, 1, 9, 16, 100]
Note: The two pointers approach allows us to avoid sorting the squared array again, achieving O(n) time complexity instead of O(n log n).
5. Finding Triplet Sum
The Two Pointers pattern is commonly used to solve the "Three Sum" problem, where we need to find all unique triplets in an array that sum up to zero.
| Property | Description | Example |
|---|---|---|
| Input | Array of integers | [1, -2, 1, 0] |
| Target Sum | Zero (0) | 0 |
| Output | List of unique triplets that sum to zero | [[1, -2, 1]] |
Example: Finding Triplet Sum
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 left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
// Example usage:
const nums = [-1, 0, 1, 2, -1, -4];
console.log(threeSum(nums)); // [[-1, -1, 2], [-1, 0, 1]]
Note: The array must be sorted to efficiently use two pointers and avoid duplicates.
Algorithm Steps
- Sort the array to enable two-pointer technique and simplify duplicate handling.
- Iterate through each element as the first element of a potential triplet.
- Use two pointers (left and right) to find pairs that sum with the current element to zero.
- Adjust pointers based on whether the sum is less than or greater than zero.
- Skip duplicates to ensure unique triplets in the result.
6. Comparing Strings for Backspace
| Property | Description | Example |
|---|---|---|
| Backspace character | Represents a delete operation in strings | "a##b" |
| Two-pointer approach | Use two pointers to simulate backspace operations | i and j for traversing from end to start |
Example: Comparing strings with backspace
function backspaceCompare(s, t) {
let i = s.length - 1;
let j = t.length - 1;
let skipS = 0;
let skipT = 0;
while (i >= 0 || j >= 0) {
// Process backspaces for s
if (s[i] === '#') {
skipS++;
i--;
} else if (skipS > 0) {
skipS--;
i--;
} else {
// Process backspaces for t
if (t[j] === '#') {
skipT++;
j--;
} else if (skipT > 0) {
skipT--;
j--;
} else {
// Compare characters
if (s[i] !== t[j]) return false;
i--;
j--;
}
}
}
return true;
}
// Example usage
console.log(backspaceCompare("ab#c", "ad#c")); // true
console.log(backspaceCompare("ab##", "c#d#")); // true
console.log(backspaceCompare("a#c", "b")); // false
Note: The algorithm processes strings from the end to avoid reprocessing characters.
Key Points
- Use two pointers starting from the end of each string
- Count backspaces (
#) to determine how many characters to skip - Compare characters only when no backspaces remain to process
- Time complexity: O(n + m), Space complexity: O(1)
7. Partitioning Arrays
| Property | Description | Usage |
|---|---|---|
| pivot | Element used to divide the array into two parts | Selected element in partitioning logic |
| left pointer | Starts from left side, moves right to find element >= pivot | Used in partitioning to find misplaced elements |
| right pointer | Starts from right side, moves left to find element < pivot | Used in partitioning to find misplaced elements |
Example: Partitioning Around Pivot
function partition(arr, low, high) {
let pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
let arr = [3, 5, 2, 1, 4];
let pivotIndex = partition(arr, 0, arr.length - 1);
console.log(arr); // [2, 1, 3, 5, 4]
Note: The pivot element ends up in its correct sorted position after partitioning.
Partitioning Strategy
- Choose a pivot element from the array
- Rearrange elements so that all elements less than the pivot come before it
- All elements greater than or equal to the pivot come after it
8. Trapping Rain Water
The Trapping Rain Water problem involves calculating how much water can be trapped between bars of different heights, given an array of bar heights.
| Property | Description | Value |
|---|---|---|
| Input | Array of non-negative integers representing bar heights | [0,1,0,2,1,0,1,3,2,1,2,1] |
| Output | Total units of trapped water | 6 |
Example: Trapping Rain Water
function trap(height) {
let left = 0;
let right = height.length - 1;
let leftMax = 0;
let rightMax = 0;
let water = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}
// Example usage:
const height = [0,1,0,2,1,0,1,3,2,1,2,1];
console.log(trap(height)); // Output: 6Algorithm Summary
- Use two pointers, starting from both ends of the array.
- Track maximum height from left and right sides.
- Move the pointer with smaller height inward, accumulating trapped water based on the max height from that side.
- Continue until pointers meet.
9. Finding Container with Most Water
| Property | Description | Example |
|---|---|---|
| Two Pointers Approach | Use left and right pointers to calculate area between lines | let left = 0; let right = height.length - 1; |
| Area Calculation | Area = min(height[left], height[right]) * (right - left) | const area = Math.min(height[left], height[right]) * (right - left); |
| Pointer Movement | Move pointer with smaller height inward | if (height[left] < height[right]) left++; else right--; |
Example: Container With Most Water
function maxArea(height) {
let left = 0;
let right = height.length - 1;
let maxArea = 0;
while (left < right) {
const area = Math.min(height[left], height[right]) * (right - left);
maxArea = Math.max(maxArea, area);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
// Example usage:
const heights = [1, 8, 6, 2, 5, 4, 8, 3, 7];
console.log(maxArea(heights)); // Output: 49
10. Verifying Palindromes
| Property | Description | Example |
|---|---|---|
| Two Pointers Approach | Use left and right pointers to compare characters from both ends moving towards center | |
| Time Complexity | O(n) where n is the length of string | |
| Space Complexity | O(1) - only using constant extra space |
Example: Check if a string is palindrome
function isPalindrome(str) {
let left = 0;
let right = str.length - 1;
while (left < right) {
if (str[left] !== str[right]) return false;
left++;
right--;
}
return true;
}
// Example usage
console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("hello")); // false
Note: For case-insensitive checks, convert string to lowercase before comparison.
Example: Handle special characters and spaces
function isPalindromeAlphanumeric(str) {
let left = 0;
let right = str.length - 1;
while (left < right) {
// Skip non-alphanumeric from left
while (left < right && !isAlphaNumeric(str[left])) {
left++;
}
// Skip non-alphanumeric from right
while (left < right && !isAlphaNumeric(str[right])) {
right--;
}
if (str[left].toLowerCase() !== str[right].toLowerCase()) {
return false;
}
left++;
right--;
}
return true;
}
function isAlphaNumeric(char) {
return /[a-zA-Z0-9]/.test(char);
}
// Example usage
console.log(isPalindromeAlphanumeric("A man, a plan, a canal: Panama")); // true11. Partitioning Arrays by Pivot
| Property | Description | Usage |
|---|---|---|
| pivot | Element used to partition the array | Selected element for comparison in partitioning logic |
| left pointer | Starts at the beginning of the array | Moves right until finding an element greater than or equal to pivot |
| right pointer | Starts at the end of the array | Moves left until finding an element less than or equal to pivot |
Example: Partitioning Logic
function partition(arr, low, high) {
let pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
Note: The pivot element is placed in its correct sorted position after partitioning.
Partitioning Strategy
- Select a pivot element from the array
- Rearrange elements so that all elements less than the pivot come before it
- All elements greater than the pivot come after it
- Partitioning is a key step in QuickSort algorithm
12. Merging Sorted Arrays In-Place
| Property | Description | Usage |
|---|---|---|
| Two Pointers | Use two pointers starting from the end of both arrays to merge in-place | Efficient for merging sorted arrays without extra space |
Example: Merging Two Sorted Arrays In-Place
function mergeSortedArrays(arr1, arr2) {
let i = arr1.length - 1;
let j = arr2.length - 1;
let k = arr1.length + arr2.length - 1;
// Extend arr1 to accommodate both arrays
arr1.length = k + 1;
// Merge from the end
while (i >= 0 && j >= 0) {
if (arr1[i] > arr2[j]) {
arr1[k--] = arr1[i--];
} else {
arr1[k--] = arr2[j--];
}
}
// Copy remaining elements from arr2
while (j >= 0) {
arr1[k--] = arr2[j--];
}
return arr1;
}
// Example usage:
const arr1 = [1, 3, 5, 7];
const arr2 = [2, 4, 6, 8];
console.log(mergeSortedArrays(arr1, arr2)); // [1, 2, 3, 4, 5, 6, 7, 8]