> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.
# Two Pointers & Sliding Window
> Transform O(n²) brute force into elegant O(n) solutions
# Two Pointers & Sliding Window
## The Mental Model
Imagine you are adjusting a rubber band stretched between two fingers on a number line. You can stretch it wider by moving your right finger forward, or shrink it by sliding your left finger forward. The critical insight is that **neither finger ever moves backwards**. Each finger visits each position at most once, so the total work is O(n) + O(n) = O(n), even though it looks like a nested loop.
Compare this to the brute force approach, where you would try every possible left position with every possible right position---that is O(n^2) pairs. Two pointers exploit the monotonic structure of the problem to skip the vast majority of those pairs.
**Pattern Recognition Signals**:
* "Find pair/triplet with property X"
* "Subarray with sum/length condition"
* Array is **sorted** or can be sorted
* Need to avoid O(n²) nested loops
***
## When to Use Two Pointers
* Sorted array + finding pairs
* Subarray with sum/length constraints
* Palindrome checking
* Merging sorted arrays
* Removing duplicates in-place
* Need to preserve original order
* No monotonic property exists
* Need random access queries
* Prefix sum is more natural
***
## The Two Pointer Variants
### Variant 1: Opposite Ends (Converging)
**Use for**: Sorted arrays, finding pairs with target sum, palindromes.
```cpp theme={null}
// Template: Two Sum in Sorted Array
pair twoSumSorted(vector& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
return {left, right};
} else if (sum < target) {
left++; // Need larger sum
} else {
right--; // Need smaller sum
}
}
return {-1, -1}; // Not found
}
```
**Why It Works**: The array is sorted. If the current sum is too small, the only way to increase it is to replace the smaller number with a larger one---move left pointer right. If the sum is too large, replace the larger number---move right pointer left. We never miss the answer because every pair we skip is provably worse. **Complexity**: O(n) after sorting. Each pointer moves at most n times.
**Common Mistake**: Forgetting to sort first. Two-sum with converging pointers requires a sorted array. If you cannot sort (because you need original indices), use a hashmap approach instead.
### Variant 2: Same Direction (Fast & Slow)
**Use for**: Removing duplicates, cycle detection, partitioning.
```cpp theme={null}
// Template: Remove Duplicates from Sorted Array
int removeDuplicates(vector& arr) {
if (arr.empty()) return 0;
int slow = 0; // Position to write next unique element
for (int fast = 1; fast < arr.size(); fast++) {
if (arr[fast] != arr[slow]) {
slow++;
arr[slow] = arr[fast];
}
}
return slow + 1; // Length of unique portion
}
```
### Variant 3: Sliding Window
**Use for**: Subarray with sum/product condition, longest/shortest subarray.
```cpp theme={null}
// Template: Smallest Subarray with Sum >= Target
int minSubarrayLen(int target, vector& nums) {
int left = 0, sum = 0;
int minLen = INT_MAX;
for (int right = 0; right < nums.size(); right++) {
sum += nums[right]; // Expand window
while (sum >= target) { // Shrink while valid
minLen = min(minLen, right - left + 1);
sum -= nums[left];
left++;
}
}
return minLen == INT_MAX ? 0 : minLen;
}
```
***
## Pattern Recognition: Sliding Window Types
### Fixed-Size Window
**Signal**: "Find max/min/count in every window of size K"
```cpp theme={null}
// Maximum sum of subarray of size K
int maxSumSubarray(vector& arr, int k) {
int n = arr.size();
if (n < k) return -1;
// Compute first window
int windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += arr[i];
}
int maxSum = windowSum;
// Slide the window
for (int i = k; i < n; i++) {
windowSum += arr[i] - arr[i - k]; // Add new, remove old
maxSum = max(maxSum, windowSum);
}
return maxSum;
}
```
### Variable-Size Window
**Signal**: "Find longest/shortest subarray where condition holds"
```cpp theme={null}
// Longest substring with at most K distinct characters
// Complexity: O(n) -- each element is added once and removed once
int longestWithKDistinct(string& s, int k) {
unordered_map charCount;
int left = 0, maxLen = 0;
for (int right = 0; right < (int)s.size(); right++) {
charCount[s[right]]++; // Expand: add new character to window
// Shrink window while invalid (too many distinct chars)
while ((int)charCount.size() > k) {
charCount[s[left]]--;
if (charCount[s[left]] == 0) {
charCount.erase(s[left]); // Remove char entirely when count hits 0
}
left++;
}
// Window [left, right] now has at most k distinct characters
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}
```
**Worked Example**: s = "aabacbebebe", k = 3
* Window grows: "a", "aa", "aab", "aaba", "aabac" (3 distinct: a,b,c)
* Adding 'b': "aabacb" still 3 distinct, fine
* Adding 'e': "aabacbe" has 4 distinct, must shrink from left
* Remove 'a','a','b','a','c' until distinct count drops to 3
* Continue expanding from right...
* Answer: "cbebebe" with length 7
**Contest Tip**: For variable-size sliding window problems, the hardest part is deciding the window invariant. Write it down explicitly before coding: "The window \[left, right] always satisfies \_\_\_." This prevents subtle off-by-one bugs in the shrink condition.
***
## The "When to Shrink" Framework
For sliding window, the key question is: **when do I move the left pointer?**
| Problem Type | Shrink When |
| ----------------------------- | -------------------- |
| Sum ≥ target (minimum length) | Window sum ≥ target |
| Sum ≤ target (maximum length) | Window sum > target |
| At most K distinct | More than K distinct |
| No duplicates | Duplicate found |
**General Rule**: For "minimum length" problems, shrink while valid. For "maximum length" problems, shrink while invalid.
***
## Classic Problems & Solutions
### Three Sum (CF Pattern)
**Problem**: Find all triplets that sum to zero.
**Approach**: Fix one element, use two pointers for the remaining two.
```cpp theme={null}
vector> threeSum(vector& nums) {
vector> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
// Skip duplicates for first element
if (i > 0 && nums[i] == nums[i-1]) continue;
int target = -nums[i];
int left = i + 1, right = nums.size() - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
result.push_back({nums[i], nums[left], nums[right]});
// Skip duplicates
while (left < right && nums[left] == nums[left+1]) left++;
while (left < right && nums[right] == nums[right-1]) right--;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;
}
```
### Container With Most Water
**Problem**: Given heights, find two lines that form container with most water.
**Insight**: Start from ends. The limiting factor is the shorter line. Moving the shorter line might find a taller one; moving the taller can't help.
```cpp theme={null}
int maxArea(vector& height) {
int left = 0, right = height.size() - 1;
int maxWater = 0;
while (left < right) {
int h = min(height[left], height[right]);
int w = right - left;
maxWater = max(maxWater, h * w);
// Move the shorter line
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxWater;
}
```
***
## Common Mistakes
**Mistake 1: Wrong Shrink Condition**
```cpp theme={null}
// WRONG: Shrinking when should expand
while (sum > target) { ... } // For "sum >= target" minimum length
// CORRECT
while (sum >= target) {
minLen = min(minLen, right - left + 1);
sum -= nums[left++];
}
```
**Mistake 2: Forgetting Edge Cases**
* Empty array
* Single element
* All elements same
* No valid window exists
**Mistake 3: Infinite Loop**
Make sure left pointer can never exceed right pointer:
```cpp theme={null}
while (left < right) { // Not left <= right for two pointers
// ...
}
```
***
## Practice Problems
### Beginner (800-1100)
| Problem | Pattern | Link |
| ------------------- | ----------------------- | ------------------------------------------------------------ |
| Pair with Given Sum | Two pointers converging | [CSES](https://cses.fi/problemset/task/1640) |
| Maximum Subarray | Sliding window | [CF 1343B](https://codeforces.com/problemset/problem/1343/B) |
### Intermediate (1100-1400)
| Problem | Pattern | Link |
| ---------------------- | ------------------------- | ---------------------------------------------------------- |
| Segment with Small Sum | Sliding window | [CF 279B](https://codeforces.com/problemset/problem/279/B) |
| Books | Two pointers | [CF 279B](https://codeforces.com/problemset/problem/279/B) |
| Vasya and String | Sliding window + counting | [CF 676C](https://codeforces.com/problemset/problem/676/C) |
### Advanced (1400-1700)
| Problem | Pattern | Link |
| --------------------- | ---------------------------- | ------------------------------------------------------------ |
| Playlist | Sliding window + set | [CF 1296E](https://codeforces.com/problemset/problem/1296/E) |
| K-Good Segment | Binary search + two pointers | [CF 616D](https://codeforces.com/problemset/problem/616/D) |
| String Transformation | Two pointers | [CF 946D](https://codeforces.com/problemset/problem/946/D) |
***
## Decision Flowchart
```
Is array sorted (or can be sorted)?
├── Yes: Do you need pairs?
│ ├── Yes → Two Pointers (converging)
│ └── No: Subarray condition?
│ ├── Yes → Sliding Window
│ └── No → Consider other techniques
└── No: Is sorting acceptable?
├── Yes → Sort first, then two pointers
└── No: Can problem be reformulated?
├── Yes → Prefix sum + hashmap
└── No → Likely different pattern
```
**Contest Tip -- Two Pointers vs Prefix Sum**: Both solve subarray problems in O(n), but they have different strengths. Two pointers/sliding window require that expanding the window always makes the property "more satisfied" (monotonicity). Prefix sum + hashmap works even when elements can be negative (no monotonicity needed). If the array has negative numbers and you are looking for a subarray sum, use prefix sum. If all elements are positive and you want longest/shortest subarray with sum condition, two pointers is usually cleaner.
***
## Key Takeaways
Two pointers work when moving in one direction doesn't require backtracking.
For minimum → shrink while valid. For maximum → shrink while invalid.
Many two-pointer problems require sorted input. Don't forget to sort.
Use hashmap/set to track window contents when needed.
***
## Next Up
Master the art of binary search—not just on arrays, but on the answer itself.
***
## Interview Deep-Dive
**Strong Answer:**
* This is a variable-size sliding window problem. Maintain a left and right pointer, expand right to increase the window sum, and shrink left while the sum is >= S. Track the minimum window length seen.
* Why it works: because all elements are positive, expanding the window (moving right) always increases the sum, and shrinking (moving left) always decreases it. This monotonicity guarantees that each pointer moves at most n times total, giving O(n) time.
* Key insight for "minimum length" windows: shrink while valid. The moment the window sum drops below S, stop shrinking and resume expanding. This is the opposite of "maximum length" windows where you shrink while invalid.
* Edge case: if the total array sum is less than S, no valid subarray exists -- return 0 or -1 as specified. Also, a single element might satisfy the condition (element >= S), so minimum length could be 1.
* Complexity: O(n) time, O(1) space. Each pointer visits each element at most once, so total operations are at most 2n.
**Follow-up:** What if the array contains negative numbers? Does the sliding window still work?
No. With negative numbers, expanding the window can decrease the sum and shrinking can increase it. The monotonic property breaks, so the pointers might need to move backward, which violates the two-pointer invariant. For arrays with negative numbers, use prefix sums with a sorted data structure: for each position j, find the smallest prefix\[i] where i \< j such that prefix\[j] - prefix\[i] >= S. A balanced BST (multiset) or segment tree can answer this in O(n log n).
**Strong Answer:**
* Two-pointer approach: sort the array, then use converging pointers from both ends. Time: O(n log n) for sort + O(n) for scan = O(n log n). Space: O(1) if sorting in-place (or O(n) for the sorted copy).
* Hashmap approach: single pass, for each element check if (target - element) exists in the hashmap. Time: O(n) average. Space: O(n) for the hashmap.
* Choose two pointers when: you need to find all pairs (not just one), the array is already sorted, you need to solve the problem in O(1) space, or you want to avoid hash collision risks on competitive programming judges.
* Choose hashmap when: you need O(n) time (log factor matters), you must preserve original indices (sorting destroys index information), or the problem has follow-up operations that benefit from the hashmap (e.g., counting pairs, finding the pair closest to target).
* For the classic LeetCode Two Sum that asks for indices: hashmap is the only correct O(n) approach because sorting loses index information. For the Codeforces variant that asks "does such a pair exist": two pointers after sorting is simpler and avoids hash collision issues.
**Follow-up:** How would you extend the two-pointer approach to Three Sum?
Fix one element (iterate i from 0 to n-3), then use two pointers on the remaining subarray to find pairs that sum to (target - nums\[i]). Sort first for O(n log n), outer loop is O(n), inner two-pointer scan is O(n), total O(n^2). Skip duplicate values for the fixed element to avoid duplicate triplets. This is optimal because there can be O(n^2) valid triplets, so any correct algorithm must be at least O(n^2).
**Strong Answer:**
* Maintain a window \[left, right] and a hashmap tracking character frequencies within the window. Expand right, adding each character to the map. When the number of distinct characters exceeds K, shrink from the left: decrement the frequency of s\[left], and if it reaches zero, remove it from the map. Track the maximum (right - left + 1) seen.
* Time complexity proof: the right pointer advances from 0 to n-1, making exactly n steps. The left pointer also advances, but crucially it never moves backward. In total, left advances at most n times (it starts at 0 and can reach at most n-1). Each advance of either pointer involves O(1) hashmap work. Total: O(n) + O(n) = O(n).
* The common mistake: computing the number of distinct characters by scanning the hashmap each time -- this makes the inner work O(alphabet\_size) per step. Instead, maintain a separate counter that increments when a new character is added (frequency goes from 0 to 1) and decrements when a character is removed (frequency goes from 1 to 0). This keeps the distinct count in O(1) per step.
* Window invariant (write this down before coding): "The window \[left, right] always contains at most K distinct characters." When the invariant is violated, shrink until it is restored. Update the answer only when the invariant holds.
**Follow-up:** What if the problem asks for the longest substring with exactly K distinct characters?
Transform to: (longest with at most K distinct) - (longest with at most K-1 distinct). This is the "at most K" trick. Run the sliding window twice, once with limit K and once with limit K-1, and subtract. Alternatively, maintain the window as before but only update the answer when the distinct count equals exactly K. Both approaches are O(n).