This page is your toolbox of essential data structures for LeetCode. Each template is self-contained C++ you can copy directly into your solution. They range from beginner-friendly (binary search, prefix sum) to advanced (segment tree, sparse table) — start with what you need and come back for more as you level up.

This is the foundation. These data structures are the building blocks that other templates (DFS, BFS, DP) build on. Master binary search and prefix sums first, then work outward — you’ll see them appear inside graph, tree, and dynamic programming solutions.

Which Data Structure Do I Need? Sorted + search? → Binary Search Range sums? → Prefix Sum / BIT Next greater/smaller? → Monotonic Stack Top-K / min cost? → Heap Connected groups? → Union-Find (DSU) Prefix of strings? → Trie Range query + update? → Segment Tree Static range min/max? → Sparse Table Start with binary search + prefix sum — they appear inside most other patterns

Contents

Binary Search (Bounds)

When to use: The input is sorted (or the answer space is monotonic) and you need to find a boundary — first element ≥ x, last element ≤ x, or the minimum/maximum value satisfying a condition.

Half-open range [lo, hi). Use when you need first ≥ x (lower_bound) or first > x (upper_bound).

Binary Search on [2, 5, 8, 12, 16, 23, 38] — target = 23 2 5 8 12 16 23 38 lo mid ✓ hi Step 1: lo=0, hi=6, mid=3 → 12 < 23 → lo=4 Step 2: lo=4, hi=6, mid=5 → 23 = target → found! Key: half-open range [lo, hi) — mid never equals hi 
// First index where a[i] >= x (lower_bound)
int lower_bound(const vector<int>& a, int x) {
    int lo = 0, hi = a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// First index where a[i] > x (upper_bound)
int upper_bound(const vector<int>& a, int x) {
    int lo = 0, hi = a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// Binary search on answer: smallest x in [lo, hi] such that ok(x)
template<class F>
int bsearch_ans(int lo, int hi, F ok) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (ok(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
ID Title Link
34 Find First and Last Position Link
35 Search Insert Position Link
875 Koko Eating Bananas Link

Prefix Sum & Difference Array

When to use: You need to answer many “sum of subarray [l, r]” queries, or apply the same increment to many ranges efficiently.

Prefix sum: range sum in O(1). Difference array: range add in O(1), then one prefix sum to recover.

// Prefix sum: ps[i] = a[0]+...+a[i-1], sum(l,r) = ps[r+1]-ps[l]
vector<long long> prefix(const vector<int>& a) {
    vector<long long> ps(a.size() + 1);
    for (int i = 0; i < (int)a.size(); i++) ps[i + 1] = ps[i] + a[i];
    return ps;
}

// Difference array: for [l,r] += d do diff[l]+=d, diff[r+1]-=d; then partial_sum(diff) = values
void range_add(vector<long long>& diff, int l, int r, long long d) {
    diff[l] += d;
    if (r + 1 < (int)diff.size()) diff[r + 1] -= d;
}
// After all updates: partial_sum(diff.begin(), diff.end(), diff.begin());
ID Title Link
560 Subarray Sum Equals K Link
1109 Corporate Flight Bookings Link
1094 Car Pooling Link

Monotonic Stack

When to use: You need “next greater element”, “next smaller element”, “largest rectangle in histogram”, or any problem where each element is compared to its neighbors in one direction.

Maintain indices with strictly increasing (or decreasing) values. Use for next greater/smaller, or histogram rectangle.

// Next greater element (for each index)
vector<int> next_greater(const vector<int>& a) {
    int n = a.size();
    vector<int> ng(n, -1);
    vector<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.back()] < a[i]) {
            ng[st.back()] = a[i];
            st.pop_back();
        }
        st.push_back(i);
    }
    return ng;
}

// Circular: wrap with 2*n and only push when i < n
vector<int> next_greater_circular(const vector<int>& a) {
    int n = a.size();
    vector<int> ng(n, -1);
    vector<int> st;
    for (int i = 0; i < 2 * n; i++) {
        int j = i % n;
        while (!st.empty() && a[st.back()] < a[j]) {
            ng[st.back()] = a[j];
            st.pop_back();
        }
        if (i < n) st.push_back(j);
    }
    return ng;
}
ID Title Link
739 Daily Temperatures Link
42 Trapping Rain Water Link
84 Largest Rectangle in Histogram Link
503 Next Greater Element II Link
1944 Visible People in Queue Link

Monotonic Queue

When to use: You need the maximum or minimum within a sliding window of fixed size, or need to maintain a monotonic property as elements enter and leave a window.

Deque of indices with values in monotonic order. Sliding window max/min.

// Sliding window maximum (window size k)
vector<int> max_sliding_window(const vector<int>& a, int k) {
    deque<int> dq;
    vector<int> out;
    for (int i = 0; i < (int)a.size(); i++) {
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front();
        if (i >= k - 1) out.push_back(a[dq.front()]);
    }
    return out;
}
ID Title Link
239 Sliding Window Maximum Link
1438 Longest Continuous Subarray With Abs Diff ≤ Limit Link

Heap / Priority Queue

When to use: You repeatedly need the smallest (or largest) element — merging k sorted lists, scheduling, median maintenance, or any “top K” problem.

Min-heap: priority_queue<T, vector<T>, greater<T>>. K-way merge: push heads, pop min, push next from same list.

// K-way merge of sorted arrays (or list heads)
vector<int> merge_k_sorted(const vector<vector<int>>& lists) {
    using T = tuple<int, int, int>;
    priority_queue<T, vector<T>, greater<T>> pq;
    for (int i = 0; i < (int)lists.size(); i++)
        if (!lists[i].empty()) pq.emplace(lists[i][0], i, 0);
    vector<int> out;
    while (!pq.empty()) {
        auto [v, i, j] = pq.top();
        pq.pop();
        out.push_back(v);
        if (j + 1 < (int)lists[i].size()) pq.emplace(lists[i][j + 1], i, j + 1);
    }
    return out;
}
ID Title Link
23 Merge k Sorted Lists Link
295 Find Median from Data Stream Link

Union-Find (DSU)

When to use: You need to track connected components, determine if two nodes are in the same group, or merge groups — common in graph connectivity, redundant edge detection, and “accounts merge” problems.

Path compression + rank merge. find(x), unite(a,b).

Union-Find — unite(1,2), unite(3,4), unite(2,3) 0 1 2 3 4 Group {0,1,2} Group {3,4} find(x) returns root with path compression | unite merges two groups 
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;
    }
};
ID Title Link
684 Redundant Connection Link
721 Accounts Merge Link
1319 Number of Operations to Make Network Connected Link

