Data Structure Designs

Overview

Data structure design problems begin with an interface and a performance contract. Before choosing an implementation, list every operation, its required complexity, and the information it must answer. The final structure is often a combination of standard structures rather than a new structure built from scratch.

The most important concept is the invariant connecting those structures. If an array stores values and a hash map stores their indexes, every swap must update the map. If a map points to nodes in a linked list, removing a node must update both representations. If a heap contains historical entries, a separate map must identify which entry is still current.

Recurring patterns in this post include:

  • Hash map plus dense array: the array provides indexing or random access, while the map locates an item in O(1). Swap-with-last removal keeps the array dense.
  • Hash map plus doubly linked list: the map locates a node, while the list maintains recency or ordered buckets. Sentinel nodes eliminate most boundary cases.
  • Two containers or a circular array: two stacks reverse order lazily, while head, tail, and size indexes implement a bounded queue without shifting elements.
  • Buffered or flattened iterators: cache the next item for peeking, or flatten nested input before iteration when eager O(n) preprocessing is acceptable.
  • Timestamped or versioned histories: append changes in chronological order and use binary search to retrieve the latest value at or before a requested time.
  • Frequency buckets: group values by frequency so the current minimum, maximum, or most recent value at a frequency can be found directly.
  • Intervals: represent free space with half-open ranges, allocate from a fitting interval, and merge touching ranges after memory is released.
  • Authoritative map plus lazy heap: update the map immediately, push new heap entries, and discard stale entries only when they reach the top.

Most design bugs occur during mutation, when two internal representations briefly disagree. Write each modifying operation as a sequence that restores every invariant before returning. Track logical state such as size explicitly instead of inferring it from stored values, and distinguish worst-case from amortized complexity: lazy stack transfers and stale-heap cleanup may occasionally do extra work, but each old entry is processed only a limited number of times.

Templates

There is no universal data-structure-design template. The following patterns capture the most reusable combinations in this post.

Hash map plus dense array

  • Keep values in a dense array and map each value to its current index.
  • Insert at the end and record the new index.
  • To remove a value, move the final value into its index, update the moved value’s index, and pop the last slot.
  • Never mutate the array without making the corresponding map update.
import java.util.*;

class DenseIndexTemplate {
    private final List<Integer> values = new ArrayList<>();
    private final Map<Integer, Integer> valueToIndex = new HashMap<>();

    public boolean add(int value) {
        if (valueToIndex.containsKey(value)) {
            return false;
        }
        valueToIndex.put(value, values.size());
        values.add(value);
        return true;
    }

    public boolean remove(int value) {
        if (!valueToIndex.containsKey(value)) {
            return false;
        }
        int index = valueToIndex.get(value);
        int lastIndex = values.size() - 1;
        int lastValue = values.get(lastIndex);
        values.set(index, lastValue);
        valueToIndex.put(lastValue, index);
        values.remove(lastIndex);
        valueToIndex.remove(value);
        return true;
    }
}

Hash map plus doubly linked ordering

  • Map each key directly to its linked-list node.
  • Use head and tail sentinels so insertion and removal never need special endpoint logic.
  • Reorder an existing key by detaching its node and inserting it at the desired position.
  • When evicting a node, remove it from both the list and the map.
import java.util.HashMap;
import java.util.Map;

class LinkedOrderNode {
    int key;
    LinkedOrderNode prev;
    LinkedOrderNode next;

    LinkedOrderNode(int key) {
        this.key = key;
    }
}

class LinkedOrderTemplate {
    private final Map<Integer, LinkedOrderNode> nodes = new HashMap<>();
    private final LinkedOrderNode head = new LinkedOrderNode(-1);
    private final LinkedOrderNode tail = new LinkedOrderNode(-1);

    public LinkedOrderTemplate() {
        head.next = tail;
        tail.prev = head;
    }

    public void touch(int key) {
        LinkedOrderNode node = nodes.get(key);
        if (node == null) {
            node = new LinkedOrderNode(key);
            nodes.put(key, node);
        } else {
            removeNode(node);
        }
        insertAfter(head, node);
    }

