design_patterns.cpp

/*
LeetCode Design Patterns - Data Structure Design Problems
Mathematical Foundation: API Design + Optimal Time/Space Complexity
Core: Constructor, Insert, Delete, Query operations with constraints
Applications: Cache systems, data streams, special collections
*/

#include <bits/stdc++.h>
using namespace std;

// 981. Time Based Key-Value Store
// https://leetcode.com/problems/time-based-key-value-store/
class TimeMap {
    unordered_map<string, vector<pair<int, string>>> mp;
public:
    void set(string k, string v, int t) { mp[k].push_back({t, v}); }
    string get(string k, int t) {
        if (!mp.count(k)) return "";
        auto& vec = mp[k];
        int l = 0, r = vec.size() - 1, ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (vec[mid].first <= t) { ans = mid; l = mid + 1; }
            else r = mid - 1;
        }
        return ans == -1 ? "" : vec[ans].second;
    }
};

// 232. Implement Queue using Stacks
// https://leetcode.com/problems/implement-queue-using-stacks/
class MyQueue {
    stack<int> in, out;
public:
    void push(int x) { in.push(x); }
    int pop() { peek(); int x = out.top(); out.pop(); return x; }
    int peek() { if (out.empty()) while (!in.empty()) { out.push(in.top()); in.pop(); } return out.top(); }
    bool empty() { return in.empty() && out.empty(); }
};

// 225. Implement Stack using Queues
// https://leetcode.com/problems/implement-stack-using-queues/
class MyStack {
    queue<int> q;
public:
    void push(int x) { q.push(x); for (int i = 0; i < q.size() - 1; i++) { q.push(q.front()); q.pop(); } }
    int pop() { int x = q.front(); q.pop(); return x; }
    int top() { return q.front(); }
    bool empty() { return q.empty(); }
};

// 155. Min Stack
// https://leetcode.com/problems/min-stack/
class MinStack {
    stack<int> st, mn;
public:
    void push(int x) { st.push(x); mn.push(mn.empty() ? x : min(x, mn.top())); }
    void pop() { st.pop(); mn.pop(); }
    int top() { return st.top(); }
    int getMin() { return mn.top(); }
};

// 716. Max Stack
// https://leetcode.com/problems/max-stack/
class MaxStack {
    stack<int> st, mx;
public:
    void push(int x) { st.push(x); mx.push(mx.empty() ? x : max(x, mx.top())); }
    int pop() { int x = st.top(); st.pop(); mx.pop(); return x; }
    int top() { return st.top(); }
    int peekMax() { return mx.top(); }
    int popMax() {
        int maxVal = mx.top();
        stack<int> tmp;
        while (st.top() != maxVal) { tmp.push(pop()); }
        pop();
        while (!tmp.empty()) { push(tmp.top()); tmp.pop(); }
        return maxVal;
    }
};

// 146. LRU Cache
// https://leetcode.com/problems/lru-cache/
class LRUCache {
    struct Node { int k, v; Node *p, *n; Node(int x = 0, int y = 0) : k(x), v(y) {} };
    unordered_map<int, Node*> mp;
    Node *h, *t;
    int cap;
    void add(Node* x) { x->p = h; x->n = h->n; h->n->p = x; h->n = x; }
    void del(Node* x) { x->p->n = x->n; x->n->p = x->p; }
    void move(Node* x) { del(x); add(x); }
public:
    LRUCache(int c) : cap(c) { h = new Node(); t = new Node(); h->n = t; t->p = h; }
    int get(int k) { if (!mp.count(k)) return -1; move(mp[k]); return mp[k]->v; }
    void put(int k, int v) {
        if (mp.count(k)) { mp[k]->v = v; move(mp[k]); }
        else {
            if (mp.size() >= cap) { Node* x = t->p; del(x); mp.erase(x->k); delete x; }
            Node* x = new Node(k, v); add(x); mp[k] = x;
        }
    }
};

