SyntaxPilot
Courses/C++ Coding Questions/Lesson 15
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C++ Coding Questions · Lesson 15 of 30

Two pointers and sliding window

pair with a given sum in a sorted vectormax sum of a window of size klongest substring without repeating characters

These are the notes for C++ Coding Questions, episode 15, placement practice for people who finished the SyntaxPilot C++ course. Two ideas that turn O(n²) into O(n), usually with no extra memory: two pointers (a pair with a given sum in a sorted vector, and why while (i <= j) uses one element twice) and the sliding window, fixed (the best sum of k numbers in a row, and why best = 0 is wrong) and variable (the longest substring without repeating characters, and a left end that must never move backwards).

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was compiled with g++ -Wall -O2 -std=c++17 main.cpp -o main (g++ 13.3, Linux x86-64), the SyntaxPilot compiler's C++ command with warnings on, and every output below is real. The compiler stops a program that runs too long (Time Limit Exceeded, TLE), like an online judge.

Real-life pictures

In real life In C++
Two friends buying two gifts for exactly ₹10 from a price-sorted shelf, one at each end two pointers i (left) and j (right) on a sorted vector
Too little: the cheap-end friend steps right; too much: the costly-end friend steps left sum < target → i++, sum > target → j--
They can't both take the same gift while (i < j)
A shop's best 3 days in a row: add the new day, drop the oldest a fixed sliding window: sum += a[i]; sum -= a[i - k];
A bad month: the best stretch is the smallest loss, not 0 start best at LLONG_MIN
A caterpillar on a string of beads: the head eats the next bead; on a repeated colour the tail jumps past the old bead, never backwards a variable sliding window: left = max(left, last[c] + 1)

Q1: Pair with a given sum in a sorted vector

Problem. Given n sorted numbers and a target, print two different elements (different positions) that add up to the target, or no pair.

Input Output
1 3 5 6 9, target 10 1 9
1 3 5 8, target 10 no pair (5 + 5 would use one element twice)

Think out loud. Edge cases: no pair, n = 1. Big test: 500,000 numbers with no pair (the test block, when n is 0, builds 0 2 4 ... and target 1).

The obvious attempt: every pair

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    long long target;
    cin >> n >> target;
    vector<long long> v(n);
    for (auto& x : v) cin >> x;
    if (n == 0) {                        // test: 500,000 even numbers, odd target
        n = 500000;
        v.resize(n);
        for (int i = 0; i < n; i++) v[i] = 2 * i;
        target = 1;
    }
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (v[i] + v[j] == target) {
                cout << v[i] << " " << v[j] << "\n";
                return 0;
            }
    cout << "no pair\n";
    return 0;
}
1 9

The big test (0 0) checks all ≈ 1.25 × 10¹¹ pairs and runs for well over 25 seconds: Time Limit Exceeded. It never uses the fact that the numbers are sorted.

Why two pointers are allowed to skip

Put i at the start and j at the end.

  • v[i] + v[j] < target: even the biggest partner is too small for v[i], so v[i] is in no pair. Throw it away: i++.
  • v[i] + v[j] > target: even the smallest partner is too big for v[j]. Throw it away: j--.

Each step throws one element away for good: at most n steps.

Attempt: two pointers with while (i <= j)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    long long target;
    cin >> n >> target;
    vector<long long> v(n);
    for (auto& x : v) cin >> x;
    if (n == 0) {                        // test: 500,000 even numbers, odd target
        n = 500000;
        v.resize(n);
        for (int i = 0; i < n; i++) v[i] = 2 * i;
        target = 1;
    }
    int i = 0, j = n - 1;
    while (i <= j) {
        long long sum = v[i] + v[j];
        if (sum == target) {
            cout << v[i] << " " << v[j] << "\n";
            return 0;
        }
        if (sum < target) i++;           // need more: move the left end right
        else j--;                        // too much: move the right end left
    }
    cout << "no pair\n";
    return 0;
}

1 3 5 6 9 (10), then 1 3 5 8 (10):

1 9

5 5