    public int removeLast() {
        if (tail.prev == head) {
            return -1;
        }
        LinkedOrderNode node = tail.prev;
        removeNode(node);
        nodes.remove(node.key);
        return node.key;
    }

    private void removeNode(LinkedOrderNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void insertAfter(LinkedOrderNode prevNode, LinkedOrderNode node) {
        LinkedOrderNode nextNode = prevNode.next;
        prevNode.next = node;
        node.prev = prevNode;
        node.next = nextNode;
        nextNode.prev = node;
    }
}

Authoritative map plus lazy heap

  • Store the current priority for every active ID in a map.
  • On an add or edit, update the map and push a new heap record; do not search the heap for the old record.
  • Remove an item by deleting it from the map.
  • When popping, discard records whose ID is absent or whose priority no longer matches the map.
import java.util.*;

class LazyHeapTemplate {
    private final Map<Integer, Integer> livePriority = new HashMap<>();
    private final PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> {
        if (a[0] != b[0]) {
            return Integer.compare(b[0], a[0]);
        }
        return Integer.compare(b[1], a[1]);
    });

    public void upsert(int id, int priority) {
        livePriority.put(id, priority);
        heap.offer(new int[]{priority, id});
    }

    public void remove(int id) {
        livePriority.remove(id);
    }

    public int popTop() {
        while (!heap.isEmpty()) {
            int[] entry = heap.poll();
            int priority = entry[0];
            int id = entry[1];
            if (!livePriority.containsKey(id) || livePriority.get(id) != priority) {
                continue;
            }
            livePriority.remove(id);
            return id;
        }
        return -1;
    }
}

Append-only history plus binary search

  • Keep a sorted history of (version, value) records for each key or index.
  • Append changes when versions arrive in nondecreasing order.
  • Search for the first version greater than the requested version.
  • Return the record immediately before that boundary.
import java.util.*;

class VersionedHistoryTemplate {
    private final Map<Integer, List<int[]>> history = new HashMap<>();

    public void set(int key, int version, int value) {
        history.computeIfAbsent(key, ignored -> new ArrayList<>())
            .add(new int[]{version, value});
    }

    public int get(int key, int version) {
        if (!history.containsKey(key)) {
            return 0;
        }
        List<int[]> entries = history.get(key);
        int left = 0;
        int right = entries.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (entries.get(mid)[0] <= version) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left == 0 ? 0 : entries.get(left - 1)[1];
    }
}

Problems

146. LRU Cache

Combine a key-to-node hash map with a doubly linked list ordered by recency. The node after head is most recently used, and the node before tail is least recently used. A successful get or an existing-key put moves its node to the front; inserting a new key into a full cache evicts the last node before adding the replacement, so the cache never exceeds capacity. Both operations run in O(1).

import java.util.HashMap;
import java.util.Map;

class ListNode {
    int key;
    int val;
    ListNode prev;
    ListNode next;

    ListNode(int key, int val) {
        this.key = key;
        this.val = val;
    }
}

class LRUCache {
    private final int capacity;
    private final ListNode head;
    private final ListNode tail;
    private final Map<Integer, ListNode> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.head = new ListNode(0, 0);
        this.tail = new ListNode(0, 0);
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.cache = new HashMap<>();
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        ListNode node = cache.get(key);
        removeNode(node);
        addFront(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (cache.size() == capacity && !cache.containsKey(key)) {
            // Evict before insertion so the cache never exceeds its capacity.
            ListNode lastNode = tail.prev;
            int lastKey = lastNode.key;
            removeNode(lastNode);
            cache.remove(lastKey);
        }

        ListNode node;
        if (!cache.containsKey(key)) {
            node = new ListNode(key, value);
            cache.put(key, node);
        } else {
            node = cache.get(key);
            node.val = value;
            removeNode(node);
        }

        addFront(node);
    }

    private void removeNode(ListNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.next = null;
        node.prev = null;
    }

    private void addFront(ListNode node) {
        ListNode tmp = head.next;
        head.next = node;
        node.prev = head;
        node.next = tmp;
        tmp.prev = node;
    }
}