// 460. LFU Cache
// https://leetcode.com/problems/lfu-cache/
class LFUCache {
    struct Node { int k, v, f; Node *p, *n; Node(int x = 0, int y = 0, int z = 0) : k(x), v(y), f(z) {} };
    unordered_map<int, Node*> mp;
    unordered_map<int, Node*> freq;
    int cap, minF;
    void add(Node* x, int f) { if (!freq[f]) { freq[f] = new Node(); freq[f]->n = freq[f]->p = freq[f]; } 
        x->p = freq[f]; x->n = freq[f]->n; freq[f]->n->p = x; freq[f]->n = x; }
    void del(Node* x) { x->p->n = x->n; x->n->p = x->p; }
    void update(Node* x) { del(x); x->f++; add(x, x->f); 
        if (freq[minF]->n == freq[minF]) minF++; }
public:
    LFUCache(int c) : cap(c), minF(0) {}
    int get(int k) { if (!mp.count(k)) return -1; update(mp[k]); return mp[k]->v; }
    void put(int k, int v) {
        if (cap == 0) return;
        if (mp.count(k)) { mp[k]->v = v; update(mp[k]); }
        else {
            if (mp.size() >= cap) { Node* x = freq[minF]->p; del(x); mp.erase(x->k); delete x; }
            Node* x = new Node(k, v, 1); add(x, 1); mp[k] = x; minF = 1;
        }
    }
};

// 208. Implement Trie (Prefix Tree)
// https://leetcode.com/problems/implement-trie-prefix-tree/
class Trie {
    struct Node { Node* ch[26] = {}; bool end = false; };
    Node* root;
public:
    Trie() { root = new Node(); }
    void insert(string w) { Node* p = root; for (char c : w) { if (!p->ch[c-'a']) p->ch[c-'a'] = new Node(); p = p->ch[c-'a']; } p->end = true; }
    bool search(string w) { Node* p = root; for (char c : w) { if (!p->ch[c-'a']) return false; p = p->ch[c-'a']; } return p->end; }
    bool startsWith(string w) { Node* p = root; for (char c : w) { if (!p->ch[c-'a']) return false; p = p->ch[c-'a']; } return true; }
};

// 211. Design Add and Search Words Data Structure
// https://leetcode.com/problems/design-add-and-search-words-data-structure/
class WordDictionary {
    struct Node { Node* ch[26] = {}; bool end = false; };
    Node* root;
    bool dfs(Node* p, string& w, int i) {
        if (i == w.size()) return p->end;
        if (w[i] == '.') { for (auto c : p->ch) if (c && dfs(c, w, i+1)) return true; return false; }
        return p->ch[w[i]-'a'] && dfs(p->ch[w[i]-'a'], w, i+1);
    }
public:
    WordDictionary() { root = new Node(); }
    void addWord(string w) { Node* p = root; for (char c : w) { if (!p->ch[c-'a']) p->ch[c-'a'] = new Node(); p = p->ch[c-'a']; } p->end = true; }
    bool search(string w) { return dfs(root, w, 0); }
};

// 295. Find Median from Data Stream
// https://leetcode.com/problems/find-median-from-data-stream/
class MedianFinder {
    priority_queue<int> lo;
    priority_queue<int, vector<int>, greater<int>> hi;
public:
    void addNum(int x) { lo.push(x); hi.push(lo.top()); lo.pop(); if (lo.size() < hi.size()) { lo.push(hi.top()); hi.pop(); } }
    double findMedian() { return lo.size() > hi.size() ? lo.top() : (lo.top() + hi.top()) / 2.0; }
};

// 355. Design Twitter
// https://leetcode.com/problems/design-twitter/
class Twitter {
    unordered_map<int, unordered_set<int>> follow;
    vector<pair<int, int>> tweets;
public:
    void postTweet(int uid, int tid) { tweets.push_back({uid, tid}); }
    vector<int> getNewsFeed(int uid) {
        vector<int> res;
        for (int i = tweets.size() - 1; i >= 0 && res.size() < 10; i--) {
            int u = tweets[i].first;
            if (u == uid || follow[uid].count(u)) res.push_back(tweets[i].second);
        }
        return res;
    }
    void follow(int f1, int f2) { if (f1 != f2) follow[f1].insert(f2); }
    void unfollow(int f1, int f2) { follow[f1].erase(f2); }
};

// 362. Design Hit Counter
// https://leetcode.com/problems/design-hit-counter/
class HitCounter {
    queue<int> hits;
public:
    void hit(int t) { hits.push(t); }
    int getHits(int t) { while (!hits.empty() && t - hits.front() >= 300) hits.pop(); return hits.size(); }
};

