Monotonic order, mins, and recency

Simple — read this first

int[] nextGreaterRtl(int[] a) {
    int n = a.length;
    int[] ans = new int[n];
    Deque<Integer> st = new ArrayDeque<>(); // values, decreasing toward the top
    for (int i = n - 1; i >= 0; i--) {      // walk from the right so the stack is "what is to my right"
        while (!st.isEmpty() && st.peek() <= a[i]) st.pop(); // not strictly greater — discard
        ans[i] = st.isEmpty() ? -1 : st.peek();              // top is the nearest greater to the right
        st.push(a[i]);                                       // we become a candidate for the left
    }
    return ans;
}

Interview — type this

int[] nextGreater(int[] a) {
    int n = a.length;
    int[] ans = new int[n];
    Arrays.fill(ans, -1);                   // leftover indices never find a greater
    Deque<Integer> st = new ArrayDeque<>(); // indices; a[st] is decreasing toward the top
    for (int i = 0; i < n; i++) {           // left to right: i is a candidate "next greater" for waiters
        while (!st.isEmpty() && a[st.peek()] < a[i]) {
            ans[st.pop()] = a[i];           // popped index just found its next greater
        }
        st.push(i);                         // i still waits for someone greater than a[i]
    }
    return ans;                             // anything still on the stack keeps -1
}

Simple — read this first

class MinStackPair {
    Deque<int[]> st = new ArrayDeque<>(); // [value, minSoFar]
    void push(int x) {
        int m = st.isEmpty() ? x : Math.min(x, st.peek()[1]);
        st.push(new int[]{x, m});         // min rides along with this height
    }
    void pop() { st.pop(); }
    int top() { return st.peek()[0]; }
    int getMin() { return st.peek()[1]; } // O(1) — no scan
}

Interview — type this

class MinStack {
    Deque<Integer> st = new ArrayDeque<>();
    Deque<Integer> mins = new ArrayDeque<>(); // mins.peek() = getMin of current st
    void push(int x) {
        st.push(x);
        mins.push(mins.isEmpty() ? x : Math.min(x, mins.peek())); // duplicate mins still pushed
    }
    void pop() { st.pop(); mins.pop(); }
    int top() { return st.peek(); }
    int getMin() { return mins.peek(); }
}

Simple — read this first

int[] maxWindowBrute(int[] a, int k) {
    int n = a.length;
    int[] ans = new int[n - k + 1];
    for (int i = 0; i + k <= n; i++) {   // each window start
        int m = a[i];
        for (int j = i + 1; j < i + k; j++) m = Math.max(m, a[j]);
        ans[i] = m;
    }
    return ans; // O(n k) — fine to type first, then upgrade
}

Interview — type this

int[] maxSlidingWindow(int[] a, int k) {
    int n = a.length;
    int[] ans = new int[n - k + 1];
    Deque<Integer> dq = new ArrayDeque<>(); // indices; a[idx] decreasing front → back
    for (int i = 0; i < n; i++) {
        if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst(); // slid out of the window
        while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast(); // useless as max
        dq.offerLast(i);
        if (i >= k - 1) ans[i - k + 1] = a[dq.peekFirst()]; // front is the window max
    }
    return ans;
}

Simple — read this first

class LRUSimple {
    static class Node {
        int k, v;
        Node prev, next;
        Node(int k, int v) { this.k = k; this.v = v; }
    }
    int cap;
    Map<Integer, Node> map = new HashMap<>();
    Node head, tail; // head = MRU, tail = LRU; null edges instead of dummies
    LRUSimple(int cap) { this.cap = cap; }
    void moveToFront(Node n) {         // sketch: unlink, then n becomes head
        if (n == head) return;
        if (n.prev != null) n.prev.next = n.next;
        if (n.next != null) n.next.prev = n.prev;
        if (n == tail) tail = n.prev;
        n.prev = null;
        n.next = head;
        if (head != null) head.prev = n;
        head = n;
        if (tail == null) tail = n;
    }
    int get(int k) {
        Node n = map.get(k);
        if (n == null) return -1;
        moveToFront(n);
        return n.v;
    }
    void put(int k, int v) {
        Node n = map.get(k);
        if (n != null) { n.v = v; moveToFront(n); return; }
        n = new Node(k, v);
        map.put(k, n);
        moveToFront(n);
        if (map.size() > cap) {        // evict tail — interview dummies skip these nulls
            map.remove(tail.k);
            Node gone = tail;
            tail = gone.prev;
            if (tail != null) tail.next = null;
            else head = null;
        }
    }
}

Interview — type this

class LRUCache {
    static class Node {
        int k, v;
        Node prev, next;
        Node(int k, int v) { this.k = k; this.v = v; }
    }
    int cap;
    Map<Integer, Node> map = new HashMap<>();
    Node head = new Node(0, 0), tail = new Node(0, 0); // dummies: never evict these
    LRUCache(int cap) {
        this.cap = cap;
        head.next = tail;
        tail.prev = head;
    }
    void unlink(Node n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }
    void insertAfterHead(Node n) {     // new MRU
        n.next = head.next;
        n.prev = head;
        head.next.prev = n;
        head.next = n;
    }
    int get(int key) {
        Node n = map.get(key);
        if (n == null) return -1;
        unlink(n);
        insertAfterHead(n);
        return n.v;
    }
    void put(int key, int val) {
        Node n = map.get(key);
        if (n != null) { n.v = val; unlink(n); insertAfterHead(n); return; }
        Node x = new Node(key, val);
        map.put(key, x);
        insertAfterHead(x);
        if (map.size() > cap) {
            Node lru = tail.prev;      // real LRU sits just before dummy tail
            unlink(lru);
            map.remove(lru.k);
        }
    }
}