Arrays and strings are the foundation of coding interviews — you’ll encounter them in nearly every problem set. This page provides battle-tested C++ templates for the most important patterns: sliding window, two pointers, binary search on answer, prefix sum, hash maps, and string algorithms like KMP and Manacher. Master these and you’ll have the tools to solve a huge fraction of Medium-level problems.

This template covers the fundamental patterns for array and string problems. Sliding window, two pointers, and prefix sum together solve a huge fraction of Medium problems.

Contents

Sliding Window (fixed/variable)

When to use: “longest substring”, “shortest subarray”, “at most k distinct”, or any problem asking for a contiguous subrange that satisfies a constraint.

Sliding Window — Longest Substring Without Repeating 0123 4567 #1 a b c a b c b b expand → window "abc", len = 3 seen: {a, b, c} #2 a b c a b c b b expand → "abca" — 'a' repeats! shrink left to remove duplicate #3 a b c a b c b b shrink → "bca", len = 3 no duplicates, continue expanding #4 a b c a b c b b expand → "abc", len = 3 max length = 3 
// Variable-size window (e.g., longest substring without repeating)
int longestNoRepeat(const string& s){
    vector<int> cnt(256, 0);
    int dup = 0, best = 0;
    for (int l = 0, r = 0; r < (int)s.size(); ++r){
        dup += (++cnt[(unsigned char)s[r]] == 2);
        while (dup > 0){
            dup -= (--cnt[(unsigned char)s[l++]] == 1);
        }
        best = max(best, r - l + 1);
    }
    return best;
}
ID Title Link Solution
3 Longest Substring Without Repeating Characters Link Solution
76 Minimum Window Substring Link -
392 Is Subsequence Link Solution
424 Longest Repeating Character Replacement Link -
616 Add Bold Tag in String Link Solution
681 Next Closest Time Link Solution
713 Subarray Product Less Than K Link Solution
2461 Maximum Sum of Distinct Subarrays With Length K Link Solution

Two Pointers (sorted arrays/strings)

When to use: “pair with target sum in sorted array”, “container with most water”, “valid palindrome”, or when the array is sorted and you can shrink the search space from both ends.

Two Pointers — Find Pair with Target Sum = 9 1 0 2 1 3 2 4 3 5 4 6 5 7 6 left right move → Step 1: left=0, right=6 → 1 + 7 = 8 < 9 → move left Step 2: left=1, right=6 → 2 + 7 = 9 = target ✓ 
bool twoSumSorted(const vector<int>& a, int target){
    int l = 0, r = (int)a.size() - 1;
    while (l < r){
        long long sum = (long long)a[l] + a[r];
        if (sum == target) return true;
        if (sum < target) ++l; else --r;
    }
    return false;
}
ID Title Link Solution
15 3Sum Link -
11 Container With Most Water Link -
125 Valid Palindrome Link -
1768 Merge Strings Alternately Link Solution

Binary Search on Answer (monotonic predicate)

When to use: “minimize the maximum”, “feasibility check”, “minimum speed/capacity”, or when the answer has a monotonic property (if x works, then x+1 also works).

