Introduction In competitive programming, optimizing time complexity is crucial. A common scenario is when we need to process pairs or subarrays. A naive solution often involves nested loops with O(n^2) complexity. This is where the Two Pointers technique shines — it allows you to solve many of these problems in O(n) or O(n log n) time.
**What is the Two Pointers Technique? : ** The idea is simple:
Maintain two indices (commonly named left and right).
Move these pointers intelligently to process the array or string.
The pointers either move toward each other or in the same direction (depending on the problem).
It is especially effective when the input is sorted or when we need to work on a window (subarray).
Typical Use Cases : Finding pairs with a specific sum in a sorted array.
Sliding Window problems (e.g., longest subarray with some condition).
Merging sorted arrays or intervals.
String problems like checking for palindromes.
Two arrays comparison and intersection problems.
Example Problem (Pair Sum) Problem Statement: Given a sorted array arr and a number k, check if there exists a pair of numbers in the array that sums to k.
Approach using Two Pointers:
Set left = 0 and right = n-1.
If arr[left] + arr[right] == k, we found a pair.
If the sum is less than k, we increase left (to get a bigger sum).
If the sum is greater than k, we decrease right (to get a smaller sum).
C++ Implementation :
#include
using namespace std;
bool pairSum(vector& arr, int k) {
int left = 0, right = arr.size() — 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == k) return true;
else if (sum < k) left++;
else right--;
}
return false;
}
int main() {
vector arr = {1, 2, 4, 7, 11};
int k = 15;
cout << (pairSum(arr, k) ? "YES" : "NO") << "\n";
}
Time Complexity: O(n)
Step-by-Step Learning Roadmap : Here is how you can master this technique:
Start with basic problems involving sorted arrays or simple subarrays.
Move on to sliding window problems.
Practice medium-level Codeforces problems that combine sorting + two pointers.
Tackle harder problems where two pointers are combined with binary search or DP.
Codeforces Problems for Practice Here are curated problems from easy to hard:
Easy : 381A — Sereja and Dima
1490B — Balanced Remainders
702A — Maximum Increase
Medium : 676C — Vasya and String (classic sliding window)
381B — Sum of Medians
1201A — Important Exam
Hard : 1256D — Binary String Minimizing
987C — Three Displays
1276C — Beautiful Pairs of Numbers
Pro Tips : If you see nested loops checking subarray sums or pairs, always think: Can this be solved with two pointers?
Combine with prefix sums or sorting for more complex problems.
For string problems (like "at most K changes"), two pointers + frequency counters are your friends.
Conclusion The Two Pointers technique is a must-have weapon in a competitive programmer's arsenal. With enough practice, you will start recognizing patterns where this technique applies immediately, saving both time and complexity.
