2349. Design a Number Container System Solution

Q: Is Design a Number Container System easy or hard?

The problem is rated Medium because the logic requires coordinating multiple data structures and handling updates correctly. The individual operations are simple, but maintaining consistency between mappings and ensuring the smallest index is returned makes it slightly tricky.

Q: Design a Number Container System Python or Java solution

Python implementations typically use a dictionary with heapq for each number and lazy deletion to remove outdated indices. Java solutions often use HashMap combined with TreeSet, allowing direct retrieval of the smallest index using first(). Both achieve O(log n) operations.

Q: How to solve Design a Number Container System in O(log n)?

Maintain two mappings: indexToNumber to track the current value at each index, and numberToIndices which stores all indices for a number in a sorted structure like TreeSet or a min heap. Updates adjust the index membership, while queries return the smallest stored index. Ordered structures ensure O(log n) insertion and removal.

Q: What is the best approach for Design a Number Container System?

The most reliable approach uses a HashMap and an ordered set (such as TreeSet). A map stores index -> number while another map stores number -> sorted set of indices. Each change operation updates both structures and find(number) simply returns the smallest index from the set. Both operations run in O(log n) time with O(n) space.

The problem

Design a number container system that can do the following:

Insert or Replace a number at the given index in the system.
Return the smallest index for the given number in the system.

Implement the NumberContainers class:

NumberContainers() Initializes the number container system.
void change(int index, int number) Fills the container at index with the number. If there is already a number at that index, replace it.
int find(int number) Returns the smallest index for the given number, or -1 if there is no index that is filled by number in the system.

Example 1:

Input
["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"]
[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]
Output
[null, -1, null, null, null, null, 1, null, 2]

Explanation
NumberContainers nc = new NumberContainers();
nc.find(10); // There is no index that is filled with number 10. Therefore, we return -1.
nc.change(2, 10); // Your container at index 2 will be filled with number 10.
nc.change(1, 10); // Your container at index 1 will be filled with number 10.
nc.change(3, 10); // Your container at index 3 will be filled with number 10.
nc.change(5, 10); // Your container at index 5 will be filled with number 10.
nc.find(10); // Number 10 is at the indices 1, 2, 3, and 5. Since the smallest index that is filled with 10 is 1, we return 1.
nc.change(1, 20); // Your container at index 1 will be filled with number 20. Note that index 1 was filled with 10 and then replaced with 20. 
nc.find(10); // Number 10 is at the indices 2, 3, and 5. The smallest index that is filled with 10 is 2. Therefore, we return 2.

Constraints:

1 <= index, number <= 10⁹
At most 10⁵ calls will be made in total to change and find.

Approach overview

Problem Overview: You need to design a data structure that supports two operations: change(index, number) which assigns a number to an index, and find(number) which returns the smallest index currently storing that number. The challenge is handling frequent updates while always retrieving the minimum index efficiently.

Approach 1: HashMap + Ordered Set (O(log n) per operation)

Maintain two structures: a hash map indexToNumber that records the current number stored at each index, and another map numberToIndices where each number points to an ordered set of indices. When change(index, number) is called, check if the index already holds a value. If it does, remove that index from the ordered set of the previous number. Then insert the index into the ordered set of the new number and update indexToNumber. The find(number) operation simply returns the smallest element from the ordered set (e.g., TreeSet.first()). Insertions and removals in the ordered set cost O(log n), while lookups in the hash map are O(1). Space complexity is O(n). This approach relies heavily on hash tables and an ordered set structure.

Approach 2: Two HashMaps + Min Heap with Lazy Cleanup (O(log n) amortized)

Instead of maintaining a perfectly clean ordered set, store indices for each number in a min heap. Use indexToNumber to track the latest value assigned to each index, and numberToHeap where each number maps to a min heap of indices. Every time change(index, number) runs, push the index into the heap for that number and update indexToNumber. Old entries are not removed immediately. During find(number), repeatedly check the heap's top element. If the index at the top no longer maps to that number in indexToNumber, discard it. Continue until a valid index appears or the heap becomes empty. Each heap push or pop costs O(log n), and lazy deletion keeps updates simple. Total space complexity remains O(n). This method uses hash tables and a heap (priority queue).