Why 5 5. Trace: 1+8 = 9 → i++; 3+8 = 11 → j--; 3+5 = 8 → i++; now i = j = 2, and 5+5 = 10. When i == j both pointers are on the same element.

Fix: while (i < j)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    long long target;
    cin >> n >> target;
    vector<long long> v(n);
    for (auto& x : v) cin >> x;
    if (n == 0) {                        // test: 500,000 even numbers, odd target
        n = 500000;
        v.resize(n);
        for (int i = 0; i < n; i++) v[i] = 2 * i;
        target = 1;
    }
    int i = 0, j = n - 1;
    while (i < j) {
        long long sum = v[i] + v[j];
        if (sum == target) {
            cout << v[i] << " " << v[j] << "\n";
            return 0;
        }
        if (sum < target) i++;           // need more: move the left end right
        else j--;                        // too much: move the right end left
    }
    cout << "no pair\n";
    return 0;
}

1 3 5 8 (10), the big test, 1 3 5 6 9 (10), a single 2 (4), and 1 3 5 8 (4):

no pair

no pair

1 9

no pair

1 3

O(n) time, O(1) extra space. Needs sorted input; for unsorted input use the hash map of episode 10 (O(n) average, O(n) space) or sort first (O(n log n)).

Q2: Maximum sum of a window of size k

Problem. Given n numbers (negatives allowed) and k (1 ≤ k ≤ n), print the largest sum of k numbers in a row.

Input Output
2 1 5 1 3 2, k = 3 9 (5 1 3)
-3 -1 -2 -5 -4, k = 2 -3 (-1 -2)

Think out loud. Edge cases: k = n, every number negative. Big test: 1,000,000 numbers with k = 500,000 (the test block, when n is 0, builds 0 1 2 ... 99 0 1 ...).

The obvious attempt: add up every window again

#include <iostream>
#include <vector>
using namespace std;

long long bestWindow(const vector<int>& a, int k) {
    long long best = 0;
    for (int i = 0; i + k <= (int)a.size(); i++) {
        long long sum = 0;
        for (int j = i; j < i + k; j++) sum += a[j];
        best = max(best, sum);
    }
    return best;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    if (n == 0) {                        // test: 1,000,000 numbers, k = 500,000
        n = 1000000; k = 500000;
        a.resize(n);
        for (int i = 0; i < n; i++) a[i] = i % 100;
    }
    cout << bestWindow(a, k) << "\n";
    return 0;
}
9

The big test does (n − k + 1) · k ≈ 2.5 × 10¹¹ additions: Time Limit Exceeded (still running after 30 seconds on our machine).

Why. Neighbouring windows share k − 1 numbers; only one comes in and one leaves:

[2 1 5] 1 3 2   = 8
2 [1 5 1] 3 2   = 8 + 1 - 2 = 7
2 1 [5 1 3] 2   = 7 + 3 - 1 = 9
2 1 5 [1 3 2]   = 9 + 2 - 5 = 6

Attempt: the sliding window, with best = 0

#include <iostream>
#include <vector>
using namespace std;

long long bestWindow(const vector<int>& a, int k) {
    long long sum = 0, best = 0;
    for (int i = 0; i < (int)a.size(); i++) {
        sum += a[i];                     // the new number comes in
        if (i >= k) sum -= a[i - k];     // the oldest one leaves
        if (i >= k - 1) best = max(best, sum);
    }
    return best;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    if (n == 0) {                        // test: 1,000,000 numbers, k = 500,000
        n = 1000000; k = 500000;
        a.resize(n);
        for (int i = 0; i < n; i++) a[i] = i % 100;
    }
    cout << bestWindow(a, k) << "\n";
    return 0;
}

2 1 5 1 3 2 (k = 3), the big test, then -3 -1 -2 -5 -4 (k = 2):

9

24750000

0

Why 0. best = 0 is a fake window with sum 0. When every real window is negative, the fake one wins. The brute force has the same line; it just never got a negative test.

Fix: best = LLONG_MIN

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

