Algorithm Patterns for Technical Interviews

1. Sliding Window / Two Pointers

1.1 When to Use

Contiguous segment with some property (sum/length/unique chars)
Array has non-negative values → shrinking window works with sums/frequencies

1.2 Classic Questions (Recognition Phrases)

"Longest substring without repeating characters" (distinct elements)
"Minimum window substring" (cover requirement)
"Max consecutive 1s with at most k flips" (≤k constraint)
"Smallest subarray with sum ≥ S" (positives)
"Group all 1s in circular array" (fixed-length window)

1.3 Templates

1. Fixed-Length Window

int bestFixedWindow(const vector<int>& a, int W) {
    int n = a.size();
    int cur = 0;
    for (int i = 0; i < W; ++i) cur += a[i];
    int best = cur;
    for (int i = W; i < n; ++i) {
        cur += a[i] - a[i - W];
        best = max(best, cur);
    }
    return best;
}

2. Variable-Length, At Most K Distinct

int atMostKDistinct(const vector<int>& a, int K) {
    unordered_map<int,int> freq; freq.reserve(a.size()*2);
    int L = 0, distinct = 0, best = 0;
    for (int R = 0; R < (int)a.size(); ++R) {
        if (++freq[a[R]] == 1) ++distinct;
        while (distinct > K) {
            if (--freq[a[L]] == 0) --distinct;
            ++L;
        }
        best = max(best, R - L + 1);
    }
    return best;
}

3. Smallest Subarray with Sum ≥ S (Positives Only)

int minLenSumAtLeast(const vector<int>& a, int S) {
    int n = a.size(), L = 0, cur = 0, best = INT_MAX;
    for (int R = 0; R < n; ++R) {
        cur += a[R];
        while (cur >= S) {
            best = min(best, R - L + 1);
            cur -= a[L++];
        }
    }
    return best==INT_MAX? -1 : best;
}

Talk Track: "Maintain an invariant inside the window; grow R to satisfy; shrink L to optimize. Each index enters/leaves once → O(n)."

Pitfalls: Duplicates bookkeeping; forgetting unordered_map::reserve; using this when values can be negative (breaks sum logic).

2. Prefix Sums & Difference Arrays

2.1 When to Use

Subarray sums, count of subarrays with target sum/divisibility, range updates, 2D sums

2.2 Classic Questions

"Count subarrays with sum = k" (allow negatives)
"Subarray sums divisible by k"
"Range add updates, then read final array" (difference array)
"2D matrix sum queries"

2.3 Key Idea

pref[i] = sum of a[0..i-1]. Subarray sum a[l..r] = pref[r+1]-pref[l].

2.4 Count Subarrays with Sum = K

long long countSubarraysSumK(const vector<int>& a, int k) {
    long long ans = 0, pref = 0;
    unordered_map<long long, long long> cnt; cnt.reserve(a.size()*2);
    cnt[0] = 1; // empty prefix
    for (int x : a) {
        pref += x;
        if (auto it = cnt.find(pref - k); it != cnt.end()) ans += it->second;
        ++cnt[pref];
    }
    return ans;
}

2.5 Difference Array for Range Adds

For add +v to [L, R]: diff[L]+=v; diff[R+1]-=v; then prefix once.

3. Monotonic Deque (Sliding Window Min/Max)

3.1 When to Use

"Sliding window maximum/minimum" in O(n)
"Shortest subarray with sum ≥ K" (advanced with prefix sums)

3.2 Sliding Window Maximum

vector<int> maxSlidingWindow(const vector<int>& a, int W) {
    deque<int> dq; // stores indices, a[dq] decreasing
    vector<int> ans;
    for (int i = 0; i < (int)a.size(); ++i) {
        while (!dq.empty() && dq.front() <= i - W) dq.pop_front();
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= W - 1) ans.push_back(a[dq.front()]);
    }
    return ans;
}

Invariant: Indices in deque are in window and values strictly decreasing.

4. Monotonic Stack

4.1 When to Use

Next greater element, daily temperatures, largest rectangle in histogram, trapping rainwater

4.2 Largest Rectangle in Histogram

int largestRectangleArea(const vector<int>& h) {
    vector<int> st; // indices with increasing heights
    int n = h.size(), best = 0;
    for (int i = 0; i <= n; ++i) {
        int cur = (i==n? 0 : h[i]);
        while (!st.empty() && h[st.back()] > cur) {
            int ht = h[st.back()]; st.pop_back();
            int L = st.empty()? 0 : st.back()+1;
            int R = i-1;
            best = max(best, ht * (R - L + 1));
        }
        st.push_back(i);
    }
    return best;
}

Invariant: Indices in stack have strictly increasing heights.

5. Binary Search on Answer (Parametric Search)

5.1 When to Use

Minimize a value with monotone feasibility ("can we do it with capacity X?")

5.2 Classic Questions

"Ship packages within D days" (min capacity)
"Koko eating bananas" (min speed)
"Split array largest sum" (min largest part)