long long binsearch(long long lo, long long hi){ // [lo, hi]
    auto good = [&](long long x){ /* check feasibility */ return true; };
    while (lo < hi){
        long long mid = (lo + hi) >> 1;
        if (good(mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
}
ID Title Link Solution
33 Search in Rotated Sorted Array Link Solution
34 Find First and Last Position of Element in Sorted Array Link -
162 Find Peak Element Link -
875 Koko Eating Bananas Link -
1870 Minimum Speed to Arrive on Time Link Solution

Prefix Sum / Difference Array

When to use: “range sum query”, “subarray sum equals k”, “number of subarrays with sum”, or when you need O(1) range queries after O(n) preprocessing.

vector<int> prefix(const vector<int>& a){
    vector<int> ps(a.size()+1);
    for (int i = 0; i < (int)a.size(); ++i) ps[i+1] = ps[i] + a[i];
    return ps;
}
ID Title Link Solution
303 Range Sum Query - Immutable Link Solution
523 Continuous Subarray Sum Link Solution
560 Subarray Sum Equals K Link -
238 Product of Array Except Self Link -
525 Contiguous Array Link Solution
1177 Can Make Palindrome from Substring Link Solution
370 Range Addition Link -
134 Gas Station Link Solution
2270 Number of Ways to Split Array Link Solution

Hash Map Frequencies

When to use: “two sum”, “group anagrams”, “frequency count”, “contains duplicate”, or any problem where you need O(1) lookups by value.

unordered_map<int,int> freq;
for (int x: nums) ++freq[x];
ID Title Link Solution
1 Two Sum Link -
49 Group Anagrams Link -
242 Valid Anagram Link Solution
217 Contains Duplicate Link Solution
219 Contains Duplicate II Link Solution
383 Ransom Note Link Solution
981 Time Based Key-Value Store Link -
359 Logger Rate Limiter Link -
2365 Task Scheduler II Link Solution
2342 Max Sum of a Pair With Equal Sum of Digits Link Solution

When to use: “find pattern in string”, “shortest palindrome by prepending”, “repeated string match”, or when you need O(n + m) exact pattern matching.

KMP is a pattern matching algorithm that finds occurrences of a pattern string P within a text string T efficiently — without re-checking characters that are already known to match.

While a naive substring search checks character-by-character and backtracks when a mismatch occurs (worst case O(n * m)), KMP preprocesses the pattern to know how far it can safely skip ahead when mismatches happen.

It does this using a “prefix function” (also called LPS — longest prefix which is also suffix).

Steps

Preprocess the pattern to build the lps[] array.

  • lps[i] = the length of the longest proper prefix of the substring P[0..i] which is also a suffix of this substring.

  • Proper prefix = prefix ≠ the string itself.

Use the LPS array during the search

  • When mismatch occurs, instead of resetting j = 0, we move j back to lps[j-1].
vector<int> kmpPi(const string& s) {
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}
ID Title Link Solution
28 Find the Index of the First Occurrence in a String Link -
214 Shortest Palindrome Link -
686 Repeated String Match Link Solution

Manacher (Longest Palindromic Substring, O(n))

When to use: “longest palindromic substring” when O(n) time is required, or counting all palindromic substrings efficiently.

string manacher(const string& s) {
    string t = "|";
    for (char c : s) { t.push_back(c); t.push_back('|'); }
    int n = t.size();
    vector<int> p(n);
    int c = 0, r = 0, best = 0, center = 0;
    for (int i = 0; i < n; i++) {
        int mir = 2 * c - i;
        if (i < r) p[i] = min(r - i, p[mir]);
        while (i - 1 - p[i] >= 0 && i + 1 + p[i] < n && t[i - 1 - p[i]] == t[i + 1 + p[i]]) p[i]++;
        if (i + p[i] > r) { c = i; r = i + p[i]; }
        if (p[i] > best) { best = p[i]; center = i; }
    }
    int start = (center - best) / 2;
    return s.substr(start, best);
}
ID Title Link Solution
5 Longest Palindromic Substring Link -

Z-Algorithm (Pattern occurrences)

When to use: “find all pattern occurrences”, “longest happy prefix”, or as an alternative to KMP for pattern matching.

vector<int> zfunc(const string& s) {
    int n = s.size();
    vector<int> z(n);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i <= r) z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; }
    }
    return z;
}
ID Title Link Solution
1392 Longest Happy Prefix Link -

String Rolling Hash (Rabin–Karp)

When to use: “repeated DNA sequences”, “longest duplicate substring”, or when you need to compare many substrings in O(1) each after O(n) preprocessing.

struct RH {
    static const long long B = 911382323, M = 972663749;
    vector<long long> p, h;
    RH(const string& s) {
        int n = s.size();
        p.assign(n + 1, 1);
        h.assign(n + 1, 0);
        for (int i = 0; i < n; i++) {
            p[i + 1] = p[i] * B % M;
            h[i + 1] = (h[i] * B + s[i]) % M;
        }
    }
    long long get(int l, int r) {  // [l, r)
        return (h[r] - h[l] * p[r - l] % M + M) % M;
    }
};
ID Title Link Solution
187 Repeated DNA Sequences Link -
686 Repeated String Match Link Solution
1044 Longest Duplicate Substring Link -

Summary

Pattern Signal Phrases Time
Sliding Window “substring”, “subarray”, “at most k” O(n)
Two Pointers “sorted”, “pair”, “container” O(n)
Binary Search on Answer “minimize max”, “feasibility” O(n log range)
Prefix Sum “range sum”, “subarray sum” O(n) build, O(1) query
Hash Map “frequency”, “group”, “two sum” O(n)
KMP “pattern in string” O(n + m)

More templates