coding problems · high

LeetCode: 8 Must-Know Patterns — Two Pointers, Sliding Window, BFS, DP, Monotonic Stack

8 interview coding patterns. Two Pointers: l=0,r=n-1; converge (sorted pair sum) or stride (in-place compaction); O(n) O(1). Sliding Window: expand r; shrink l when invalid; O(n) total moves; use map for char counts. Fast/Slow Pointers (Floyd): cycle detection, middle of list, detect duplicate in [1..n]. Binary Search: mid=l+(r-l)/2 (no overflow); exact=l<=r; boundary=l<r with r=n, r=m when ok(m). BFS: queue + visited; shortest path (unweighted); level order. DFS: recursion/stack; backtracking; connected components; preorder/inorder. DP: define dp[i]; recurrence dp[i]=f(dp[j<i]); base case; bottom-up or memoized. Heap: top-K via min-heap size k; Dijkstra via min-heap (dist,node). Monotonic Stack: maintain decreasing (or increasing) stack of indices; pop when arr[i] breaks monotone = found next-greater for popped element. std::lower_bound, upper_bound, binary_search — know their semantics.

🔑 Key line

8 LeetCode patterns: Two Pointers (O(n) sorted pair), Sliding Window (expand+shrink), Fast/Slow (cycle detect), Binary Search (mid=l+(r-l)/2; boundary: l<r, r=m when ok), BFS/DFS, DP (define dp[i]; recurrence; fill order), Heap (top-K, Dijkstra), Monotonic Stack (next-greater; pop when invariant breaks).

The code

// 8 must-know C++ coding patterns for FAANG interviews

// Pattern 1: Two Pointers — O(n), no extra space
// Use: sorted array, palindrome, pair sum, container with most water
int l = 0, r = n - 1;
while (l < r) { /* converge or skip */
}

// Pattern 2: Sliding Window — O(n), variable or fixed window
// Use: max sum subarray, longest substring without repeat, min window
int l = 0, maxLen = 0;
for (int r = 0; r < n; r++) {
    window.add(arr[r]);
    while (window.invalid()) {
        window.remove(arr[l++]);
    }
    maxLen = max(maxLen, r - l + 1);
}

// Pattern 3: Fast/Slow Pointers (Floyd's) — cycle detection
// Use: linked list cycle, find middle, happy number
auto fast = head, slow = head;
while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
}
// slow at middle if no cycle; fast==slow if cycle

// Pattern 4: Binary Search — O(log n)
// Use: sorted array, rotated array, search space reduction
int l = 0, r = n - 1;
while (l <= r) {
    int m = l + (r - l) / 2; // avoid overflow
    if (arr[m] == target)
        return m;
    else if (arr[m] < target)
        l = m + 1;
    else
        r = m - 1;
}

// Pattern 5: BFS/DFS — graphs, trees, island counting
// BFS: queue, level order, shortest path (unweighted)
// DFS: recursion/stack, backtracking, connected components
queue<int> q;
q.push(start);
vis[start] = 1;
while (!q.empty()) {
    int u = q.front();
    q.pop(); /* process u */
}

// Pattern 6: Dynamic Programming
// Top-down (memo) or bottom-up (tabulation)
vector<int> dp(n + 1, 0); // 1D: dp[i] = answer for subproblem i
// 2D: dp[i][j] = answer for subproblem (i,j)
for (int i = 1; i <= n; i++)
    dp[i] = /* recurrence */;

// Pattern 7: Heap/Priority Queue
// K largest: min-heap size k
priority_queue<int, vector<int>, greater<int>> pq; // min heap
// Dijkstra: min heap of (dist, node)
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> dijkstra;

// Pattern 8: Monotonic Stack/Queue
// Use: next greater element, largest rectangle in histogram, sliding max
stack<int> st;
for (int i = 0; i < n; i++) {
    while (!st.empty() && arr[st.top()] < arr[i])
        process_next_greater(st.top(), i), st.pop();
    st.push(i);
}

What this lesson walks through

018 patterns that cover ~80% of interview coding problems
02Two Pointers — converge or stride
03Sliding Window — variable and fixed
04Binary Search — template and edge cases
05Dynamic Programming — identify recurrence
06Monotonic Stack/Queue — the secret pattern

These 8 patterns form a mental toolkit for C++ coding interviews. When you see a problem, first classify it into a pattern — then the solution structure becomes clear. Two Pointers, Sliding Window, Fast/Slow Pointers, Binary Search, BFS/DFS, Dynamic Programming, Heap/PQ, and Monotonic Stack. Recognizing the pattern is 80% of the solution.

See it animated — step by step, at your own pace

Unlock the full interactive walkthrough of LeetCode: 8 Must-Know Patterns — Two Pointers, Sliding Window, BFS, DP, Monotonic Stack and 100+ animated C++ interview lessons.

Start free →Already a member? Log in →