Trie

When to use: Problems involve prefix matching, autocomplete, word search in a dictionary, or “find all words with prefix X”. Also useful for XOR-maximization with a bitwise trie.

Fixed alphabet (e.g. 26). Insert and search in O( s ).
Trie for words: "cat", "car", "dog" root c d a a t✓ r✓ o g✓ Shared prefixes share nodes — "cat" and "car" share c→a 
struct Trie {
    struct Node {
        int nxt[26];
        bool end = false;
        Node() { memset(nxt, -1, sizeof nxt); }
    };
    vector<Node> t{1};
    void insert(const string& s) {
        int u = 0;
        for (char c : s) {
            int i = c - 'a';
            if (t[u].nxt[i] == -1) { t[u].nxt[i] = t.size(); t.emplace_back(); }
            u = t[u].nxt[i];
        }
        t[u].end = true;
    }
    bool search(const string& s) {
        int u = 0;
        for (char c : s) {
            u = t[u].nxt[c - 'a'];
            if (u == -1) return false;
        }
        return t[u].end;
    }
};
ID Title Link
208 Implement Trie Link
211 Design Add and Search Words Link
212 Word Search II Link

Segment Tree

When to use: You need both range queries (sum, min, max) AND point or range updates on the same array. More powerful than Fenwick tree when you need lazy propagation or non-commutative operations.

0-indexed range [0, n-1]. Point update, range sum (or min/max). Recursive implementation.

struct SegTree {
    int n;
    vector<long long> st;
    SegTree(int n) : n(n), st(4 * n, 0) {}
    void upd(int i, int l, int r, int p, long long v) {
        if (l == r) { st[i] = v; return; }
        int m = (l + r) / 2;
        if (p <= m) upd(2 * i, l, m, p, v);
        else upd(2 * i + 1, m + 1, r, p, v);
        st[i] = st[2 * i] + st[2 * i + 1];
    }
    long long qry(int i, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return st[i];
        int m = (l + r) / 2;
        return qry(2 * i, l, m, ql, qr) + qry(2 * i + 1, m + 1, r, ql, qr);
    }
    void upd(int p, long long v) { upd(1, 0, n - 1, p, v); }
    long long qry(int ql, int qr) { return qry(1, 0, n - 1, ql, qr); }
};
ID Title Link
307 Range Sum Query – Mutable Link
732 My Calendar III Link

Fenwick Tree (BIT)

When to use: You need prefix sums with point updates — simpler and faster constant than segment tree when you don’t need lazy propagation. Great for counting inversions or “count of smaller numbers after self”.

1-indexed. Point add, prefix sum. Range sum [l, r] = sum(r) - sum(l-1).

struct BIT {
    int n;
    vector<long long> f;
    BIT(int n) : n(n), f(n + 1, 0) {}
    void add(int i, long long v) {
        for (; i <= n; i += i & -i) f[i] += v;
    }
    long long sum(int i) {
        long long s = 0;
        for (; i > 0; i -= i & -i) s += f[i];
        return s;
    }
    long long range_sum(int l, int r) { return sum(r) - sum(l - 1); }
};
ID Title Link
307 Range Sum Query – Mutable Link
315 Count of Smaller Numbers After Self Link
308 Range Sum Query 2D – Mutable Link

Sparse Table (Range Min/Max)

When to use: You need O(1) range min/max/gcd queries with NO updates. Perfect for static arrays where you precompute once and query many times.

O(n log n) build, O(1) range min/max. Idempotent only (min, max, gcd). 0-indexed.

struct SparseTable {
    vector<vector<int>> st;
    vector<int> lg;
    int op(int a, int b) { return min(a, b); } // or max
    SparseTable(const vector<int>& a) {
        int n = a.size();
        lg.assign(n + 1, 0);
        for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
        int k = lg[n] + 1;
        st.assign(n, vector<int>(k));
        for (int i = 0; i < n; i++) st[i][0] = a[i];
        for (int j = 1; j < k; j++)
            for (int i = 0; i + (1 << j) <= n; i++)
                st[i][j] = op(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    }
    int qry(int l, int r) {
        int j = lg[r - l + 1];
        return op(st[l][j], st[r - (1 << j) + 1][j]);
    }
};
ID Title Link
— Range min/max, GCD (no update) —

Quick Reference

Structure When to Use Operations Time
Binary Search Sorted data, find boundary lower/upper bound O(log n)
Prefix Sum Range sum queries build + query O(n) + O(1)
Monotonic Stack Next greater/smaller push/pop O(n)
DSU Connected components, union find/union O(α(n))
Trie Prefix search, autocomplete insert/search O(L)
Segment Tree Range query + update build/query/update O(n) + O(log n)
Fenwick Tree Prefix sums + point update update/query O(log n)

More Templates