// 380. Insert Delete GetRandom O(1)
// https://leetcode.com/problems/insert-delete-getrandom-o1/
class RandomizedSet {
    vector<int> nums;
    unordered_map<int, int> pos;
public:
    bool insert(int x) { if (pos.count(x)) return false; pos[x] = nums.size(); nums.push_back(x); return true; }
    bool remove(int x) { 
        if (!pos.count(x)) return false;
        int last = nums.back(), idx = pos[x];
        nums[idx] = last; pos[last] = idx;
        nums.pop_back(); pos.erase(x); return true;
    }
    int getRandom() { return nums[rand() % nums.size()]; }
};

// 381. Insert Delete GetRandom O(1) - Duplicates allowed
// https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/
class RandomizedCollection {
    vector<int> nums;
    unordered_map<int, unordered_set<int>> pos;
public:
    bool insert(int x) { bool res = !pos.count(x); pos[x].insert(nums.size()); nums.push_back(x); return res; }
    bool remove(int x) {
        if (!pos.count(x)) return false;
        int idx = *pos[x].begin(), last = nums.back();
        pos[x].erase(idx); if (pos[x].empty()) pos.erase(x);
        if (idx != nums.size() - 1) { nums[idx] = last; pos[last].erase(nums.size() - 1); pos[last].insert(idx); }
        nums.pop_back(); return true;
    }
    int getRandom() { return nums[rand() % nums.size()]; }
};

// 146. LRU Cache (Alternative Implementation)
// https://leetcode.com/problems/lru-cache/
class LRUCache2 {
    list<pair<int, int>> cache;
    unordered_map<int, list<pair<int, int>>::iterator> mp;
    int cap;
public:
    LRUCache2(int c) : cap(c) {}
    int get(int k) { 
        if (!mp.count(k)) return -1;
        cache.splice(cache.begin(), cache, mp[k]); return mp[k]->second;
    }
    void put(int k, int v) {
        if (mp.count(k)) { mp[k]->second = v; cache.splice(cache.begin(), cache, mp[k]); }
        else {
            if (cache.size() >= cap) { mp.erase(cache.back().first); cache.pop_back(); }
            cache.emplace_front(k, v); mp[k] = cache.begin();
        }
    }
};

// 284. Peeking Iterator
// https://leetcode.com/problems/peeking-iterator/
// Minimal Iterator definition for compilation(pre-defined in leetcode)
class Iterator {
    vector<int>::const_iterator cur, end;
public:
    Iterator(const vector<int>& nums) : cur(nums.begin()), end(nums.end()) {}
    int next() { return *cur++; }
    bool hasNext() const { return cur != end; }
};

class PeekingIterator : public Iterator {
    int next_val;
    bool has_next;
public:
    PeekingIterator(const vector<int>& nums) : Iterator(nums), has_next(Iterator::hasNext()) {
        if (has_next) next_val = Iterator::next();
    }
    int peek() { return next_val; }
    int next() { int res = next_val; has_next = Iterator::hasNext(); if (has_next) next_val = Iterator::next(); return res; }
    bool hasNext() const { return has_next; }
};

// 173. Binary Search Tree Iterator
// https://leetcode.com/problems/binary-search-tree-iterator/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BSTIterator {
    stack<TreeNode*> st;
    void pushLeft(TreeNode* root) { while (root) { st.push(root); root = root->left; } }
public:
    BSTIterator(TreeNode* root) { pushLeft(root); }
    int next() { TreeNode* node = st.top(); st.pop(); pushLeft(node->right); return node->val; }
    bool hasNext() { return !st.empty(); }
};

// 341. Flatten Nested List Iterator
// https://leetcode.com/problems/flatten-nested-list-iterator/

// Minimal stub for NestedInteger to allow compilation (pre-defined in leetcode)
class NestedInteger {
public:
    // Return true if this NestedInteger holds a single integer, rather than a nested list.
    bool isInteger() const { return true; }
    // Return the single integer that this NestedInteger holds, if it holds a single integer.
    int getInteger() const { return 0; }
    // Return the nested list that this NestedInteger holds, if it holds a nested list.
    const vector<NestedInteger> &getList() const { static vector<NestedInteger> dummy; return dummy; }
};

class NestedIterator {
    stack<NestedInteger> st;
public:
    NestedIterator(vector<NestedInteger> &nestedList) { for (int i = nestedList.size() - 1; i >= 0; i--) st.push(nestedList[i]); }
    int next() { NestedInteger ni = st.top(); st.pop(); return ni.getInteger(); }
    bool hasNext() {
        while (!st.empty() && !st.top().isInteger()) {
            NestedInteger ni = st.top(); st.pop();
            for (int i = ni.getList().size() - 1; i >= 0; i--) st.push(ni.getList()[i]);
        }
        return !st.empty();
    }
};

// 900. RLE Iterator
// https://leetcode.com/problems/rle-iterator/
class RLEIterator {
    vector<int> enc;
    int idx;
public:
    RLEIterator(vector<int>& encoding) : enc(encoding), idx(0) {}
    int next(int n) {
        while (idx < enc.size() && enc[idx] < n) { n -= enc[idx]; idx += 2; }
        if (idx >= enc.size()) return -1;
        enc[idx] -= n; return enc[idx + 1];
    }
};

// 348. Design Tic-Tac-Toe
// https://leetcode.com/problems/design-tic-tac-toe/
class TicTacToe {
    vector<int> rows, cols;
    int diag, anti_diag, n;
public:
    TicTacToe(int sz) : n(sz), rows(sz), cols(sz), diag(0), anti_diag(0) {}
    int move(int r, int c, int player) {
        int add = player == 1 ? 1 : -1;
        rows[r] += add; cols[c] += add;
        if (r == c) diag += add;
        if (r + c == n - 1) anti_diag += add;
        return (abs(rows[r]) == n || abs(cols[c]) == n || abs(diag) == n || abs(anti_diag) == n) ? player : 0;
    }
};

// 353. Design Snake Game
// https://leetcode.com/problems/design-snake-game/
class SnakeGame {
    deque<pair<int, int>> snake;
    unordered_set<int> body;
    vector<vector<int>> food;
    int m, n, score, fidx;
public:
    SnakeGame(int w, int h, vector<vector<int>>& f) : n(w), m(h), food(f), score(0), fidx(0) {
        snake.push_back({0, 0}); body.insert(0);
    }
    int move(string dir) {
        auto [x, y] = snake.front();
        if (dir == "U") x--;
        else if (dir == "D") x++;
        else if (dir == "L") y--;
        else y++;
        
        if (x < 0 || x >= m || y < 0 || y >= n) return -1;
        
        bool eat = fidx < food.size() && x == food[fidx][0] && y == food[fidx][1];
        if (!eat) { auto [tx, ty] = snake.back(); snake.pop_back(); body.erase(tx * n + ty); }
        else { score++; fidx++; }
        
        int pos = x * n + y;
        if (body.count(pos)) return -1;
        snake.push_front({x, y}); body.insert(pos);
        return score;
    }
};

// 1146. Snapshot Array
// https://leetcode.com/problems/snapshot-array/
class SnapshotArray {
    vector<map<int, int>> arr;
    int snap_id;
public:
    SnapshotArray(int len) : arr(len), snap_id(0) {}
    void set(int idx, int val) { arr[idx][snap_id] = val; }
    int snap() { return snap_id++; }
    int get(int idx, int snap_id) {
        auto it = arr[idx].upper_bound(snap_id);
        return it == arr[idx].begin() ? 0 : prev(it)->second;
    }
};

// 1381. Design a Stack With Increment Operation
// https://leetcode.com/problems/design-a-stack-with-increment-operation/
class CustomStack {
    vector<int> st, inc;
    int top;
public:
    CustomStack(int sz) : st(sz), inc(sz), top(0) {}
    void push(int x) { if (top < st.size()) st[top++] = x; }
    int pop() { if (top == 0) return -1; 
        int res = st[--top] + inc[top]; 
        if (top > 0) inc[top - 1] += inc[top]; 
        inc[top] = 0; return res; }
    void increment(int k, int val) { if (top > 0) inc[min(k, top) - 1] += val; }
};

// 432. All O`one Data Structure
// https://leetcode.com/problems/all-oone-data-structure/
class AllOne {
    struct Node { int count; unordered_set<string> keys; Node *prev, *next; 
        Node(int c) : count(c), prev(nullptr), next(nullptr) {} };
    unordered_map<string, Node*> mp;
    Node *head, *tail;
    void remove(Node* node) { node->prev->next = node->next; node->next->prev = node->prev; delete node; }
    Node* insert(Node* prev, int count) { Node* node = new Node(count); 
        node->next = prev->next; node->prev = prev; prev->next->prev = node; prev->next = node; return node; }
public:
    AllOne() { head = new Node(0); tail = new Node(0); head->next = tail; tail->prev = head; }
    void inc(string key) {
        if (!mp.count(key)) {
            if (head->next->count != 1) insert(head, 1);
            head->next->keys.insert(key); mp[key] = head->next;
        } else {
            Node* node = mp[key]; node->keys.erase(key);
            if (node->next->count != node->count + 1) insert(node, node->count + 1);
            node->next->keys.insert(key); mp[key] = node->next;
            if (node->keys.empty()) remove(node);
        }
    }
    void dec(string key) {
        Node* node = mp[key]; node->keys.erase(key);
        if (node->count == 1) mp.erase(key);
        else {
            if (node->prev->count != node->count - 1) insert(node->prev, node->count - 1);
            node->prev->keys.insert(key); mp[key] = node->prev;
        }
        if (node->keys.empty()) remove(node);
    }
    string getMaxKey() { return tail->prev == head ? "" : *tail->prev->keys.begin(); }
    string getMinKey() { return head->next == tail ? "" : *head->next->keys.begin(); }
};

// 705. Design HashSet
// https://leetcode.com/problems/design-hashset/
class MyHashSet {
    vector<list<int>> buckets;
    int sz = 1000;
    int hash(int key) { return key % sz; }
public:
    MyHashSet() : buckets(sz) {}
    void add(int key) { int h = hash(key); auto& bucket = buckets[h]; 
        if (find(bucket.begin(), bucket.end(), key) == bucket.end()) bucket.push_back(key); }
    void remove(int key) { int h = hash(key); auto& bucket = buckets[h]; bucket.remove(key); }
    bool contains(int key) { int h = hash(key); auto& bucket = buckets[h]; 
        return find(bucket.begin(), bucket.end(), key) != bucket.end(); }
};

// 706. Design HashMap
// https://leetcode.com/problems/design-hashmap/
class MyHashMap {
    vector<list<pair<int, int>>> buckets;
    int sz = 1000;
    int hash(int key) { return key % sz; }
public:
    MyHashMap() : buckets(sz) {}
    void put(int key, int val) { int h = hash(key); auto& bucket = buckets[h];
        for (auto& p : bucket) if (p.first == key) { p.second = val; return; }
        bucket.push_back({key, val}); }
    int get(int key) { int h = hash(key); auto& bucket = buckets[h];
        for (auto& p : bucket) if (p.first == key) return p.second; return -1; }
    void remove(int key) { int h = hash(key); auto& bucket = buckets[h];
        bucket.remove_if([key](const auto& p) { return p.first == key; }); }
};

// 707. Design Linked List
// https://leetcode.com/problems/design-linked-list/
class MyLinkedList {
    struct Node { int val; Node* next; Node(int x) : val(x), next(nullptr) {} };
    Node* head; int sz;
public:
    MyLinkedList() : head(nullptr), sz(0) {}
    int get(int idx) { if (idx >= sz) return -1; Node* p = head; 
        for (int i = 0; i < idx; i++) p = p->next; return p->val; }
    void addAtHead(int val) { Node* node = new Node(val); node->next = head; head = node; sz++; }
    void addAtTail(int val) { if (!head) { addAtHead(val); return; } 
        Node* p = head; while (p->next) p = p->next; p->next = new Node(val); sz++; }
    void addAtIndex(int idx, int val) { if (idx > sz) return; if (idx == 0) { addAtHead(val); return; }
        Node* p = head; for (int i = 0; i < idx - 1; i++) p = p->next; 
        Node* node = new Node(val); node->next = p->next; p->next = node; sz++; }
    void deleteAtIndex(int idx) { if (idx >= sz) return; if (idx == 0) { head = head->next; sz--; return; }
        Node* p = head; for (int i = 0; i < idx - 1; i++) p = p->next; 
        p->next = p->next->next; sz--; }
};

// 1244. Design A Leaderboard
// https://leetcode.com/problems/design-a-leaderboard/
class Leaderboard {
    unordered_map<int, int> scores;
public:
    void addScore(int id, int score) { scores[id] += score; }
    int top(int k) { vector<int> vals; for (auto& p : scores) vals.push_back(p.second);
        nth_element(vals.begin(), vals.begin() + k - 1, vals.end(), greater<int>());
        return accumulate(vals.begin(), vals.begin() + k, 0); }
    void reset(int id) { scores[id] = 0; }
};

// 1472. Design Browser History
// https://leetcode.com/problems/design-browser-history/
class BrowserHistory {
    vector<string> history;
    int cur;
public:
    BrowserHistory(string homepage) : cur(0) { history.push_back(homepage); }
    void visit(string url) { history.erase(history.begin() + cur + 1, history.end()); 
        history.push_back(url); cur++; }
    string back(int steps) { cur = max(0, cur - steps); return history[cur]; }
    string forward(int steps) { cur = min((int)history.size() - 1, cur + steps); return history[cur]; }
};

// 1656. Design an Ordered Stream
// https://leetcode.com/problems/design-an-ordered-stream/
class OrderedStream {
    vector<string> stream;
    int ptr;
public:
    OrderedStream(int n) : stream(n + 1), ptr(1) {}
    vector<string> insert(int id, string val) { stream[id] = val; vector<string> res;
        while (ptr < stream.size() && !stream[ptr].empty()) res.push_back(stream[ptr++]);
        return res; }
};

// 1286. Iterator for Combination
// https://leetcode.com/problems/iterator-for-combination/
class CombinationIterator {
    vector<string> combos;
    int idx;
    void generate(string& chars, int start, int k, string cur) {
        if (k == 0) { combos.push_back(cur); return; }
        for (int i = start; i <= chars.size() - k; i++) generate(chars, i + 1, k - 1, cur + chars[i]);
    }
public:
    CombinationIterator(string chars, int k) : idx(0) { generate(chars, 0, k, ""); }
    string next() { return combos[idx++]; }
    bool hasNext() { return idx < combos.size(); }
};

// 622. Design Circular Queue
// https://leetcode.com/problems/design-circular-queue/
class MyCircularQueue {
    vector<int> q;
    int front, rear, sz, cap;
public:
    MyCircularQueue(int k) : q(k), front(0), rear(0), sz(0), cap(k) {}
    bool enQueue(int val) { if (isFull()) return false; q[rear] = val; rear = (rear + 1) % cap; sz++; return true; }
    bool deQueue() { if (isEmpty()) return false; front = (front + 1) % cap; sz--; return true; }
    int Front() { return isEmpty() ? -1 : q[front]; }
    int Rear() { return isEmpty() ? -1 : q[(rear - 1 + cap) % cap]; }
    bool isEmpty() { return sz == 0; }
    bool isFull() { return sz == cap; }
};

// 641. Design Circular Deque
// https://leetcode.com/problems/design-circular-deque/
class MyCircularDeque {
    vector<int> dq;
    int front, rear, sz, cap;
public:
    MyCircularDeque(int k) : dq(k), front(0), rear(0), sz(0), cap(k) {}
    bool insertFront(int val) { if (isFull()) return false; front = (front - 1 + cap) % cap; dq[front] = val; sz++; return true; }
    bool insertLast(int val) { if (isFull()) return false; dq[rear] = val; rear = (rear + 1) % cap; sz++; return true; }
    bool deleteFront() { if (isEmpty()) return false; front = (front + 1) % cap; sz--; return true; }
    bool deleteLast() { if (isEmpty()) return false; rear = (rear - 1 + cap) % cap; sz--; return true; }
    int getFront() { return isEmpty() ? -1 : dq[front]; }
    int getRear() { return isEmpty() ? -1 : dq[(rear - 1 + cap) % cap]; }
    bool isEmpty() { return sz == 0; }
    bool isFull() { return sz == cap; }
};