Recommended for interviews: The ordered set solution is the cleanest and easiest to reason about. Interviewers like it because every structure always stays consistent and each operation has a clear O(log n) bound. The heap-based approach is also acceptable and commonly used in languages without a built-in ordered set. Showing both demonstrates strong understanding of data structure design and tradeoffs between strict ordering and lazy cleanup strategies.

Approach 1: Using HashMaps and SortedMap

In this approach, we use two main data structures:

A map (or dictionary) to track the number at each index. This allows us to efficiently get or update the number for a specific index.
A SortedMap (or TreeMap equivalent) for each unique number to maintain indices in sorted order.

The initial idea is to map each index to its number and, for each number, keep a sorted set of indices where the number occurs. This allows us to quickly access the smallest index for any number.

Python

from sortedcontainers import SortedSet

class NumberContainers:

    def __init__(self):
        self.index_map = {}
        self.number_map = {}

    def change(self, index: int, number: int) -> None:
        if index in self.index_map:
            old_number = self.index_map[index]
            if old_number in self.number_map:
                self.number_map[old_number].discard(index)
                if not self.number_map[old_number]:
                    del self.number_map[old_number]
        self.index_map[index] = number
        if number not in self.number_map:
            self.number_map[number] = SortedSet()
        self.number_map[number].add(index)

    def find(self, number: int) -> int:
        if number in self.number_map and self.number_map[number]:
            return self.number_map[number][0]
        return -1

Java

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

class NumberContainers {
    private Map<Integer, Integer> indexMap = new HashMap<>();
    private Map<Integer, TreeSet<Integer>> numberMap = new HashMap<>();

    public void change(int index, int number) {
        if (indexMap.containsKey(index)) {
            int oldNumber = indexMap.get(index);
            numberMap.get(oldNumber).remove(index);
            if (numberMap.get(oldNumber).isEmpty()) {
                numberMap.remove(oldNumber);
            }
        }
        indexMap.put(index, number);
        numberMap.computeIfAbsent(number, k -> new TreeSet<>()).add(index);
    }

    public int find(int number) {
        if (numberMap.containsKey(number) && !numberMap.get(number).isEmpty()) {
            return numberMap.get(number).first();
        }
        return -1;
    }
}

This Python implementation uses the sortedcontainers library to efficiently maintain a sorted set of indices for each number. The change method updates the current index with the new number and ensures indices for the old number are updated. The find method returns the smallest index from the sorted set.

Complexity

Time Complexity:
change: O(log N), where N is the number of indices tracked for a number.
find: O(1) on average since accessing the minimum index is direct.
Space Complexity: O(N + M), where N is the number of indices and M is the number of unique numbers.

Try this approach in the editor

Approach 2: Using Two HashMaps

In this approach, we can optimize by using two hash maps:

indexToNumber to map each index to its current number.
numberToIndices to map each number to a min-heap of indices (using a custom data structure).

This provides efficient data management for the system with an alternative focus on comprehensive hash map manipulation.

C++

#include <unordered_map>
#include <set>

class NumberContainers {
public:
    std::unordered_map<int, int> indexToNumber;
    std::unordered_map<int, std::set<int>> numberToIndices;

    void change(int index, int number) {
        if (indexToNumber.count(index)) {
            int oldNumber = indexToNumber[index];
            numberToIndices[oldNumber].erase(index);
            if (numberToIndices[oldNumber].empty()) {
                numberToIndices.erase(oldNumber);
            }
        }
        indexToNumber[index] = number;
        numberToIndices[number].insert(index);
    }

    int find(int number) {
        if (numberToIndices.count(number) && !numberToIndices[number].empty()) {
            return *numberToIndices[number].begin();
        }
        return -1;
    }
};

JavaScript

class NumberContainers {
    constructor() {
        this.indexToNumber = new Map();
        this.numberToIndices = new Map();
    }

    change(index, number) {
        if (this.indexToNumber.has(index)) {
            const oldNumber = this.indexToNumber.get(index);
            this.numberToIndices.get(oldNumber).delete(index);
            if (this.numberToIndices.get(oldNumber).size === 0) {
                this.numberToIndices.delete(oldNumber);
            }
        }
        this.indexToNumber.set(index, number);
        if (!this.numberToIndices.has(number)) {
            this.numberToIndices.set(number, new Set());
        }
        this.numberToIndices.get(number).add(index);
    }

    find(number) {
        if (this.numberToIndices.has(number) && this.numberToIndices.get(number).size > 0) {
            return Math.min(...this.numberToIndices.get(number));
        }
        return -1;
    }
}

This C++ implementation uses an unordered map to track the number at each index and a set for sorted index tracking for each number. Both data structures allow for efficient operations on updates and retrievals.

Complexity

Time Complexity:
change: O(log N) due to set operations.
find: O(1) by accessing the first element of a set.
Space Complexity: O(N + M), where N and M are sizes of index and number maps.

Try this approach in the editor

Approach 3: Hash Table + Ordered Set

We use a hash table d to record the mapping relationship between indices and numbers, and another hash table g to record the set of indices corresponding to each number. Here, we can use an ordered set to store the indices, which allows us to conveniently find the smallest index.

When calling the change method, we first check if the index already exists. If it does, we remove the original number from its corresponding index set and then add the new number to the corresponding index set. The time complexity is O(log n).

When calling the find method, we simply return the first element of the index set corresponding to the number. The time complexity is O(1).

The space complexity is O(n), where n is the number of numbers.

TypeScript

class NumberContainers {
    private d = new Map<number, number>();
    private g = new Map<number, TreeSet<number>>();
    constructor() {}

    change(index: number, number: number): void {
        if (this.d.has(index)) {
            const oldNumber = this.d.get(index)!;
            this.g.get(oldNumber)!.delete(index);
            if (!this.g.get(oldNumber)!.size()) {
                this.g.delete(oldNumber);
            }
        }
        this.d.set(index, number);
        if (!this.g.has(number)) {
            this.g.set(number, new TreeSet());
        }
        this.g.get(number)!.add(index);
    }

    find(number: number): number {
        return this.g.has(number) ? this.g.get(number)!.first()! : -1;
    }
}

type Compare<T> = (lhs: T, rhs: T) => number;

class RBTreeNode<T = number> {
    data: T;
    count: number;
    left: RBTreeNode<T> | null;
    right: RBTreeNode<T> | null;
    parent: RBTreeNode<T> | null;
    color: number;
    constructor(data: T) {
        this.data = data;
        this.left = this.right = this.parent = null;
        this.color = 0;
        this.count = 1;
    }

    sibling(): RBTreeNode<T> | null {
        if (!this.parent) return null; // sibling null if no parent
        return this.isOnLeft() ? this.parent.right : this.parent.left;
    }

    isOnLeft(): boolean {
        return this === this.parent!.left;
    }

    hasRedChild(): boolean {
        return (
            Boolean(this.left && this.left.color === 0) ||
            Boolean(this.right && this.right.color === 0)
        );
    }
}