232. Implement Queue Using Stacks

Use one stack for newly pushed values and another stack for values ready to leave the queue. Transfer all values from the input stack only when the output stack is empty; the reversal exposes the oldest value. Each value is pushed and transferred at most once before removal, giving amortized O(1) queue operations.

import java.util.ArrayDeque;
import java.util.Deque;

class MyQueue {
    private final Deque<Integer> stack;
    private final Deque<Integer> queue;

    public MyQueue() {
        this.stack = new ArrayDeque<>(); // push to stack
        this.queue = new ArrayDeque<>(); // pop from queue
    }

    public void push(int x) {
        stack.offerLast(x);
    }

    public int pop() {
        if (queue.isEmpty()) {
            transfer();
        }
        return queue.pollLast();
    }

    public int peek() {
        if (queue.isEmpty()) {
            transfer();
        }
        return queue.peekLast();
    }

    private void transfer() {
        while (!stack.isEmpty()) {
            queue.offerLast(stack.pollLast());
        }
    }

    public boolean empty() {
        return stack.isEmpty() && queue.isEmpty();
    }
}

284. Peeking Iterator

Prefetch one value from the wrapped iterator and store it in next_val with a separate availability flag. peek returns the buffered value without advancing, while next returns it and immediately refills the buffer. Every operation uses O(1) time and the wrapper stores only one extra value.

import java.util.Iterator;

class PeekingIterator implements Iterator<Integer> {
    private final Iterator<Integer> iterator;
    // Do not name instance variables the same as methods.
    private Integer nextVal;
    private boolean hasNext;

    public PeekingIterator(Iterator<Integer> iterator) {
        this.iterator = iterator;
        this.nextVal = null;
        this.hasNext = false;
        if (this.iterator.hasNext()) {
            this.nextVal = this.iterator.next();
            this.hasNext = true;
        }
    }

    public Integer peek() {
        return nextVal;
    }

    @Override
    public Integer next() {
        if (!hasNext) {
            return null;
        }

        int val = nextVal;
        if (iterator.hasNext()) {
            nextVal = iterator.next();
            hasNext = true;
        } else {
            nextVal = null;
            hasNext = false;
        }
        return val;
    }

    @Override
    public boolean hasNext() {
        return hasNext;
    }
}

341. Flatten Nested List Iterator

This solution eagerly traverses the nested list with DFS and stores every integer in left-to-right order. The constructor takes O(n) time and space for n integers, after which next and hasNext are O(1). This favors simple iteration over a lazy iterator that would flatten values only when requested.

import java.util.*;

class NestedIterator implements Iterator<Integer> {
    private final List<Integer> vals;
    private int idx;
    private final int size;

    public NestedIterator(List<NestedInteger> nestedList) {
        this.vals = new ArrayList<>();
        dfs(nestedList);
        this.idx = 0;
        this.size = vals.size();
    }

    private void dfs(List<NestedInteger> nList) {
        for (NestedInteger n : nList) {
            if (n.isInteger()) {
                vals.add(n.getInteger());
            } else {
                dfs(n.getList());
            }
        }
    }

    @Override
    public Integer next() {
        int val = vals.get(idx);
        idx += 1;
        return val;
    }

    @Override
    public boolean hasNext() {
        if (idx < size) {
            return true;
        } else {
            return false;
        }
    }
}

362. Design Hit Counter

Group hits with the same timestamp into one deque bucket and maintain a running total. During getHits(timestamp), remove buckets at or before timestamp - 300 and subtract their counts. Each bucket enters and leaves the deque once, so hit recording is O(1) and retrieval is amortized O(1).

import java.util.ArrayDeque;
import java.util.Deque;

class HitCounter {
    private final Deque<int[]> dq;
    private int total;

    public HitCounter() {
        this.dq = new ArrayDeque<>();
        this.total = 0;
    }

    public void hit(int timestamp) {
        if (!dq.isEmpty() && timestamp == dq.peekLast()[0]) {
            dq.peekLast()[1] += 1;
        } else {
            dq.offerLast(new int[]{timestamp, 1});
        }
        total += 1;
    }

    public int getHits(int timestamp) {
        while (!dq.isEmpty() && dq.peekFirst()[0] <= timestamp - 300) {
            int[] previous = dq.pollFirst();
            int prevCount = previous[1];
            total -= prevCount;
        }
        return total;
    }
}

380. Insert Delete GetRandom O(1)

Store values in a dense array for uniform random indexing and map each value to its array index. Removal swaps the target with the final value, updates the moved value’s index, and pops the last slot. This synchronization gives average O(1) insertion, removal, and random selection.

import java.util.*;

class RandomizedSet {
    private final Map<Integer, Integer> valToIdx;
    private final List<Integer> values;
    private final Random random;

    public RandomizedSet() {
        this.valToIdx = new HashMap<>();
        this.values = new ArrayList<>();
        this.random = new Random();
    }

    public boolean insert(int val) {
        if (valToIdx.containsKey(val)) {
            return false;
        } else {
            valToIdx.put(val, values.size());
            values.add(val);
            return true;
        }
    }

    public boolean remove(int val) {
        if (!valToIdx.containsKey(val)) {
            return false;
        } else {
            int idx = valToIdx.get(val);
            int lastIdx = values.size() - 1;
            int lastVal = values.get(lastIdx);
            values.set(idx, lastVal);
            values.set(lastIdx, val);
            valToIdx.put(lastVal, idx);
            values.remove(lastIdx);
            valToIdx.remove(val);
            return true;
        }
    }

    public int getRandom() {
        int N = values.size();
        return values.get(random.nextInt(N));
    }
}

432. All O`one Data Structure

Maintain a doubly linked list of frequency buckets in increasing count order. Each bucket stores a set of keys, while a hash map points every key directly to its current bucket. Incrementing or decrementing moves a key only to an adjacent bucket, empty buckets are removed, and the first and last buckets expose a minimum or maximum key in O(1).

import java.util.*;

class Node {
    int count;
    Set<String> keys;
    Node prev;
    Node next;

    Node(int count) {
        this.count = count;
        this.keys = new HashSet<>();
    }
}

class AllOne {
    private final Map<String, Node> keyToNode;
    private final Node head;
    private final Node tail;

    public AllOne() {
        this.keyToNode = new HashMap<>();
        this.head = new Node(-1);
        this.tail = new Node(-1);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    public void inc(String key) {
        if (!keyToNode.containsKey(key)) {
            Node firstNode = head.next;
            if (firstNode.count == 1) {
                firstNode.keys.add(key);
                keyToNode.put(key, firstNode);
            } else {
                Node newNode = new Node(1);
                newNode.keys.add(key);
                insertAfter(head, newNode);
                keyToNode.put(key, newNode);
            }
            return;
        }

        // Handle an existing key below.
        Node keyNode = keyToNode.get(key);
        int keyCount = keyNode.count;
        Node nextNode = keyNode.next;
        keyNode.keys.remove(key);
        if (keyNode.keys.isEmpty()) {
            remove(keyNode);
        }
        if (nextNode.count == keyCount + 1) {
            nextNode.keys.add(key);
            keyToNode.put(key, nextNode);
        } else {
            Node newNode = new Node(keyCount + 1);
            newNode.keys.add(key);
            insertAfter(nextNode.prev, newNode);
            keyToNode.put(key, newNode);
        }
    }

    public void dec(String key) {
        Node keyNode = keyToNode.get(key);
        int keyCount = keyNode.count;
        Node prevNode = keyNode.prev;
        keyNode.keys.remove(key);
        if (keyNode.keys.isEmpty()) {
            remove(keyNode);
        }

        if (keyCount == 1) {
            keyToNode.remove(key);
            return;
        }

        if (prevNode.count == keyCount - 1) {
            prevNode.keys.add(key);
            keyToNode.put(key, prevNode);
        } else {
            Node newNode = new Node(keyCount - 1);
            newNode.keys.add(key);
            insertAfter(prevNode, newNode);
            keyToNode.put(key, newNode);
        }
    }

    public String getMaxKey() {
        if (tail.prev != head) {
            return tail.prev.keys.iterator().next();
        } else {
            return "";
        }
    }

    public String getMinKey() {
        if (head.next != tail) {
            return head.next.keys.iterator().next();
        } else {
            return "";
        }
    }

    private void remove(Node node) {
        Node prevNode = node.prev;
        Node nextNode = node.next;
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
        node.prev = null;
        node.next = null;
    }

    private void insertAfter(Node prevNode, Node node) {
        Node nextNode = prevNode.next;
        prevNode.next = node;
        node.prev = prevNode;
        node.next = nextNode;
        nextNode.prev = node;
    }
}

622. Design Circular Queue

Use a fixed array with head as the next dequeue index, tail as the next enqueue index, and modulo arithmetic to wrap both indexes. An explicit size determines whether the queue is empty or full; stored values such as 0 or -1 never indicate occupancy. Every operation runs in O(1).

class MyCircularQueue {
    private int[] dq;
    int capacity;
    int size;
    int head; // where to dequeue
    int tail; // where to enqueue

    public MyCircularQueue(int k) {
        dq = new int[k];
        size = 0;
        capacity = k;
        head = 0;
        tail = 0;
    }

    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        dq[tail] = value;
        tail = (1 + tail) % capacity;
        size++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        // int val = dq[head];
        dq[head] = -1;
        head = (1 + head) % capacity;
        size--;
        return true;
    }

    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return dq[head];
    }

    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return dq[(tail - 1 + capacity) % capacity];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }
}

635. Design Log Storage System

Keep (timestamp, ID) records sorted lexicographically. For a query, truncate both endpoints at the requested granularity, append minimum components to the start and maximum components to the end, then use binary search to isolate the inclusive range. Array insertion costs O(n), while retrieval costs O(log n + k) for k returned IDs.

import java.util.*;

class LogEntry {
    String timestamp;
    int id;

    LogEntry(String timestamp, int id) {
        this.timestamp = timestamp;
        this.id = id;
    }
}

class LogSystem {
    private final List<LogEntry> data;
    private final Map<String, Integer> lastIdx;
    private final Map<String, String> minSuffix;
    private final Map<String, String> maxSuffix;

    public LogSystem() {
        this.data = new ArrayList<>();
        this.lastIdx = Map.of(
            "Year", 4,
            "Month", 7,
            "Day", 10,
            "Hour", 13,
            "Minute", 16,
            "Second", 19
        );
        this.minSuffix = Map.of(
            "Year", ":00:00:00:00:00",
            "Month", ":00:00:00:00",
            "Day", ":00:00:00",
            "Hour", ":00:00",
            "Minute", ":00",
            "Second", ""
        );
        this.maxSuffix = Map.of(
            "Year", ":99:99:99:99:99",
            "Month", ":99:99:99:99",
            "Day", ":99:99:99",
            "Hour", ":99:99",
            "Minute", ":99",
            "Second", ""
        );
    }

    public void put(int id, String timestamp) {
        int left = 0;
        int right = data.size();
        while (left < right) {
            int mid = (left + right) / 2;
            LogEntry curr = data.get(mid);
            int comparison = curr.timestamp.compareTo(timestamp);
            if (comparison < 0 || (comparison == 0 && curr.id <= id)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        data.add(left, new LogEntry(timestamp, id));
    }

    public List<Integer> retrieve(String start, String end, String granularity) {
        int last = lastIdx.get(granularity);
        String startStr = start.substring(0, last) + minSuffix.get(granularity);
        String endStr = end.substring(0, last) + maxSuffix.get(granularity);
        int startIdx = lowerBound(startStr);
        if (startIdx == data.size()) {
            return new ArrayList<>();
        }
        int endIdx = upperBound(endStr);
        List<Integer> res = new ArrayList<>();
        for (int i = startIdx; i < endIdx; i++) {
            res.add(data.get(i).id);
        }
        return res;
    }

    private int lowerBound(String target) {
        int left = 0;
        int right = data.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (data.get(mid).timestamp.compareTo(target) < 0) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private int upperBound(String target) {
        int left = 0;
        int right = data.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (data.get(mid).timestamp.compareTo(target) <= 0) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

895. Maximum Frequency Stack

Map each value to its current frequency and each frequency to a stack of values that reached it in push order. max_freq identifies the stack to pop, and that stack automatically resolves ties by recency. Both push and pop run in O(1).

import java.util.*;

class FreqStack {
    private final Map<Integer, Deque<Integer>> freqToStack;
    private final Map<Integer, Integer> numToFreq;
    private int maxFreq;

    public FreqStack() {
        // frequency to a stack of numbers
        this.freqToStack = new HashMap<>();
        this.numToFreq = new HashMap<>();
        this.maxFreq = 0;
    }

    public void push(int val) {
        int valFreq = 1 + numToFreq.getOrDefault(val, 0);
        numToFreq.put(val, valFreq);
        freqToStack.computeIfAbsent(valFreq, ignored -> new ArrayDeque<>()).offerLast(val);
        maxFreq = Math.max(maxFreq, valFreq);
    }

    public int pop() {
        Deque<Integer> stack = freqToStack.get(maxFreq);
        int num = stack.pollLast();
        int numFreq = maxFreq - 1;
        if (stack.isEmpty()) {
            freqToStack.remove(maxFreq);
            maxFreq -= 1;
        }
        numToFreq.put(num, numFreq);
        return num;
    }
}

981. Time Based Key-Value Store

Because timestamps for each key arrive in increasing order, append them and their values to parallel per-key arrays. A lookup uses bisect_left(timestamp + 1) to find the first later timestamp and returns the preceding value. set is O(1), and get is O(log n) for that key’s history.

import java.util.*;

class TimeMap {
    private final Map<String, List<Integer>> keyToTime;
    private final Map<String, List<String>> keyToValue;

    public TimeMap() {
        this.keyToTime = new HashMap<>();
        this.keyToValue = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        keyToTime.computeIfAbsent(key, ignored -> new ArrayList<>()).add(timestamp);
        keyToValue.computeIfAbsent(key, ignored -> new ArrayList<>()).add(value);
    }

    public String get(String key, int timestamp) {
        if (!keyToTime.containsKey(key)) {
            return "";
        }
        List<Integer> times = keyToTime.get(key);
        List<String> values = keyToValue.get(key);
        // Using 1 + timestamp here saves many corner cases.
        int idx = lowerBound(times, 1 + timestamp);
        if (idx == 0) {
            return "";
        }
        return values.get(idx - 1);
    }

    private int lowerBound(List<Integer> values, int target) {
        int left = 0;
        int right = values.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (values.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

1146. Snapshot Array

Store an append-only history of (snapshot ID, value) pairs for each index rather than copying the entire array. set appends under the current snapshot, snap advances a global ID, and get uses binary search to find the latest record at or before the requested snapshot. Updates and snapshots are O(1), while retrieval is O(log u) for u updates at that index.

import java.util.ArrayList;
import java.util.List;

class SnapshotArray {
    private int snapId;
    // data[i] is a list of {snapId, value} pairs.
    private final List<List<int[]>> data;

    public SnapshotArray(int length) {
        this.snapId = 0;
        this.data = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            List<int[]> history = new ArrayList<>();
            history.add(new int[]{0, 0});
            data.add(history);
        }
    }

    public void set(int index, int val) {
        data.get(index).add(new int[]{snapId, val});
    }

    public int snap() {
        snapId += 1;
        return snapId - 1;
    }

    public int get(int index, int snapId) {
        List<int[]> history = data.get(index);
        int ptr = lowerBound(history, 1 + snapId);
        return history.get(ptr - 1)[1];
    }

    private int lowerBound(List<int[]> history, int target) {
        int left = 0;
        int right = history.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (history.get(mid)[0] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

2502. Design Memory Allocator

Represent free memory as half-open intervals and keep every allocated interval grouped by mID. Allocation scans for the first fitting free range and consumes space from its left edge. Freeing an ID returns all of its intervals, then sorts and merges overlapping or touching ranges. With f free intervals, allocation is O(f) and merging is O(f log f).

import java.util.*;

class Allocator {
    // Free intervals are half-open: [start, end).
    private List<int[]> free;
    private final Map<Integer, List<int[]>> used;

    public Allocator(int n) {
        this.free = new ArrayList<>();
        this.free.add(new int[]{0, n});
        this.used = new HashMap<>(); // mID -> list of [start, end)
    }

    public int allocate(int size, int mID) {
        for (int idx = 0; idx < free.size(); idx++) {
            int[] interval = free.get(idx);
            int start = interval[0];
            int end = interval[1];
            if (end - start >= size) {
                used.computeIfAbsent(mID, ignored -> new ArrayList<>())
                    .add(new int[]{start, start + size});
                // It is fine to leave an empty range such as [5, 5).
                free.set(idx, new int[]{start + size, end});
                return start;
            }
        }
        return -1;
    }

    public int freeMemory(int mID) {
        // Check first.
        if (!used.containsKey(mID)) {
            return 0;
        }

        int total = 0;
        for (int[] interval : used.get(mID)) {
            int start = interval[0];
            int end = interval[1];
            total += end - start;
            free.add(interval);
        }
        used.remove(mID);
        free = merge(free);
        return total;
    }

    private List<int[]> merge(List<int[]> intervals) {
        intervals.sort((a, b) -> {
            int startComparison = Integer.compare(a[0], b[0]);
            return startComparison != 0
                ? startComparison
                : Integer.compare(a[1], b[1]);
        });
        List<int[]> res = new ArrayList<>();
        for (int[] interval : intervals) {
            int start = interval[0];
            int end = interval[1];
            // Must be >, not >=.
            if (res.isEmpty() || start > res.get(res.size() - 1)[1]) {
                res.add(new int[]{start, end});
            } else {
                int[] previous = res.get(res.size() - 1);
                previous[1] = Math.max(previous[1], end);
            }
        }
        return res;
    }
}

3408. Design Task Manager

Treat the hash map from task ID to current (priority, user ID) as authoritative, and keep (priority, task ID) snapshots in a max-heap. Adds and edits push a new snapshot, removals only delete from the map, and execTop discards heap records that no longer match current map state. This lazy deletion avoids arbitrary heap removal while preserving highest-priority and highest-task-ID ordering.

import java.util.*;

class TaskManager {
    // taskId to [priority, userId]
    private Map<Integer, int[]> taskInfo;
    // [priority, taskId]
    private PriorityQueue<int[]> heap;

    public TaskManager(List<List<Integer>> tasks) {
        taskInfo = new HashMap<>();
        heap = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return b[0] - a[0];
            } else {
                return b[1] - a[1];
            }
        });

        for (List<Integer> task : tasks) {
            int userId = task.get(0);
            int taskId = task.get(1);
            int priority = task.get(2);
            taskInfo.put(taskId, new int[]{priority, userId});
            heap.offer(new int[]{priority, taskId});
        }
    }

    public void add(int userId, int taskId, int priority) {
        taskInfo.put(taskId, new int[]{priority, userId});
        heap.offer(new int[]{priority, taskId});
    }

    public void edit(int taskId, int newPriority) {
        int[] info = taskInfo.get(taskId);
        info[0] = newPriority;
        // Don't forget to add the new task to the heap!
        heap.offer(new int[]{newPriority, taskId});
    }

    public void rmv(int taskId) {
        taskInfo.remove(taskId);
    }

    public int execTop() {
        while (!heap.isEmpty()) {
            int[] task = heap.poll();
            int priority = task[0];
            int taskId = task[1];
            if (!taskInfo.containsKey(taskId) || priority != taskInfo.get(taskId)[0]) {
                continue;
            }
            int userId = taskInfo.get(taskId)[1];
            taskInfo.remove(taskId);
            return userId;
        }
        return -1;
    }
}