Two Pointers Technique
Simplify and optimize problems using the two pointers approach.
What is the Two Pointers Technique?
The Two Pointers Technique is a powerful approach to solve problems involving arrays or strings by using two pointers that traverse the data structure in a coordinated manner. This technique is often used to reduce time complexity compared to traditional nested loops.
Key Concepts in Two Pointers
-
Pointers Movement:
- Opposite Direction: Start one pointer at the beginning and the other at the end, moving them toward each other (e.g., checking for a palindrome or two-sum in a sorted array).
- Same Direction: Start both pointers from the same side and advance them at different rates (e.g., finding subarrays or solving sliding window problems).
-
Conditions for Use:
- The array or string must be sorted in many cases (e.g., two-sum in a sorted array).
- Problems should have a linear or near-linear solution, often replacing nested loops.
Time & Space Complexities
- Time Complexity: Typically
O(n)since each pointer traverses the array only once. - Space Complexity:
O(1)as no extra space is used.
When to Use Two Pointers
This technique is commonly used in problems like:
- Finding pairs with a given sum (e.g., two-sum).
- Merging two sorted arrays.
- Solving substring or subarray problems.
- Detecting cycles in linked lists (Floyd's cycle detection).
- Validating palindromes or skipping specific characters.
Code Examples
Below is an example of using the Two Pointers technique to solve the Two-Sum in a Sorted Array problem.
#include <iostream>
#include <vector>
using namespace std;
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0, right = numbers.size() - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return {left + 1, right + 1}; // Return 1-based indices
} else if (sum < target) {
left++; // Move left pointer right
} else {
right--; // Move right pointer left
}
}
return {}; // No solution
}
int main() {
vector<int> numbers = {2, 7, 11, 15};
int target = 9;
vector<int> result = twoSum(numbers, target);
if (!result.empty()) {
cout << "Indices: " << result[0] << ", " << result[1] << endl;
} else {
cout << "No solution found." << endl;
}
return 0;
}