Two Pointer Technique
Two Pointer Idea
The two-pointer technique uses two index variables that move through an array, often from opposite ends or at different speeds, to solve a problem in one pass instead of the nested loops a brute-force approach would need.
Example: Two Pointer Idea
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 2, 3, 4, 5};
int left = 0, right = 4;
while (left < right) { // two indices moving through the array in one pass
cout << arr[left] << "+" << arr[right] << " ";
left++; right--;
}
cout << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int left = 0, right = 4;
while (left < right) {
System.out.print(arr[left] + "+" + arr[right] + " ");
left++; right--;
}
System.out.println();
}
}arr = [1, 2, 3, 4, 5]
left, right = 0, 4
while left < right: # two indices moving through the array in one pass
print(f"{arr[left]}+{arr[right]}", end=" ")
left += 1
right -= 1
print()#include <stdio.h>
int main() {
int arr[] = {1, 2, 3, 4, 5};
int left = 0, right = 4;
while (left < right) {
printf("%d+%d ", arr[left], arr[right]);
left++; right--;
}
printf("\n");
return 0;
}Login to try C/C++/Java code in the editor
Pair Sum
On a sorted array, placing one pointer at the start and one at the end lets you find a pair that sums to a target value in O(n): if the current sum is too small, move the left pointer right; if too large, move the right pointer left.
Example: Pair Sum
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 3, 5, 7, 9};
int n = 5, target = 12;
int left = 0, right = n - 1;
while (left < right) {
int s = arr[left] + arr[right];
if (s == target) { cout << arr[left] << " + " << arr[right] << " = " << target << endl; break; }
else if (s < target) left++;
else right--;
}
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9};
int target = 12, left = 0, right = arr.length - 1;
while (left < right) {
int s = arr[left] + arr[right];
if (s == target) { System.out.println(arr[left] + " + " + arr[right] + " = " + target); break; }
else if (s < target) left++;
else right--;
}
}
}arr = [1, 3, 5, 7, 9]
target = 12
left, right = 0, len(arr) - 1
while left < right:
s = arr[left] + arr[right]
if s == target:
print(f"{arr[left]} + {arr[right]} = {target}")
break
elif s < target:
left += 1
else:
right -= 1#include <stdio.h>
int main() {
int arr[] = {1, 3, 5, 7, 9};
int n = 5, target = 12, left = 0, right = n - 1;
while (left < right) {
int s = arr[left] + arr[right];
if (s == target) { printf("%d + %d = %d\n", arr[left], arr[right], target); break; }
else if (s < target) left++;
else right--;
}
return 0;
}Login to try C/C++/Java code in the editor
Remove Duplicates
To remove duplicates from a sorted array in place, one pointer tracks the last unique value written so far while a second pointer scans ahead looking for the next distinct value, compacting all unique elements to the front.
Example: Remove Duplicates
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 1, 2, 2, 3, 4, 4};
int n = 7;
int slow = 0;
for (int fast = 1; fast < n; fast++) {
if (arr[fast] != arr[slow]) {
slow++;
arr[slow] = arr[fast];
}
}
cout << "Unique count: " << slow + 1 << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {1, 1, 2, 2, 3, 4, 4};
int slow = 0;
for (int fast = 1; fast < arr.length; fast++) {
if (arr[fast] != arr[slow]) {
slow++;
arr[slow] = arr[fast];
}
}
System.out.println("Unique count: " + (slow + 1));
}
}arr = [1, 1, 2, 2, 3, 4, 4]
slow = 0
for fast in range(1, len(arr)):
if arr[fast] != arr[slow]:
slow += 1
arr[slow] = arr[fast]
print("Unique count:", slow + 1)#include <stdio.h>
int main() {
int arr[] = {1, 1, 2, 2, 3, 4, 4};
int n = 7, slow = 0;
for (int fast = 1; fast < n; fast++) {
if (arr[fast] != arr[slow]) {
slow++;
arr[slow] = arr[fast];
}
}
printf("Unique count: %d\n", slow + 1);
return 0;
}Login to try C/C++/Java code in the editor
Partitioning
For partitioning, one pointer tracks where the next wanted element should go while the other scans the array, swapping elements so that values satisfying some condition end up grouped on one side, similar in spirit to a step of quicksort's partition.
Example: Partitioning
#include <iostream>
using namespace std;
int main() {
int arr[] = {5, 2, 8, 1, 9, 3};
int n = 6, pivot = 5;
int wanted = 0; // where the next 'less than pivot' element should go
for (int i = 0; i < n; i++) {
if (arr[i] < pivot) {
swap(arr[i], arr[wanted]);
wanted++;
}
}
cout << "First element >= pivot at index: " << wanted << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {5, 2, 8, 1, 9, 3};
int pivot = 5, wanted = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
int tmp = arr[i]; arr[i] = arr[wanted]; arr[wanted] = tmp;
wanted++;
}
}
System.out.println("First element >= pivot at index: " + wanted);
}
}arr = [5, 2, 8, 1, 9, 3]
pivot = 5
wanted = 0 # where the next 'less than pivot' element should go
for i in range(len(arr)):
if arr[i] < pivot:
arr[i], arr[wanted] = arr[wanted], arr[i]
wanted += 1
print("First element >= pivot at index:", wanted)#include <stdio.h>
int main() {
int arr[] = {5, 2, 8, 1, 9, 3};
int n = 6, pivot = 5, wanted = 0;
for (int i = 0; i < n; i++) {
if (arr[i] < pivot) {
int tmp = arr[i]; arr[i] = arr[wanted]; arr[wanted] = tmp;
wanted++;
}
}
printf("First element >= pivot at index: %d\n", wanted);
return 0;
}Login to try C/C++/Java code in the editor
Two Pointer Practice
Two pointers work especially well when the array is sorted or when you're scanning from both ends inward, turning what would be an O(n²) brute-force search into an O(n) linear-time solution.
Example: Two Pointer Practice
#include <iostream>
using namespace std;
int main() {
// Sorted array: two pointers turn an O(n^2) brute-force pair search into O(n).
int arr[] = {2, 4, 6, 8, 10};
int target = 14, left = 0, right = 4;
while (left < right) {
int s = arr[left] + arr[right];
if (s == target) { cout << "Found: " << arr[left] << "," << arr[right] << endl; break; }
s < target ? left++ : right--;
}
return 0;
}public class Main {
public static void main(String[] args) {
// Sorted array: two pointers turn O(n^2) brute-force into O(n).
int[] arr = {2, 4, 6, 8, 10};
int target = 14, left = 0, right = 4;
while (left < right) {
int s = arr[left] + arr[right];
if (s == target) { System.out.println("Found: " + arr[left] + "," + arr[right]); break; }
if (s < target) left++; else right--;
}
}
}# Sorted array: two pointers turn an O(n^2) brute-force search into O(n).
arr = [2, 4, 6, 8, 10]
target = 14
left, right = 0, 4
while left < right:
s = arr[left] + arr[right]
if s == target:
print(f"Found: {arr[left]},{arr[right]}")
break
if s < target:
left += 1
else:
right -= 1#include <stdio.h>
int main() {
int arr[] = {2, 4, 6, 8, 10};
int target = 14, left = 0, right = 4;
while (left < right) {
int s = arr[left] + arr[right];
if (s == target) { printf("Found: %d,%d\n", arr[left], arr[right]); break; }
if (s < target) left++; else right--;
}
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 8 topics to unlock
0/8 topics done
Complete these topics first: