Chapter 14 of 30
Two Pointers & Sliding Window
Master two pointers (opposite and same direction) and sliding window (fixed and variable size) techniques.
Two Pointers (Opposite Direction)Two Pointers (Same Direction)Sliding Window (Fixed Size)Sliding Window (Variable Size)
Share:
Two Pointers & Sliding Window
Two pointers and sliding window are O(n) techniques that replace brute-force O(n²) approaches. They work when the problem has a monotonic property — as one pointer moves forward, the other can only move in one direction.
Two Pointers (Opposite Direction)
Both pointers start at opposite ends and move toward each other:
Classic: Two Sum (Sorted Array)
hljs cpp
// Find two numbers that sum to target in a sorted array
int left = 0, right = n - 1;
while (left < right) {
int sum = a[left] + a[right];
if (sum == target) {
// found: left and right
break;
} else if (sum < target) {
left++; // need larger sum
} else {
right--; // need smaller sum
}
}
Palindrome Check
hljs cpp
bool isPalindrome(string &s) {
int left = 0, right = s.size() - 1;
while (left < right) {
if (s[left] != s[right]) return false;
left++;
right--;
}
return true;
}
Two Pointers (Same Direction)
Both pointers move in the same direction, but at different speeds:
Remove Duplicates from Sorted Array
hljs cpp
int write = 0;
for (int read = 1; read < n; read++) {
if (a[read] != a[write]) {
write++;
a[write] = a[read];
}
}
// Unique elements: a[0..write]
Move Zeroes to End
hljs cpp
int write = 0;
for (int read = 0; read < n; read++) {
if (a[read] != 0) {
swap(a[read], a[write]);
write++;
}
}
Sliding Window (Fixed Size)
A window of fixed size k slides across the array:
Maximum Sum Subarray of Size K
hljs cpp
long long windowSum = 0;
for (int i = 0; i < k; i++) windowSum += a[i];
long long maxSum = windowSum;
for (int i = k; i < n; i++) {
windowSum += a[i] - a[i - k]; // slide: add new, remove old
maxSum = max(maxSum, windowSum);
}
First Negative in Every Window of Size K
hljs cpp
queue<int> negatives; // indices of negative numbers
for (int i = 0; i < n; i++) {
if (a[i] < 0) negatives.push(i);
if (i >= k - 1) {
while (!negatives.empty() && negatives.front() <= i - k) {
negatives.pop();
}
cout << (negatives.empty() ? 0 : a[negatives.front()]) << " ";
}
}
Sliding Window (Variable Size)
The window expands and contracts based on a condition:
Longest Substring Without Repeating Characters
hljs cpp
unordered_set<char> seen;
int left = 0, maxLen = 0;
for (int right = 0; right < (int)s.size(); right++) {
while (seen.count(s[right])) {
seen.erase(s[left]);
left++;
}
seen.insert(s[right]);
maxLen = max(maxLen, right - left + 1);
}
Minimum Window Substring
Find the smallest substring of s that contains all characters of t:
hljs cpp
unordered_map<char, int> need, have;
for (char c : t) need[c]++;
int formed = 0, required = need.size();
int left = 0, minLen = INT_MAX, minStart = 0;
for (int right = 0; right < (int)s.size(); right++) {
char c = s[right];
have[c]++;
if (have[c] == need[c]) formed++;
while (formed == required) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minStart = left;
}
have[s[left]]--;
if (have[s[left]] < need[s[left]]) formed--;
left++;
}
}
Subarray Sum Equals K
hljs cpp
// Prefix sum + hashmap approach
map<long long, int> count;
count[0] = 1;
long long prefix = 0;
int result = 0;
for (int i = 0; i < n; i++) {
prefix += a[i];
result += count[prefix - k];
count[prefix]++;
}
When to Use Each Technique
| Pattern | When to Use |
|---|---|
| Two pointers (opposite) | Sorted array, find pair with specific property |
| Two pointers (same direction) | Remove duplicates, partition array |
| Fixed sliding window | Subarray of size k, window property |
| Variable sliding window | Longest/shortest subarray satisfying condition |
Summary
- Two pointers reduce O(n²) to O(n) when one pointer's movement is constrained
- Fixed sliding window: add new element, remove old element — O(n)
- Variable sliding window: expand to satisfy, contract to minimize — O(n)
- The key insight: if expanding the window can only make the property "worse," you can use two pointers
Prefer reading offline? Download the full book as a PDF.
Download Free Book