Two Pointers & Sliding Window

Merge Two Sorted Arrays

Given two sorted arrays a and b, merge them into one sorted array.

Two pointers i and j — always pick the smaller front element:

int i = 0, j = 0, k = 0;
while (i < a.size() || j < b.size()) {
    if (j == b.size() || (i < a.size() && a[i] < b[j])) {
        c[k] = a[i++];
    } else {
        c[k] = b[j++];
    }
    k++;
}

Runs in O(n + m) — optimal since we must look at every element.

Problems using this

• A. Merging Arrays

Count Smaller / Number of Equal

Given sorted array a and queries from sorted array b, count how many elements in a are < b[j] (or ==).

Move pointer i on a while a[i] < b[j], then result[j] = i:

ll i = 0, j = 0;
while (i < n || j < m) {
    if (j == m || (i < n && a[i] < b[j])) {
        i++;
    } else {
        result[j++] = i;   // i elements in a are < b[j]
    }
}

For “number of equal”, advance i while a[i] <= b[j] and count matches.

Problems using this

• B. Number of Smaller
• C. Number of Equal

Sliding Window — Maximum Length (sum ≤ X)

Find the longest subarray with sum ≤ x.

Expand r every iteration. When sum exceeds x, shrink from l:

int l = 0;
ll sum = 0, final = 0;
for (int r = 0; r < n; r++) {
    sum += arr[r];
    while (sum > x) {
        sum -= arr[l];
        l++;
    }
    final = max(final, r - l + 1);
}

Each element enters and leaves the window at most once → O(n).

Problems using this

• A. Segment with Small Sum

Sliding Window — Minimum Length (sum ≥ X)

Same template, opposite condition — shrink while sum is valid (≥ x), track minimum length:

for (int r = 0; r < n; r++) {
    sum += arr[r];
    while (sum >= x) {
        final = min(final, r - l + 1);
        sum -= arr[l];
        l++;
    }
}

Problems using this

• B. Segment with Big Sum

Count Subarrays (sum ≤ X)

Instead of tracking max length, count all valid subarrays ending at r.

When window [l, r] is valid, every subarray [l', r] for l <= l' <= r is also valid. That’s (r - l + 1) subarrays:

ll result = 0;
for (int r = 0; r < n; r++) {
    sum += arr[r];
    while (sum > s) {
        sum -= arr[l];
        l++;
    }
    result += r - l + 1;
}

Total subarrays counted: O(n²) in worst case, but the two-pointer scan itself is O(n).

Problems using this

• C. Number of Segments with Small Sum
• D. Number of Segments with Big Sum

Sliding Window — At Most K Distinct

Count subarrays with at most k distinct elements.

Use a frequency array. Track cnt = number of distinct elements in window:

vi freq(100005, 0);
ll cnt = 0, l = 0, result = 0;
for (ll r = 0; r < n; r++) {
    if (freq[arr[r]] == 0) cnt++;
    freq[arr[r]]++;
    while (cnt > k) {
        freq[arr[l]]--;
        if (freq[arr[l]] == 0) cnt--;
        l++;
    }
    result += (r - l + 1);
}

Same “add all valid subarrays ending at r” trick.

Problems using this

• E. Segments with Small Set

Sliding Window — Small Spread (max - min ≤ k)

Need min and max inside the window quickly. Use two monotonic stacks (one tracking min, one tracking max):

struct stack {
    vi s, smin = {LLONG_MAX}, smax = {LLONG_MIN};
    void push(ll x) {
        s.push_back(x);
        smin.push_back(min(smin.back(), x));
        smax.push_back(max(smax.back(), x));
    }
    ll pop() { /* pop from s, smin, smax */ return s.back(); }
    ll min() { return smin.back(); }
    ll max() { return smax.back(); }
};

Use two stacks (s1, s2) for a queue — classic “two-stack queue” trick.

Window is valid when max - min <= k. Shrink from left while invalid:

for (int r = 0; r < n; r++) {
    add(arr[r]);
    while (!good()) {   // max - min > k
        remove();
        l++;
    }
    result += r - l + 1;
}

Problems using this

• F. Segments with Small Spread

General Sliding Window Template

Most sliding window problems follow this pattern:

int l = 0;
for (int r = 0; r < n; r++) {
    // add arr[r] to window state

    while (window_is_invalid) {
        // remove arr[l] from window state
        l++;
    }

    // update answer using current window [l, r]
}

The trick is defining window_is_invalid and what “window state” means (sum, count, distinct elements, min/max, etc.).