long long bestWindow(const vector<int>& a, int k) {
    long long sum = 0, best = LLONG_MIN;
    for (int i = 0; i < (int)a.size(); i++) {
        sum += a[i];                     // the new number comes in
        if (i >= k) sum -= a[i - k];     // the oldest one leaves
        if (i >= k - 1) best = max(best, sum);
    }
    return best;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    if (n == 0) {                        // test: 1,000,000 numbers, k = 500,000
        n = 1000000; k = 500000;
        a.resize(n);
        for (int i = 0; i < n; i++) a[i] = i % 100;
    }
    cout << bestWindow(a, k) << "\n";
    return 0;
}

-3 -1 -2 -5 -4 (k = 2), 2 1 5 1 3 2 (k = 3), the big test, and 4 -1 2 (k = 3, the whole vector):

-3

9

24750000

5

O(n) time: each number enters once and leaves once. O(1) extra space. (Equivalent: start with best = the sum of the first window.) LLONG_MIN comes from <climits>; numeric_limits<long long>::min() from <limits> is the same value.

Q3: Longest substring without repeating characters

Problem. For each word, print the length of the longest substring (continuous) with all characters different.

Input Output
abcabcbb 3 (abc)
bbbbb 1
pwwkew 3 (wke; pwke isn't continuous)
dvdf 3 (vdf)
abba 2 (ab, ba)

The obvious attempt: clear the window on a repeat

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int longestUnique(const string& s) {
    unordered_set<char> window;
    int best = 0;
    for (char c : s) {
        if (window.count(c)) window.clear();   // a repeat: start again
        window.insert(c);
        best = max(best, (int)window.size());
    }
    return best;
}

int main() {
    string s;
    while (cin >> s) cout << s << ": " << longestUnique(s) << "\n";
    return 0;
}
abcabcbb: 3
bbbbb: 1
pwwkew: 3
dvdf: 2

Why 2 for dvdf. The window was d v; the second d cleared everything, leaving d, then d f. But v was fine: only the old d had to go. Move the left end to just past the old copy, which needs the latest index of every character.

Attempt: left = last[c] + 1

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int longestUnique(const string& s) {
    unordered_map<char, int> last;       // character -> latest index
    int left = 0, best = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        char c = s[i];
        if (last.count(c)) left = last[c] + 1;
        last[c] = i;
        best = max(best, i - left + 1);
    }
    return best;
}

int main() {
    string s;
    while (cin >> s) cout << s << ": " << longestUnique(s) << "\n";
    return 0;
}
abcabcbb: 3
bbbbb: 1
pwwkew: 3
dvdf: 3
abba: 3

Why 3 for abba.

i c last[c] before left window
0 a — 0 a
1 b — 0 ab
2 b 1 2 b
3 a 0 1 (backwards!) bba: length 3, with two b's

The old a at index 0 was already outside the window; it must not move left back.

Fix: left = max(left, last[c] + 1)

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int longestUnique(const string& s) {
    unordered_map<char, int> last;       // character -> latest index
    int left = 0, best = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        char c = s[i];
        if (last.count(c)) left = max(left, last[c] + 1);
        last[c] = i;
        best = max(best, i - left + 1);
    }
    return best;
}

int main() {
    string s;
    while (cin >> s) cout << s << ": " << longestUnique(s) << "\n";
    return 0;
}
abcabcbb: 3
bbbbb: 1
pwwkew: 3
dvdf: 3
abba: 2
x: 1
tmmzuxt: 5

O(n) time: i and left each move forward at most n times. O(alphabet) space: at most 256 different char values. (An int last[256] filled with −1 is a faster replacement for the map.)

Why two pointers and windows are fast

  • Two pointers: every step proves one element is in no answer and throws it away.
  • Fixed window: reuse the previous sum: one number in, one out.
  • Variable window: grow on the right; shrink from the left only as much as needed.
  • In every case both ends only move forward: at most 2n moves, O(n).
Pattern Use when Example
Two pointers from both ends sorted data, pairs pair sum, container with most water
Fixed window of size k "k in a row" best k days, average of every k
Variable window "longest/shortest stretch such that ..." no repeats, shortest sum ≥ target

Complexity summary