5.3 Template

template <class Pred> // Pred(mid) -> bool
long long binarySearchAnswer(long long lo, long long hi, Pred ok) {
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (ok(mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
}

Pitfalls: Choose correct range; overflow (lo + (hi-lo)/2); ensure predicate is monotone.

6. Greedy + Sorting

6.1 Classic Questions

"Non-overlapping intervals" (maximize kept → sort by end)
"Meeting rooms II" (min rooms)
"Min arrows to burst balloons"
"Merge intervals"

6.2 Non-Overlapping Intervals (Erase Minimum)

int eraseOverlapIntervals(vector<pair<int,int>>& v) {
    sort(v.begin(), v.end(), [](auto& a, auto& b){ return a.second < b.second; });
    int cnt = 0, lastEnd = INT_MIN;
    for (auto& [s,e] : v) {
        if (s >= lastEnd) { ++cnt; lastEnd = e; }
    }
    return (int)v.size() - cnt; // removals
}

6.3 Meeting Rooms II (Sweep via Min-Heap)

int minMeetingRooms(vector<pair<int,int>>& v) {
    sort(v.begin(), v.end());
    priority_queue<int, vector<int>, greater<int>> pq;
    int best = 0;
    for (auto& [s,e] : v) {
        while (!pq.empty() && pq.top() <= s) pq.pop();
        pq.push(e);
        best = max(best, (int)pq.size());
    }
    return best;
}

7. Heaps / Priority Queues

7.1 Classic Questions

"Kth largest/smallest"
"Top K frequent"
"Merge K sorted lists"
"Find median from data stream" (two heaps)

7.2 Top-K Frequent

vector<int> topKFrequent(const vector<int>& a, int K) {
    unordered_map<int,int> f; f.reserve(a.size()*2);
    for (int x: a) ++f[x];
    using P = pair<int,int>; // freq, val
    priority_queue<P, vector<P>, greater<P>> pq; // min-heap
    for (auto& [val,c]: f) {
        if ((int)pq.size() < K) pq.emplace(c,val);
        else if (c > pq.top().first) { pq.pop(); pq.emplace(c,val); }
    }
    vector<int> out;
    while (!pq.empty()) { out.push_back(pq.top().second); pq.pop(); }
    return out;
}

Interview Flex: If you only need the Kth element, consider nth_element.

8. Disjoint Set Union (Union-Find)

8.1 When to Use

Connectivity under unions; detect cycles; components; Kruskal's MST; "accounts merge"

8.2 DSU Template

struct DSU {
    vector<int> p, r;
    DSU(int n): p(n), r(n,0) { iota(p.begin(), p.end(), 0); }
    int find(int x){ return p[x]==x? x : p[x]=find(p[x]); }
    bool unite(int a,int b){
        a=find(a); b=find(b);
        if (a==b) return false;
        if (r[a]<r[b]) swap(a,b);
        p[b]=a; if (r[a]==r[b]) ++r[a];
        return true;
    }
};

Pitfalls: Don't forget path compression and union by rank/size.

9. Sweep Line

9.1 When to Use

"Count overlaps / min rooms / min platforms", "Skyline"

9.2 Event Sorting Pattern

struct Event { int x, type; }; // type: +1 start, -1 end
// At identical x, process ends before starts to avoid overcounting.
sort(ev.begin(), ev.end(), [](auto& a, auto& b){
    if (a.x != b.x) return a.x < b.x;
    return a.type < b.type; // end(-1) before start(+1)
});

Idea: Scan in order, maintain active count with starts/ends.

10. Hashing Tricks

10.1 Classic Questions

Two-sum; Longest consecutive sequence; Anagrams; Subarray sum = k (prefix map)

10.2 Longest Consecutive Sequence (O(n))

int longestConsecutive(const vector<int>& a) {
    unordered_set<int> s(a.begin(), a.end());
    int best = 0;
    for (int x: s) if (!s.count(x-1)) { // start of a run
        int y = x;
        while (s.count(y)) ++y;
        best = max(best, y - x);
    }
    return best;
}

C++ Notes: Consider reserve for maps/sets when large. string_view avoids copies (be careful with lifetimes).

11. Graph Templates

11.1 Classic Questions

BFS shortest path in unweighted graph/grid; Dijkstra (weighted); Topological sort; Detect cycles; 0-1 BFS

11.2 BFS (Grid)

int bfsGrid(vector<string>& g) {
    int n=g.size(), m=g[0].size();
    queue<pair<int,int>> q;
    vector<vector<int>> dist(n, vector<int>(m, -1));
    q.push({0,0}); dist[0][0]=0;
    int dirs[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
    while(!q.empty()){
        auto [r,c]=q.front(); q.pop();
        for(auto& d:dirs){
            int nr=r+d[0], nc=c+d[1];
            if(nr<0||nr>=n||nc<0||nc>=m) continue;
            if(g[nr][nc]=='#'||dist[nr][nc]!=-1) continue;
            dist[nr][nc]=dist[r][c]+1;
            q.push({nr,nc});
        }
    }
    return dist[n-1][m-1];
}

11.3 Dijkstra (Adjacency List)

vector<long long> dijkstra(int n, const vector<vector<pair<int,int>>>& adj, int s){
    const long long INF = (1LL<<60);
    vector<long long> d(n, INF);
    using P = pair<long long,int>; // dist,node
    priority_queue<P, vector<P>, greater<P>> pq;
    d[s]=0; pq.push({0,s});
    while(!pq.empty()){
        auto [du,u]=pq.top(); pq.pop();
        if(du!=d[u]) continue;
        for(auto [v,w]: adj[u]){
            if(d[v]>du+w){ d[v]=du+w; pq.push({d[v],v}); }
        }
    }
    return d;
}

11.4 Topological Sort (Kahn)

vector<int> topoSort(int n, const vector<vector<int>>& g){
    vector<int> indeg(n,0);
    for(int u=0;u<n;++u) for(int v: g[u]) ++indeg[v];
    queue<int> q; for(int i=0;i<n;++i) if(!indeg[i]) q.push(i);
    vector<int> order;
    while(!q.empty()){
        int u=q.front(); q.pop(); order.push_back(u);
        for(int v: g[u]) if(--indeg[v]==0) q.push(v);
    }
    return (int)order.size()==n? order : vector<int>{}; // empty => cycle
}

Pitfalls: Recursion depth (prefer iterative DFS/BFS in interviews).

12. DP Patterns

12.1 Classic Questions

0/1 knapsack; Coin change; Edit distance; House robber; LIS (O(n log n)); Partition equal sum; Bitmask DP (TSP/assignments) for small n

12.2 LIS O(n log n) (Patience Sorting)

int LIS(const vector<int>& a){
    vector<int> tails; tails.reserve(a.size());
    for(int x: a){
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if(it==tails.end()) tails.push_back(x);
        else *it = x;
    }
    return (int)tails.size();
}

12.3 0/1 Knapsack (1D)

int knapsack01(const vector<int>& w, const vector<int>& val, int W){
    int n=w.size();
    vector<int> dp(W+1, 0);
    for(int i=0;i<n;++i){
        for(int cap=W; cap>=w[i]; --cap){
            dp[cap] = max(dp[cap], dp[cap - w[i]] + val[i]);
        }
    }
    return dp[W];
}

12.4 Edit Distance

int editDistance(const string& a, const string& b){
    int n=a.size(), m=b.size();
    vector<int> prev(m+1), cur(m+1);
    iota(prev.begin(), prev.end(), 0);
    for(int i=1;i<=n;++i){
        cur[0]=i;
        for(int j=1;j<=m;++j){
            if(a[i-1]==b[j-1]) cur[j]=prev[j-1];
            else cur[j]=1+min({prev[j], cur[j-1], prev[j-1]});
        }
        swap(prev,cur);
    }
    return prev[m];
}

13. STL & Language Fluency

13.1 What Interviewers Notice

Containers: Choose smallest sufficient (e.g., vector over list)
Algorithms: sort, nth_element (kth element), lower_bound/upper_bound, accumulate, partial_sum
Ranges (C++20): Nice-to-have; don't force if judge doesn't support it
I/O: ios::sync_with_stdio(false); cin.tie(nullptr);
Memory/Performance: reserve(), emplace_back(), pass by const&, return by value (NRVO)
Integers: Use long long for sums; safe mid: lo + (hi - lo)/2
Comparators: Lambdas with auto&
Custom Hash: Pairs/tuples if you need unordered containers of them
RAII Mindset: Even if not using exceptions, you know why it matters
Move Semantics: Returning large vectors is cheap

14. Rapid Practice Set (By Pattern)

14.1 Sliding Window

Longest substring without repeating chars (strings, map counts)
Min window substring (cover target counts)
Max consecutive 1s with at most K zeros flipped

14.2 Prefix Sums

Count subarrays sum = k (negatives allowed)
Subarray sums divisible by k (mod, handle negatives)
2D matrix region sum (build 2D prefix)

14.3 Monotonic Deque/Stack

Sliding window maximum
Daily temperatures / next greater element
Largest rectangle in histogram

14.4 Binary Search on Answer

Ship within D days (capacity)
Koko eating bananas (speed)
Split array largest sum

14.5 Greedy + Sorting

Non-overlapping intervals (min removals)
Min arrows to burst balloons
Meeting rooms II

14.6 Heaps

Top K frequent elements
Merge K sorted lists
Median from data stream

14.7 DSU

Number of connected components
Redundant connection (detect extra edge)
Kruskal's MST

14.8 Sweep Line

Skyline problem
Min platforms / meeting rooms via events

14.9 Graphs

BFS shortest path in grid
Dijkstra (weighted)
Topological sort (Kahn)

14.10 DP

0/1 knapsack (1D)
Edit distance
LIS O(n log n)

Prerequisites

Learning Objectives

Table of Contents