What is the Two Pointers Technique:
uses two index variables to traverse a linear data structure—like an array, string, or linked list—to solve problems efficiently without nested loops.
Why Use it ?
Time Efficiency: It often reduces time complexity from O(n²) (using nested loops) down to linear time O(n).
Space Efficiency: It typically requires constant space O(1) because it only tracks a few indices.
Whats Patterns of 2 Pointers
Pattern 1 (Variable_Size)
1.1 Opposite Direction (Converging Pointers):One pointer starts at the beginning (left = 0) and the other at the end (right = n — 1). They move toward each other until they meet. Best Used For: Sorted arrays, pair sum problems (ex: Two Sum on sorted input), or checking palindromes.
Problem: Can you choose two indices i , j (i≠j) and ai+aj=K If you can choose to indices solving the equation print "YES" otherwise "NO"
Brute Force Approach (TLE-->O(N^2))
int n;
long long x;
cin >> n >> x;
vector<long long> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
// Brute Force: Check every pair (i, j) where i != j
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] + arr[j] == x) {
cout << "YES\n";
return 0;
}
}
}
cout << "NO\n";
How to optmize to avoid TLE using 2 Pointers ?
long long n,x; cin>>n>>x;
int arr[n];
for(int i=0;i<n;i++) cin>>arr[i];
sort(arr,arr+n);
long long s=0,r=n-1;
while(r>s){
if(arr[s]+arr[r]>x){
r--;
}else if(arr[s]+arr[r]<x){
s++;
}else if(arr[s]+arr[r]==x){
cout<<"YES";
return 0;
}
}
cout<<"NO";
Explaning:
1.Why Brute Force Fails: In the naive O(N^2) code, we test every pair independently without learning anything from previous comparisons. We waste time adding numbers we already know are too big or too small.
2. The Key Insight (Sorting): If we sort the array first (O(N \log N)), the elements gain a predictable order:
Moving left to right->values increase.
Moving right to left->values decrease.
3.How Pointers Guide the Decision:
Instead of testing all pairs, we place one pointer at the smallest value (s = 0) and another at the largest value (r = n — 1): Sum too large (arr[s] + arr[r] > x)?
Since arr[s] is the absolute smallest available number, keeping arr[r] will never give a smaller target sum with any other element. Thus, arr[r] is useless — we safely discard it by doing r--.
Sum too small (arr[s] + arr[r] < x)?
Similarly, arr[r] is the largest available number. If even adding arr[r] can't reach x, then arr[s] is too small to pair with anything. We safely discard it by doing s++.
By making a single directional decision at each step, every element is eliminated at most once. The search loop runs in O(N) time, bringing the overall time complexity down to O(N \log N) (dominated by std::sort), which easily passes within the time limit!
1.2Same Direction (Parallel):
Both pointers start at the same end and move forward. One might move faster than the other,
which is useful for removing duplicates or sliding windows.Fast and Slow: One pointer moves faster than the other.
Problem:
Given an array of n books, where each book i takes a_i minutes to read, and a total free time of t minutes. Find the maximum number of contiguous books you can read without exceeding t minutes. The Naive Approach (O(N^2)) — TLE
For every starting position l, we expand r to compute the total reading time from scratch. When the sum exceeds t, we discard everything, increment l, and restart the summation. This recalculates overlapping elements repeatedly
// Time Complexity: O(N^2) - TLE
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
long long t;
cin >> n >> t;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
int max_books = 0;
for (int l = 0; l < n; l++) {
long long current_sum = 0;
int count = 0;
for (int r = l; r < n; r++) {
if (current_sum + a[r] <= t) {
current_sum += a[r];
count++;
} else {
break;
}
}
max_books = max(max_books, count);
}
cout << max_books << "\n";
return 0;
}
How to get optimal Solution in 2 Pointers ?
// Time Complexity: O(N)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
long long t;
cin >> n >> t;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
int l = 0, max_books = 0;
long long current_sum = 0;
for (int r = 0; r < n; r++) {
current_sum += a[r]; // Expand window to the right
// Shrink window from the left if time limit is exceeded
while (current_sum > t) {
current_sum -= a[l];
l++;
}
// Update maximum books read in a valid window
max_books = max(max_books, r - l + 1);
}
cout << max_books << "\n";
return 0;
}
2.1 Fixed-Size Pattern:
Unlike variable-size windows where the range expands and shrinks based on a condition, the Fixed-Size Sliding Window maintains a constant window length of K.
Core Logic:
Build First Window: Compute the result (e.g., sum) for the first K elements (0 to K-1).
Iterate r from index K to N-1:
Add the incoming element at r.
Remove the outgoing element at r — K.
Update the global answer.
Problem:There are n consecutive fence planks with heights h_1, h_2,..., h_n. You need to find k consecutive planks such that the sum of their heights is minimized. Print the 1-based starting index of these k planks.
// Time Complexity: O(N)
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
vector<int> h(n);
for (int i = 0; i < n; i++) cin >> h[i];
// 1. Calculate sum of the first window of size K
long long current_sum = 0;
for (int i = 0; i < k; i++) {
current_sum += h[i];
}
long long min_sum = current_sum;
int min_index = 0;
// 2. Slide the window of size K
for (int r = k; r < n; r++) {
current_sum += h[r]; // Add right element
current_sum -= h[r - k]; // Remove left element
if (current_sum < min_sum) {
min_sum = current_sum;
min_index = r - k + 1; // Start index of current window
}
}
cout << min_index + 1 << "\n";
return 0;
}