Program Time Extra space
pair sum, every pair O(n²): TLE for 500,000 O(1)
pair sum, two pointers (sorted) O(n) O(1)
best window, re-add each window O(n · k): TLE O(1)
best window, sliding O(n) O(1)
longest unique substring, window + last index O(n) O(alphabet)

Common mistakes (and the real results)

Mistake What you see Why Fix
every pair on big input Time Limit Exceeded O(n²) two pointers on sorted data
while (i <= j) 5 5 for 1 3 5 8, target 10 i == j is one element while (i < j)
two pointers on unsorted data no pair when a pair exists the skip rule needs sorted order sort first, or a hash map
re-adding every window Time Limit Exceeded O(n · k) add the new, subtract the oldest
long long best = 0; 0 instead of -3 a fake window wins best = LLONG_MIN or the first window
comparing before the window is full a "best" of fewer than k numbers i < k - 1 only update when i >= k - 1
clearing the window on a repeat dvdf: 2 good characters thrown away left = last[c] + 1
left = last[c] + 1 alone abba: 3 left moves backwards left = max(left, last[c] + 1)

Your turn: the shortest stretch reaching a target (solution)

Problem. Positive numbers and a target: the length of the shortest subarray with sum ≥ target (0 if none). 2 3 1 2 4 3, target 7 → 2 (4 3).

Idea. A variable window. Grow it on the right; while the sum is at least the target, record the length and shrink from the left. All numbers are positive, so shrinking always lowers the sum: each index enters and leaves once.

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int n;
    long long target;
    while (cin >> n >> target) {
        vector<long long> a(n);
        for (auto& x : a) cin >> x;
        long long sum = 0;
        int left = 0, best = INT_MAX;
        for (int right = 0; right < n; right++) {
            sum += a[right];                     // grow on the right
            while (sum >= target) {              // good enough: try shorter
                best = min(best, right - left + 1);
                sum -= a[left++];                // shrink from the left
            }
        }
        cout << (best == INT_MAX ? 0 : best) << "\n";
    }
    return 0;
}

2 3 1 2 4 3 (7), 1 4 4 (4), 1 1 1 1 (10):

2
1
0

O(n) time, O(1) extra space.

Practice questions (with solutions)

1. Container with most water. Heights of vertical lines; pick two lines so that min(h[i], h[j]) × (j − i) is the largest.

Solution

Two pointers from both ends; move the shorter line inward (moving the taller one can never help: the width shrinks and the height is still limited by the shorter line).

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> h(n);
    for (auto& x : h) cin >> x;
    int i = 0, j = n - 1;
    long long best = 0;
    while (i < j) {
        best = max(best, min(h[i], h[j]) * (j - i));
        if (h[i] < h[j]) i++;
        else j--;
    }
    cout << best << "\n";
    return 0;
}

1 8 6 2 5 4 8 3 7:

49

2. Remove duplicates from a sorted vector in place (two pointers).

Solution

w is where the next new value is written; r reads every element.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int& x : v) cin >> x;
    int w = 0;
    for (int r = 0; r < n; r++)
        if (r == 0 || v[r] != v[w - 1]) v[w++] = v[r];
    v.resize(w);
    for (int x : v) cout << x << " ";
    cout << "| " << w << " unique\n";
    return 0;
}
1 2 3 5 8 | 5 unique

3. Count the windows of size k whose average is at least x.

Solution

Average ≥ x ⇔ sum ≥ k · x (no division, no floating point).

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    long long x;
    cin >> n >> k >> x;
    vector<long long> a(n);
    for (auto& v : a) cin >> v;
    long long sum = 0;
    int count = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
        if (i >= k) sum -= a[i - k];
        if (i >= k - 1 && sum >= k * x) count++;
    }
    cout << count << "\n";
    return 0;
}

2 2 2 2 5 5 5 8 with k = 3, x = 4:

3

Mini project: the best 7-day streak of a step counter

