.png)
Two Pointers Technique –
1. Introduction
The Two Pointers Technique is an algorithmic approach where two indices (pointers) are used to traverse a data structure in a coordinated manner to solve problems efficiently.
Instead of checking every possible combination (which is slow), we intelligently move pointers based on conditions, reducing unnecessary computations.
This technique is widely used in:
- Arrays
- Strings
- Linked Lists
2. Why Two Pointers?
Many problems involve:
- Finding pairs
- Checking ranges
- Comparing elements from both ends
A brute-force approach usually leads to O(n²) time complexity.
Two pointers often reduce it to O(n).
3. When to Use Two Pointers
Use this technique when:
- Input is sorted
- Pair sum
- Closest sum
- Triplets
- Pair / Range based problems
- Subarrays
- Palindrome checking
- Sliding window problems
- Longest substring
- Smallest subarray with sum ≥ K
- Linked list traversal
- Detecting cycles
- Finding middle node
4. Problem Statement (Example)
Sum of Pair Equal to Target
Given:
A sorted array arr[] of integers and an integer target.
Task:
Check whether there exists a pair (arr[i], arr[j]) such that:
arr[i] + arr[j] == target
5. Illustration (Language Independent)
Example
Array: [-8, 1, 4, 6, 10, 45]
Target: 16
Index: 0 1 2 3 4 5
Array: -8 1 4 6 10 45
↑ ↑
left right
Sum = -8 + 45 = 37 → too large → move right
Index: 0 1 2 3 4 5
Array: -8 1 4 6 10 45
↑ ↑
left right
Sum = -8 + 10 = 2 → too small → move left
Index: 0 1 2 3 4 5
Array: -8 1 4 6 10 45
↑ ↑
left right
Sum = 6 + 10 = 16 ✅ FOUND
6. Algorithm (Two Pointer Technique)
- Initialize two pointers:
- left = 0
- right = n - 1
- While left < right:
- Compute sum = arr[left] + arr[right]
- If sum == target → return true
- If sum < target → left++
- If sum > target → right--
- If loop ends → return false
7. Why This Algorithm Works
Case 1: Sum < Target → Move Left
- Current left value is too small
- Moving right further only decreases possibilities
- Safe to discard arr[left]
Case 2: Sum > Target → Move Right
- Current right value is too large
- Moving left pointer increases sum
- Safe to discard arr[right]
✔ Because the array is sorted, we never miss a valid pair
Implementations in All Languages
C++ Implementation
#include
#include
using namespace std;
bool twoSum(vector& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target)
return true;
else if (sum < target)
left++;
else
right--;
}
return false;
}
int main() {
vector arr = {-8, 1, 4, 6, 10, 45};
int target = 16;
cout << (twoSum(arr, target) ? "true" : "false");
return 0;
}
Output
true
C Implementation
#include
int twoSum(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target)
return 1;
else if (sum < target)
left++;
else
right--;
}
return 0;
}
int main() {
int arr[] = {-8, 1, 4, 6, 10, 45};
int target = 16;
int n = sizeof(arr) / sizeof(arr[0]);
printf(twoSum(arr, n, target) ? "true" : "false");
return 0;
}
Output
true
Java Implementation
class TwoSum {
static boolean twoSum(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target)
return true;
else if (sum < target)
left++;
else
right--;
}
return false;
}
public static void main(String[] args) {
int[] arr = {-8, 1, 4, 6, 10, 45};
int target = 16;
System.out.println(twoSum(arr, target));
}
}
Output
true
Python Implementation
def two_sum(arr, target):
left = 0
right = len(arr) - 1
while left < right:
s = arr[left] + arr[right]
if s == target:
return True
elif s < target:
left += 1
else:
right -= 1
return False
arr = [-8, 1, 4, 6, 10, 45]
target = 16
print(two_sum(arr, target))
Output
True
C# Implementation
using System;
class Program {
static bool TwoSum(int[] arr, int target) {
int left = 0;
int right = arr.Length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target)
return true;
else if (sum < target)
left++;
else
right--;
}
return false;
}
static void Main() {
int[] arr = {-8, 1, 4, 6, 10, 45};
int target = 16;
Console.WriteLine(TwoSum(arr, target));
}
}
Output
True
JavaScript Implementation
function twoSum(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
let sum = arr[left] + arr[right];
if (sum === target)
return true;
else if (sum < target)
left++;
else
right--;
}
return false;
}
let arr = [-8, 1, 4, 6, 10, 45];
let target = 16;
console.log(twoSum(arr, target));
Output
true
9. Time and Space Complexity
| Metric | Value |
|---|---|
| Time Complexity | O(n) |
| Space Complexity | O(1) |
10. Summary
- Two Pointers is one of the most important interview techniques
- Works best on sorted data
- Reduces time from O(n²) → O(n)
- Used in many advanced problems like:
- Three Sum
- Trapping Rain Water
- Sliding Window problems
Next Blog-
Prefix Sum Technique
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
