Two Pointers / Sliding Window

Concept

Two pointers uses two indices that move through a sorted array or sequence to solve problems in O(n) instead of O(n^2). Common variants: opposite ends (converging inward) for pair sum, and same direction (sliding window) for subarray problems. The key insight is that both pointers only move forward, giving linear time.

When to Use

• ▸Finding a pair with a given sum in a sorted array
• ▸Longest/shortest subarray with a condition (sliding window)
• ▸Removing duplicates or merging sorted arrays
• ▸Container with most water, trapping rain water
• ▸Any problem on sorted data where brute force checks all pairs

Intuition

For pair sum: start with pointers at both ends of a sorted array. If the sum is too small, move the left pointer right (increase sum). If too large, move the right pointer left (decrease sum). Each step eliminates many pairs at once. For sliding window: expand the right pointer to include more elements, shrink the left pointer when the window violates the condition. Both pointers only move forward, so total work is O(n).

Complexity

Template Code

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    // --- Two Pointers: Pair Sum in Sorted Array ---
    int n, target;
    cin >> n >> target;

    vector<int> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];

    int l = 0, r = n-1;
    while(l < r){
        int sum = v[l] + v[r];
        if(sum == target){
            cout << l+1 << " " << r+1 << "\n";
            return 0;
        }
        else if(sum < target) l++;
        else r--;
    }

    cout << "IMPOSSIBLE\n";

    return 0;
}

// --- Sliding Window: Max Sum Subarray of Size K ---
// int n, k;
// cin >> n >> k;
//
// vector<int> v(n);
// for(int i = 0; i < n; i++) cin >> v[i];
//
// long long sum = 0;
// for(int i = 0; i < k; i++) sum += v[i];
//
// long long mx = sum;
// for(int i = k; i < n; i++){
//     sum += v[i] - v[i-k];
//     mx = max(mx, sum);
// }
//
// cout << mx << "\n";

// Sample Input (Pair Sum):
// 5 8
// 1 2 3 5 8
//
// Sample Output:
// 3 4