A month of daily step counts: print the best 7-day total, which days it covers, and the best 7-day average. A fixed window that also remembers where the best window starts.

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    vector<long long> steps;
    long long s;
    while (cin >> s) steps.push_back(s);
    const int k = 7;
    if ((int)steps.size() < k) { cout << "need at least 7 days\n"; return 0; }
    long long sum = 0, best = LLONG_MIN;
    int bestStart = 0;
    for (int i = 0; i < (int)steps.size(); i++) {
        sum += steps[i];
        if (i >= k) sum -= steps[i - k];
        if (i >= k - 1 && sum > best) { best = sum; bestStart = i - k + 1; }
    }
    cout << "Best 7 days: day " << bestStart + 1 << " to day " << bestStart + k << "\n";
    cout << "Total: " << best << " steps, average " << best / k << " a day\n";
    return 0;
}

Fourteen days of steps:

Best 7 days: day 4 to day 10
Total: 56600 steps, average 8085 a day

Quick quiz

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 4, 7, 11, 15};
    int i = 0, j = 5, steps = 0;
    while (i < j) {
        steps++;
        int s = v[i] + v[j];
        if (s == 15) break;
        if (s < 15) i++; else j--;
    }
    cout << v[i] << " " << v[j] << " " << steps << "\n";
    return 0;
}

(A) 4 11 4 (B) 4 11 3 (C) 1 15 1 (D) 7 7 5

Answer

(A) 4 11 4. 1+15 = 16 (too big, j--), 1+11 = 12 (too small, i++), 2+11 = 13 (i++), 4+11 = 15: found in 4 steps.

4 11 4

Interview questions

  1. Why do two pointers need sorted input for pair sum? The skip rule ("v[i] + the biggest is too small, so v[i] is useless") relies on order.
  2. Two pointers on unsorted input? Sort first (O(n log n)), or use a hash map of seen values (O(n) average, O(n) space).
  3. while (i < j) or while (i <= j)? For a pair of different elements, i < j: when i == j there is only one element.
  4. What is a sliding window? A range [left, right] over the array that moves forward, keeping some summary (sum, counts, last positions) up to date as elements enter and leave.
  5. Fixed vs variable window? Fixed: the size k never changes (one in, one out). Variable: grows and shrinks to keep a condition true ("no repeats", "sum < target").
  6. Why is the variable window O(n) even with an inner while? left only moves forward, at most n times over the whole run, so the total work is at most 2n.
  7. Why does the "shortest sum ≥ target" window need positive numbers? With negatives, shrinking can increase the sum, so the window logic breaks; use prefix sums with a monotonic deque instead.
  8. Why left = max(left, last[c] + 1)? The old copy of c may already be left of the window; left must never move backwards.
  9. What should best start at for a maximum? The smallest possible value (LLONG_MIN) or the first real candidate, never 0 when values can be negative.

Glossary

Term Meaning Example
Two pointers Two indexes that move through the data, often from both ends i = 0, j = n - 1
Sorted vector Elements in non-decreasing order 1 3 5 6 9
Pair sum Two different elements adding up to a target 1 + 9 = 10
Sliding window A range [left, right] that moves forward through the data [5 1 3] in 2 1 5 1 3 2
Fixed window A window of constant size k the best 3 days
Variable window A window that grows and shrinks to keep a condition no repeated characters
Running sum A sum kept up to date as elements enter and leave sum += a[i]; sum -= a[i - k];
LLONG_MIN The smallest long long (from <climits>) best = LLONG_MIN
Substring A continuous part of a string wke in pwwkew
last[c] The latest index where character c appeared last['a'] = 3
Amortised O(n) Total work O(n) even if one step does more left moves at most n times
Off-by-one error A condition wrong by exactly one i <= j instead of i < j
Time Limit Exceeded (TLE) The judge stopped a program that ran too long O(n²) on 500,000 numbers

Summary

  • Pair sum (sorted): i from the left, j from the right; too small → i++, too big → j--; while (i < j). O(n), O(1).
  • Best window of size k: one running sum, add a[i], subtract a[i - k]; start best at LLONG_MIN. O(n), O(1).
  • Longest substring without repeats: last[c] = latest index; left = max(left, last[c] + 1); length i - left + 1. O(n).
  • Both ends only move forward: that's why these are O(n).

Next episode: Stack questions: balanced brackets (and the empty-stack trap), the next greater element with a monotonic stack, and evaluating a postfix expression.