Contents

Monotonic Stack (next greater / histogram)

vector<int> nextGreater(vector<int>& a){
    int n = a.size(); vector<int> ans(n, -1); vector<int> st;
    for (int i = 0; i < 2*n; ++i){
        int idx = i % n;
        while (!st.empty() && a[st.back()] < a[idx]){
            ans[st.back()] = a[idx]; st.pop_back();
        }
        if (i < n) st.push_back(idx);
    }
    return ans;
}
ID Title Link Solution
739 Daily Temperatures Link -
84 Largest Rectangle in Histogram Link Solution
496 Next Greater Element I Link Solution
503 Next Greater Element II Link Solution

Monotonic Queue (sliding window extrema)

vector<int> maxWindow(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 Solution
239 Sliding Window Maximum Link Solution
1438 Longest Continuous Subarray With Absolute Diff <= Limit Link -

Heap / K-way Merge

vector<int> mergeK(vector<vector<int>>& lists){
    using T = tuple<int,int,int>; // val, list idx, pos
    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 Solution
23 Merge k Sorted Lists Link -
295 Find Median from Data Stream Link -

Union-Find (Disjoint Set Union)

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 Solution
684 Redundant Connection Link Solution
721 Accounts Merge Link -
1319 Number of Operations to Make Network Connected Link -

Trie (Prefix Tree)

struct Trie{
    struct Node{ int nxt[26]; bool end; Node(){ memset(nxt,-1,sizeof nxt); end=false; } };
    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){ int i=c-'a'; if((u=t[u].nxt[i])==-1) return false; } return t[u].end; }
};
ID Title Link Solution
208 Implement Trie Link -
211 Add and Search Word Link -
212 Word Search II Link -

Segment Tree (range query / point update)

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

Fenwick Tree (Binary Indexed Tree)

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; }
};
ID Title Link Solution
315 Count of Smaller Numbers After Self Link -
307 Range Sum Query – Mutable Link -
308 Range Sum Query 2D - Mutable Link Solution
715 Range Module Link Solution