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

Use When

Sorted array + finding pairs
Subarray with sum/length constraints
Palindrome checking
Merging sorted arrays
Removing duplicates in-place

Don't Use When

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.

// Template: Two Sum in Sorted Array
pair<int, int> twoSumSorted(vector<int>& 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.

// Template: Remove Duplicates from Sorted Array
int removeDuplicates(vector<int>& 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.

// Template: Smallest Subarray with Sum >= Target
int minSubarrayLen(int target, vector<int>& 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”

// Maximum sum of subarray of size K
int maxSumSubarray(vector<int>& 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”

// 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<char, int> 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.

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> 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.

int maxArea(vector<int>& 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

// 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:

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
Maximum Subarray	Sliding window	CF 1343B

Intermediate (1100-1400)

Problem	Pattern	Link
Segment with Small Sum	Sliding window	CF 279B
Books	Two pointers	CF 279B
Vasya and String	Sliding window + counting	CF 676C

Advanced (1400-1700)

Problem	Pattern	Link
Playlist	Sliding window + set	CF 1296E
K-Good Segment	Binary search + two pointers	CF 616D
String Transformation	Two pointers	CF 946D

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

Monotonic Property

Two pointers work when moving in one direction doesn’t require backtracking.

Shrink vs Expand

For minimum → shrink while valid. For maximum → shrink while invalid.

Sort First

Many two-pointer problems require sorted input. Don’t forget to sort.

Track State

Use hashmap/set to track window contents when needed.

Next Up

Chapter 6: Binary Search

Master the art of binary search—not just on arrays, but on the answer itself.

Interview Deep-Dive

Given an array of positive integers and a target sum S, find the length of the shortest subarray with sum >= S. What is your approach, complexity, and why does the sliding window technique work here?

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).

Compare the two-pointer technique with the hashmap-based approach for the Two Sum problem. When would you choose each?

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).

Find the longest substring with at most K distinct characters. Walk through the sliding window approach and prove its time complexity.

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).

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

Two Pointers & Sliding Window

Two Pointers & Sliding Window

The Mental Model

When to Use Two Pointers

Use When

Don't Use When

The Two Pointer Variants

Variant 1: Opposite Ends (Converging)

Variant 2: Same Direction (Fast & Slow)

Variant 3: Sliding Window

Pattern Recognition: Sliding Window Types

Fixed-Size Window

Variable-Size Window

The “When to Shrink” Framework

Classic Problems & Solutions

Three Sum (CF Pattern)

Container With Most Water

Common Mistakes

Practice Problems

Beginner (800-1100)

Intermediate (1100-1400)

Advanced (1400-1700)

Decision Flowchart

Key Takeaways

Monotonic Property

Shrink vs Expand

Sort First

Track State

Next Up

Chapter 6: Binary Search

Interview Deep-Dive

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

Documentation Index

​Two Pointers & Sliding Window

​The Mental Model

​When to Use Two Pointers

Use When

Don't Use When

​The Two Pointer Variants

​Variant 1: Opposite Ends (Converging)

​Variant 2: Same Direction (Fast & Slow)

​Variant 3: Sliding Window

​Pattern Recognition: Sliding Window Types

​Fixed-Size Window

​Variable-Size Window

​The “When to Shrink” Framework

​Classic Problems & Solutions

​Three Sum (CF Pattern)

​Container With Most Water

​Common Mistakes

​Practice Problems

​Beginner (800-1100)

​Intermediate (1100-1400)

​Advanced (1400-1700)

​Decision Flowchart

​Key Takeaways

Monotonic Property

Shrink vs Expand

Sort First

Track State

​Next Up

Chapter 6: Binary Search

​Interview Deep-Dive

Two Pointers & Sliding Window

The Mental Model

When to Use Two Pointers

The Two Pointer Variants

Variant 1: Opposite Ends (Converging)

Variant 2: Same Direction (Fast & Slow)

Variant 3: Sliding Window

Pattern Recognition: Sliding Window Types

Fixed-Size Window

Variable-Size Window

The “When to Shrink” Framework

Classic Problems & Solutions

Three Sum (CF Pattern)

Container With Most Water

Common Mistakes

Practice Problems

Beginner (800-1100)

Intermediate (1100-1400)

Advanced (1400-1700)

Decision Flowchart

Key Takeaways

Next Up

Interview Deep-Dive