class RBTree<T> {
    root: RBTreeNode<T> | null;
    lt: (l: T, r: T) => boolean;
    constructor(compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)) {
        this.root = null;
        this.lt = (l: T, r: T) => compare(l, r) < 0;
    }

    rotateLeft(pt: RBTreeNode<T>): void {
        const right = pt.right!;
        pt.right = right.left;

        if (pt.right) pt.right.parent = pt;
        right.parent = pt.parent;

        if (!pt.parent) this.root = right;
        else if (pt === pt.parent.left) pt.parent.left = right;
        else pt.parent.right = right;

        right.left = pt;
        pt.parent = right;
    }

    rotateRight(pt: RBTreeNode<T>): void {
        const left = pt.left!;
        pt.left = left.right;

        if (pt.left) pt.left.parent = pt;
        left.parent = pt.parent;

        if (!pt.parent) this.root = left;
        else if (pt === pt.parent.left) pt.parent.left = left;
        else pt.parent.right = left;

        left.right = pt;
        pt.parent = left;
    }

    swapColor(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
        const tmp = p1.color;
        p1.color = p2.color;
        p2.color = tmp;
    }

    swapData(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
        const tmp = p1.data;
        p1.data = p2.data;
        p2.data = tmp;
    }

    fixAfterInsert(pt: RBTreeNode<T>): void {
        let parent = null;
        let grandParent = null;

        while (pt !== this.root && pt.color !== 1 && pt.parent?.color === 0) {
            parent = pt.parent;
            grandParent = pt.parent.parent;

            /*  Case : A
                Parent of pt is left child of Grand-parent of pt */
            if (parent === grandParent?.left) {
                const uncle = grandParent.right;

                /* Case : 1
                   The uncle of pt is also red
                   Only Recoloring required */
                if (uncle && uncle.color === 0) {
                    grandParent.color = 0;
                    parent.color = 1;
                    uncle.color = 1;
                    pt = grandParent;
                } else {
                    /* Case : 2
                       pt is right child of its parent
                       Left-rotation required */
                    if (pt === parent.right) {
                        this.rotateLeft(parent);
                        pt = parent;
                        parent = pt.parent;
                    }

                    /* Case : 3
                       pt is left child of its parent
                       Right-rotation required */
                    this.rotateRight(grandParent);
                    this.swapColor(parent!, grandParent);
                    pt = parent!;
                }
            } else {
                /* Case : B
               Parent of pt is right child of Grand-parent of pt */
                const uncle = grandParent!.left;

                /*  Case : 1
                    The uncle of pt is also red
                    Only Recoloring required */
                if (uncle != null && uncle.color === 0) {
                    grandParent!.color = 0;
                    parent.color = 1;
                    uncle.color = 1;
                    pt = grandParent!;
                } else {
                    /* Case : 2
                       pt is left child of its parent
                       Right-rotation required */
                    if (pt === parent.left) {
                        this.rotateRight(parent);
                        pt = parent;
                        parent = pt.parent;
                    }

                    /* Case : 3
                       pt is right child of its parent
                       Left-rotation required */
                    this.rotateLeft(grandParent!);
                    this.swapColor(parent!, grandParent!);
                    pt = parent!;
                }
            }
        }
        this.root!.color = 1;
    }

    delete(val: T): boolean {
        const node = this.find(val);
        if (!node) return false;
        node.count--;
        if (!node.count) this.deleteNode(node);
        return true;
    }

    deleteAll(val: T): boolean {
        const node = this.find(val);
        if (!node) return false;
        this.deleteNode(node);
        return true;
    }

    deleteNode(v: RBTreeNode<T>): void {
        const u = BSTreplace(v);

        // True when u and v are both black
        const uvBlack = (u === null || u.color === 1) && v.color === 1;
        const parent = v.parent!;

        if (!u) {
            // u is null therefore v is leaf
            if (v === this.root) this.root = null;
            // v is root, making root null
            else {
                if (uvBlack) {
                    // u and v both black
                    // v is leaf, fix double black at v
                    this.fixDoubleBlack(v);
                } else {
                    // u or v is red
                    if (v.sibling()) {
                        // sibling is not null, make it red"
                        v.sibling()!.color = 0;
                    }
                }
                // delete v from the tree
                if (v.isOnLeft()) parent.left = null;
                else parent.right = null;
            }
            return;
        }

        if (!v.left || !v.right) {
            // v has 1 child
            if (v === this.root) {
                // v is root, assign the value of u to v, and delete u
                v.data = u.data;
                v.left = v.right = null;
            } else {
                // Detach v from tree and move u up
                if (v.isOnLeft()) parent.left = u;
                else parent.right = u;
                u.parent = parent;
                if (uvBlack) this.fixDoubleBlack(u);
                // u and v both black, fix double black at u
                else u.color = 1; // u or v red, color u black
            }
            return;
        }

        // v has 2 children, swap data with successor and recurse
        this.swapData(u, v);
        this.deleteNode(u);

        // find node that replaces a deleted node in BST
        function BSTreplace(x: RBTreeNode<T>): RBTreeNode<T> | null {
            // when node have 2 children
            if (x.left && x.right) return successor(x.right);
            // when leaf
            if (!x.left && !x.right) return null;
            // when single child
            return x.left ?? x.right;
        }
        // find node that do not have a left child
        // in the subtree of the given node
        function successor(x: RBTreeNode<T>): RBTreeNode<T> {
            let temp = x;
            while (temp.left) temp = temp.left;
            return temp;
        }
    }

    fixDoubleBlack(x: RBTreeNode<T>): void {
        if (x === this.root) return; // Reached root

        const sibling = x.sibling();
        const parent = x.parent!;
        if (!sibling) {
            // No sibiling, double black pushed up
            this.fixDoubleBlack(parent);
        } else {
            if (sibling.color === 0) {
                // Sibling red
                parent.color = 0;
                sibling.color = 1;
                if (sibling.isOnLeft()) this.rotateRight(parent);
                // left case
                else this.rotateLeft(parent); // right case
                this.fixDoubleBlack(x);
            } else {
                // Sibling black
                if (sibling.hasRedChild()) {
                    // at least 1 red children
                    if (sibling.left && sibling.left.color === 0) {
                        if (sibling.isOnLeft()) {
                            // left left
                            sibling.left.color = sibling.color;
                            sibling.color = parent.color;
                            this.rotateRight(parent);
                        } else {
                            // right left
                            sibling.left.color = parent.color;
                            this.rotateRight(sibling);
                            this.rotateLeft(parent);
                        }
                    } else {
                        if (sibling.isOnLeft()) {
                            // left right
                            sibling.right!.color = parent.color;
                            this.rotateLeft(sibling);
                            this.rotateRight(parent);
                        } else {
                            // right right
                            sibling.right!.color = sibling.color;
                            sibling.color = parent.color;
                            this.rotateLeft(parent);
                        }
                    }
                    parent.color = 1;
                } else {
                    // 2 black children
                    sibling.color = 0;
                    if (parent.color === 1) this.fixDoubleBlack(parent);
                    else parent.color = 1;
                }
            }
        }
    }

    insert(data: T): boolean {
        // search for a position to insert
        let parent = this.root;
        while (parent) {
            if (this.lt(data, parent.data)) {
                if (!parent.left) break;
                else parent = parent.left;
            } else if (this.lt(parent.data, data)) {
                if (!parent.right) break;
                else parent = parent.right;
            } else break;
        }

        // insert node into parent
        const node = new RBTreeNode(data);
        if (!parent) this.root = node;
        else if (this.lt(node.data, parent.data)) parent.left = node;
        else if (this.lt(parent.data, node.data)) parent.right = node;
        else {
            parent.count++;
            return false;
        }
        node.parent = parent;
        this.fixAfterInsert(node);
        return true;
    }

    find(data: T): RBTreeNode<T> | null {
        let p = this.root;
        while (p) {
            if (this.lt(data, p.data)) {
                p = p.left;
            } else if (this.lt(p.data, data)) {
                p = p.right;
            } else break;
        }
        return p ?? null;
    }

    *inOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
        if (!root) return;
        for (const v of this.inOrder(root.left!)) yield v;
        yield root.data;
        for (const v of this.inOrder(root.right!)) yield v;
    }

    *reverseInOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
        if (!root) return;
        for (const v of this.reverseInOrder(root.right!)) yield v;
        yield root.data;
        for (const v of this.reverseInOrder(root.left!)) yield v;
    }
}

class TreeSet<T = number> {
    _size: number;
    tree: RBTree<T>;
    compare: Compare<T>;
    constructor(
        collection: T[] | Compare<T> = [],
        compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
    ) {
        if (typeof collection === 'function') {
            compare = collection;
            collection = [];
        }
        this._size = 0;
        this.compare = compare;
        this.tree = new RBTree(compare);
        for (const val of collection) this.add(val);
    }

    size(): number {
        return this._size;
    }

    has(val: T): boolean {
        return !!this.tree.find(val);
    }

    add(val: T): boolean {
        const successful = this.tree.insert(val);
        this._size += successful ? 1 : 0;
        return successful;
    }

    delete(val: T): boolean {
        const deleted = this.tree.deleteAll(val);
        this._size -= deleted ? 1 : 0;
        return deleted;
    }

    ceil(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(p.data, val) >= 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    floor(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(val, p.data) >= 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    higher(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(val, p.data) < 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    lower(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(p.data, val) < 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    first(): T | undefined {
        return this.tree.inOrder().next().value;
    }

    last(): T | undefined {
        return this.tree.reverseInOrder().next().value;
    }

    shift(): T | undefined {
        const first = this.first();
        if (first === undefined) return undefined;
        this.delete(first);
        return first;
    }

    pop(): T | undefined {
        const last = this.last();
        if (last === undefined) return undefined;
        this.delete(last);
        return last;
    }

    *[Symbol.iterator](): Generator<T, void, void> {
        for (const val of this.values()) yield val;
    }

    *keys(): Generator<T, void, void> {
        for (const val of this.values()) yield val;
    }

    *values(): Generator<T, undefined, void> {
        for (const val of this.tree.inOrder()) yield val;
        return undefined;
    }

    /**
     * Return a generator for reverse order traversing the set
     */
    *rvalues(): Generator<T, undefined, void> {
        for (const val of this.tree.reverseInOrder()) yield val;
        return undefined;
    }
}

/**
 * Your NumberContainers object will be instantiated and called as such:
 * var obj = new NumberContainers()
 * obj.change(index,number)
 * var param_2 = obj.find(number)
 */

public class NumberContainers {
    private Dictionary<int, int> d = new Dictionary<int, int>();
    private Dictionary<int, SortedSet<int>> g = new Dictionary<int, SortedSet<int>>();

    public NumberContainers() {
    }

    public void Change(int index, int number) {
        if (d.TryGetValue(index, out int oldNumber)) {
            g[oldNumber].Remove(index);
        }
        d[index] = number;
        if (!g.ContainsKey(number)) {
            g[number] = new SortedSet<int>();
        }
        g[number].Add(index);
    }

    public int Find(int number) {
        if (!g.ContainsKey(number) || g[number].Count == 0) {
            return -1;
        }
        return g[number].Min;
    }
}

/**
 * Your NumberContainers object will be instantiated and called as such:
 * NumberContainers obj = new NumberContainers();
 * obj.Change(index, number);
 * int param_2 = obj.Find(number);
 */

type NumberContainers struct {
	d map[int]int
	g map[int]*redblacktree.Tree
}

func Constructor() NumberContainers {
	return NumberContainers{map[int]int{}, map[int]*redblacktree.Tree{}}
}

func (this *NumberContainers) Change(index int, number int) {
	if oldNumber, ok := this.d[index]; ok {
		this.g[oldNumber].Remove(index)
	}
	this.d[index] = number
	if _, ok := this.g[number]; !ok {
		this.g[number] = redblacktree.NewWithIntComparator()
	}
	this.g[number].Put(index, nil)
}

func (this *NumberContainers) Find(number int) int {
	if ids, ok := this.g[number]; ok && ids.Size() > 0 {
		return ids.Left().Key.(int)
	}
	return -1
}

/**
 * Your NumberContainers object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Change(index,number);
 * param_2 := obj.Find(number);
 */

Rust

use std::collections::{HashMap, BTreeSet};

struct NumberContainers {
    d: HashMap<i32, i32>,
    g: HashMap<i32, BTreeSet<i32>>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl NumberContainers {
    fn new() -> Self {
        Self {
            d: HashMap::new(),
            g: HashMap::new(),
        }
    }

    fn change(&mut self, index: i32, number: i32) {
        if let Some(&old_number) = self.d.get(&index) {
            if let Some(set) = self.g.get_mut(&old_number) {
                set.remove(&index);
            }
        }
        self.d.insert(index, number);
        self.g.entry(number).or_insert_with(BTreeSet::new).insert(index);
    }

    fn find(&self, number: i32) -> i32 {
        match self.g.get(&number) {
            Some(set) if !set.is_empty() => *set.iter().next().unwrap(),
            _ => -1,
        }
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using HashMaps and SortedMap	Time Complexity: change: O(log N), where N is the number of indices tracked for a number. find: O(1) on average since accessing the minimum index is direct. Space Complexity: O(N + M), where N is the number of indices and M is the number of unique numbers.
Using Two HashMaps	Time Complexity: change: O(log N) due to set operations. find: O(1) by accessing the first element of a set. Space Complexity: O(N + M), where N and M are sizes of index and number maps.
Hash Table + Ordered Set	–

Complexity analysis

Approach	Time	Space	When to Use
HashMap + Ordered Set	O(log n) per operation	O(n)	Best when language supports TreeSet/SortedSet for direct smallest-index lookup
Two HashMaps + Min Heap (Lazy Deletion)	O(log n) amortized	O(n)	Useful in languages without ordered sets; heap cleanup happens during queries

Frequently asked questions

Is Design a Number Container System easy or hard?

The problem is rated Medium because the logic requires coordinating multiple data structures and handling updates correctly. The individual operations are simple, but maintaining consistency between mappings and ensuring the smallest index is returned makes it slightly tricky.

Design a Number Container System Python or Java solution

Python implementations typically use a dictionary with heapq for each number and lazy deletion to remove outdated indices. Java solutions often use HashMap combined with TreeSet, allowing direct retrieval of the smallest index using first(). Both achieve O(log n) operations.

How to solve Design a Number Container System in O(log n)?

Maintain two mappings: indexToNumber to track the current value at each index, and numberToIndices which stores all indices for a number in a sorted structure like TreeSet or a min heap. Updates adjust the index membership, while queries return the smallest stored index. Ordered structures ensure O(log n) insertion and removal.

What is the best approach for Design a Number Container System?

The most reliable approach uses a HashMap and an ordered set (such as TreeSet). A map stores index -> number while another map stores number -> sorted set of indices. Each change operation updates both structures and find(number) simply returns the smallest index from the set. Both operations run in O(log n) time with O(n) space.

Is Design a Number Container System asked at Google/Amazon/Meta?

Design-style data structure problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The question evaluates understanding of hash maps, heaps, and ordered sets along with the ability to maintain consistent state across multiple data structures.

What data structure is used in Design a Number Container System?

The core structures are hash tables for constant-time mapping and either an ordered set (TreeSet / SortedSet) or a min heap to maintain the smallest index for each number. These structures together allow efficient updates and queries.

What is the time complexity of Design a Number Container System?

Using the optimal design, both change(index, number) and find(number) run in O(log n) time because indices are inserted or removed from a balanced ordered set or heap. Hash map lookups remain O(1). Overall space complexity is O(n) to store mappings between indices and numbers.

Design a Number Container System solution and explanation

The problem

Approach overview

Approach 1: Using HashMaps and SortedMap

Approach 2: Using Two HashMaps

Approach 3: Hash Table + Ordered Set

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Design a Number Container System solution and explanation

The problem

Approach overview

Approach 1: Using HashMaps and SortedMap

Approach 2: Using Two HashMaps

Approach 3: Hash Table + Ordered Set

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems