2349. Design a Number Container System

MediumDesignHash TableOrdered SetHeap (Priority Queue)

Problem Description

You need to design a data structure called NumberContainers that manages a system where numbers can be stored at specific indices. The system should support two main operations:

Insert or Replace Operation: You can place a number at any given index. If that index already contains a number, the old number should be replaced with the new one.
Find Operation: Given a number, you need to find and return the smallest index where this number is stored. If the number doesn't exist in the system, return -1.

The class should implement three methods:

NumberContainers(): Constructor that initializes an empty number container system.
void change(int index, int number): Places the number at the specified index. If there's already a number at that index, it replaces the existing number with the new one.
int find(int number): Returns the smallest index where the given number is stored. If the number is not present in any index, returns -1.

For example, if you store the number 10 at indices 2, 5, and 8, calling find(10) should return 2 (the smallest index). If you then change index 2 to contain number 20 instead, calling find(10) should now return 5.

The solution uses two hash tables: one (d) to track what number is at each index, and another (g) that maps each number to a sorted set of indices where that number appears. This allows efficient updates when replacing numbers and quick retrieval of the minimum index for any number.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

When we need to track relationships between indices and numbers, and quickly find the minimum index for any given number, we need to think about what data structures can help us maintain these relationships efficiently.

The key insight is that we have a bidirectional relationship to maintain:

Given an index, we need to know what number is stored there (for replacement operations)
Given a number, we need to know all indices where it appears (to find the minimum)

For the first relationship, a simple hash table mapping index -> number works perfectly. This allows us to check if an index already has a number in O(1) time, which we need when replacing values.

For the second relationship, we need to map each number to all its indices. But since we need the smallest index, we must keep these indices sorted. A regular list would require sorting after each insertion, which is inefficient. Instead, we can use a sorted set (like SortedSet in Python) that maintains order automatically. This gives us O(log n) insertion/removal and O(1) access to the minimum element.

The trickiest part is handling replacements. When we change an index from one number to another, we must:

Remove that index from the old number's set of indices
Add that index to the new number's set of indices
Update our index-to-number mapping

This is why we need both data structures - the first hash table tells us what the old number was (so we know which set to remove from), and the second hash table with sorted sets maintains the efficient minimum-finding capability.

By combining these two hash tables, we achieve optimal time complexities: O(log n) for change operations (due to sorted set operations) and O(1) for find operations (just accessing the first element of a sorted set).

Learn more about Heap (Priority Queue) patterns.

Solution Approach

The solution uses two hash tables to efficiently manage the bidirectional relationship between indices and numbers:

Hash table d: Maps index -> number, tracking what number is stored at each index
Hash table g: Maps number -> SortedSet of indices, tracking all indices where each number appears in sorted order

Implementation Details:

Initialization (__init__):

Create an empty dictionary d to store index-to-number mappings
Create a defaultdict(SortedSet) as g to store number-to-indices mappings, where each number maps to a sorted set of indices

Change Operation (change):

First, check if the index already exists in d:
- If yes, retrieve the old number at that index
- Remove this index from the old number's sorted set in g using self.g[old_number].remove(index)
Update the mapping in d by setting self.d[index] = number
Add the index to the new number's sorted set using self.g[number].add(index)

The time complexity is O(log n) where n is the number of indices for a particular number, due to the sorted set operations.

Find Operation (find):

Retrieve the sorted set of indices for the given number: ids = self.g[number]
If the set is not empty, return the first element ids[0] (which is the minimum due to sorted order)
If the set is empty, return -1

The time complexity is O(1) since accessing the first element of a sorted set is a constant-time operation.

Why This Works:

The SortedSet automatically maintains indices in ascending order, so the first element is always the smallest
Using defaultdict(SortedSet) ensures that we don't need to check if a number exists in g before adding indices to it
The dual hash table structure allows us to efficiently handle replacements by knowing both the old and new numbers at any index
The solution elegantly handles all edge cases: new insertions, replacements, and queries for non-existent numbers

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a sequence of operations to see how the two hash tables work together:

Initial State:

d = {} (index → number mapping)
g = {} (number → sorted set of indices)

Operation 1: change(2, 10)

Index 2 doesn't exist in d, so no removal needed
Update d[2] = 10, now d = {2: 10}
Add index 2 to number 10's set: g[10].add(2), now g = {10: SortedSet([2])}

Operation 2: change(5, 10)

Index 5 doesn't exist in d, so no removal needed
Update d[5] = 10, now d = {2: 10, 5: 10}
Add index 5 to number 10's set: g[10].add(5), now g = {10: SortedSet([2, 5])}

Operation 3: find(10)

Look up g[10] which gives us SortedSet([2, 5])
Return the first element: 2 (the smallest index)

Operation 4: change(2, 20) (Replacement case!)

Index 2 exists in d with value 10 (the old number)
Remove index 2 from number 10's set: g[10].remove(2), now g[10] = SortedSet([5])
Update d[2] = 20, now d = {2: 20, 5: 10}
Add index 2 to number 20's set: g[20].add(2), now g = {10: SortedSet([5]), 20: SortedSet([2])}

Operation 5: find(10)

Look up g[10] which gives us SortedSet([5])
Return the first element: 5 (now the smallest index since 2 was reassigned)

Operation 6: find(20)

Look up g[20] which gives us SortedSet([2])
Return the first element: 2

Operation 7: find(30)

Look up g[30] which gives us an empty SortedSet([])
Since it's empty, return -1

This example demonstrates how:

The sorted set automatically maintains order (indices 2 and 5 are kept sorted)
Replacements properly update both data structures
The find operation efficiently returns the minimum index
Non-existent numbers correctly return -1

Solution Implementation

1from collections import defaultdict
2from sortedcontainers import SortedSet
3
4class NumberContainers:
5    def __init__(self):
6        # Dictionary to store index -> number mapping
7        self.index_to_number = {}
8        # Dictionary to store number -> sorted set of indices mapping
9        self.number_to_indices = defaultdict(SortedSet)
10
11    def change(self, index: int, number: int) -> None:
12        """
13        Updates the number at the given index.
14        If index already exists, removes it from the old number's index set.
15      
16        Args:
17            index: The index position to update
18            number: The new number to store at the index
19        """
20        # If index already exists, remove it from the old number's index set
21        if index in self.index_to_number:
22            old_number = self.index_to_number[index]
23            self.number_to_indices[old_number].remove(index)
24      
25        # Update the index with the new number
26        self.index_to_number[index] = number
27        # Add the index to the new number's sorted set of indices
28        self.number_to_indices[number].add(index)
29
30    def find(self, number: int) -> int:
31        """
32        Finds the smallest index that contains the given number.
33      
34        Args:
35            number: The number to search for
36          
37        Returns:
38            The smallest index containing the number, or -1 if not found
39        """
40        # Get the sorted set of indices for the given number
41        indices = self.number_to_indices[number]
42        # Return the smallest index if exists, otherwise return -1
43        return indices[0] if indices else -1
44
45
46# Your NumberContainers object will be instantiated and called as such:
47# obj = NumberContainers()
48# obj.change(index,number)
49# param_2 = obj.find(number)
50

1class NumberContainers {
2    // Map to store index -> number mapping
3    private Map<Integer, Integer> indexToNumber = new HashMap<>();
4  
5    // Map to store number -> set of indices mapping (TreeSet for sorted indices)
6    private Map<Integer, TreeSet<Integer>> numberToIndices = new HashMap<>();
7
8    /**
9     * Constructor for NumberContainers
10     */
11    public NumberContainers() {
12    }
13
14    /**
15     * Updates or inserts a number at the given index
16     * @param index the index position to update
17     * @param number the number to store at the index
18     */
19    public void change(int index, int number) {
20        // If index already exists, remove it from the old number's index set
21        if (indexToNumber.containsKey(index)) {
22            int previousNumber = indexToNumber.get(index);
23            numberToIndices.get(previousNumber).remove(index);
24        }
25      
26        // Update the index with new number
27        indexToNumber.put(index, number);
28      
29        // Add index to the new number's index set (create TreeSet if not exists)
30        numberToIndices.computeIfAbsent(number, key -> new TreeSet<>()).add(index);
31    }
32
33    /**
34     * Finds the smallest index that contains the given number
35     * @param number the number to search for
36     * @return the smallest index containing the number, or -1 if not found
37     */
38    public int find(int number) {
39        TreeSet<Integer> indices = numberToIndices.get(number);
40      
41        // Return -1 if number doesn't exist or has no indices
42        // Otherwise return the smallest index (first element in TreeSet)
43        return (indices == null || indices.isEmpty()) ? -1 : indices.first();
44    }
45}
46
47/**
48 * Your NumberContainers object will be instantiated and called as such:
49 * NumberContainers obj = new NumberContainers();
50 * obj.change(index,number);
51 * int param_2 = obj.find(number);
52 */
53

1class NumberContainers {
2public:
3    NumberContainers() {
4    }
5  
6    void change(int index, int number) {
7        // Check if this index already has a value
8        if (indexToNumber.count(index)) {
9            int oldNumber = indexToNumber[index];
10            // Remove the index from the old number's set of indices
11            numberToIndices[oldNumber].erase(index);
12            // If no more indices point to this old number, remove it from the map
13            if (numberToIndices[oldNumber].empty()) {
14                numberToIndices.erase(oldNumber);
15            }
16        }
17      
18        // Update the index with the new number
19        indexToNumber[index] = number;
20        // Add this index to the set of indices for the new number
21        numberToIndices[number].insert(index);
22    }
23  
24    int find(int number) {
25        // If the number exists in our map, return the smallest index (first element in set)
26        // Otherwise return -1
27        return numberToIndices.count(number) ? *numberToIndices[number].begin() : -1;
28    }
29  
30private:
31    // Maps each index to its current number value
32    unordered_map<int, int> indexToNumber;
33  
34    // Maps each number to a sorted set of indices that contain that number
35    // Using set to maintain indices in sorted order for efficient smallest index retrieval
36    unordered_map<int, set<int>> numberToIndices;
37};
38
39/**
40 * Your NumberContainers object will be instantiated and called as such:
41 * NumberContainers* obj = new NumberContainers();
42 * obj->change(index,number);
43 * int param_2 = obj->find(number);
44 */
45

1// Map to store index -> number mapping
2const indexToNumber = new Map<number, number>();
3// Map to store number -> set of indices mapping
4const numberToIndices = new Map<number, TreeSet<number>>();
5
6/**
7 * Updates the number at the given index
8 * @param index - The index to update
9 * @param number - The new number to store at the index
10 */
11function change(index: number, number: number): void {
12    // Remove old index from previous number's set if it exists
13    if (indexToNumber.has(index)) {
14        const previousNumber = indexToNumber.get(index)!;
15        numberToIndices.get(previousNumber)!.delete(index);
16      
17        // Clean up empty sets
18        if (!numberToIndices.get(previousNumber)!.size()) {
19            numberToIndices.delete(previousNumber);
20        }
21    }
22  
23    // Update the index with new number
24    indexToNumber.set(index, number);
25  
26    // Create new TreeSet for this number if it doesn't exist
27    if (!numberToIndices.has(number)) {
28        numberToIndices.set(number, new TreeSet());
29    }
30  
31    // Add index to the number's set
32    numberToIndices.get(number)!.add(index);
33}
34
35/**
36 * Finds the smallest index that contains the given number
37 * @param number - The number to search for
38 * @returns The smallest index containing the number, or -1 if not found
39 */
40function find(number: number): number {
41    return numberToIndices.has(number) ? numberToIndices.get(number)!.first()! : -1;
42}
43
44// Type definition for comparison function
45type Compare<T> = (lhs: T, rhs: T) => number;
46
47/**
48 * Red-Black Tree Node implementation
49 * Color: 0 = RED, 1 = BLACK
50 */
51class RBTreeNode<T = number> {
52    data: T;
53    count: number;  // Number of duplicates
54    left: RBTreeNode<T> | null;
55    right: RBTreeNode<T> | null;
56    parent: RBTreeNode<T> | null;
57    color: number;  // 0 = RED, 1 = BLACK
58  
59    constructor(data: T) {
60        this.data = data;
61        this.left = this.right = this.parent = null;
62        this.color = 0;  // New nodes are red by default
63        this.count = 1;
64    }
65
66    /**
67     * Returns the sibling of this node
68     */
69    sibling(): RBTreeNode<T> | null {
70        if (!this.parent) return null;
71        return this.isOnLeft() ? this.parent.right : this.parent.left;
72    }
73
74    /**
75     * Checks if this node is the left child of its parent
76     */
77    isOnLeft(): boolean {
78        return this === this.parent!.left;
79    }
80
81    /**
82     * Checks if this node has at least one red child
83     */
84    hasRedChild(): boolean {
85        return (
86            Boolean(this.left && this.left.color === 0) ||
87            Boolean(this.right && this.right.color === 0)
88        );
89    }
90}
91
92/**
93 * Red-Black Tree implementation for balanced BST operations
94 */
95class RBTree<T> {
96    root: RBTreeNode<T> | null;
97    lt: (l: T, r: T) => boolean;  // Less than comparator
98  
99    constructor(compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)) {
100        this.root = null;
101        this.lt = (l: T, r: T) => compare(l, r) < 0;
102    }
103
104    /**
105     * Performs left rotation on the given node
106     */
107    rotateLeft(pivotNode: RBTreeNode<T>): void {
108        const rightChild = pivotNode.right!;
109        pivotNode.right = rightChild.left;
110
111        if (pivotNode.right) pivotNode.right.parent = pivotNode;
112        rightChild.parent = pivotNode.parent;
113
114        if (!pivotNode.parent) this.root = rightChild;
115        else if (pivotNode === pivotNode.parent.left) pivotNode.parent.left = rightChild;
116        else pivotNode.parent.right = rightChild;
117
118        rightChild.left = pivotNode;
119        pivotNode.parent = rightChild;
120    }
121
122    /**
123     * Performs right rotation on the given node
124     */
125    rotateRight(pivotNode: RBTreeNode<T>): void {
126        const leftChild = pivotNode.left!;
127        pivotNode.left = leftChild.right;
128
129        if (pivotNode.left) pivotNode.left.parent = pivotNode;
130        leftChild.parent = pivotNode.parent;
131
132        if (!pivotNode.parent) this.root = leftChild;
133        else if (pivotNode === pivotNode.parent.left) pivotNode.parent.left = leftChild;
134        else pivotNode.parent.right = leftChild;
135
136        leftChild.right = pivotNode;
137        pivotNode.parent = leftChild;
138    }
139
140    /**
141     * Swaps colors of two nodes
142     */
143    swapColor(node1: RBTreeNode<T>, node2: RBTreeNode<T>): void {
144        const tempColor = node1.color;
145        node1.color = node2.color;
146        node2.color = tempColor;
147    }
148
149    /**
150     * Swaps data of two nodes
151     */
152    swapData(node1: RBTreeNode<T>, node2: RBTreeNode<T>): void {
153        const tempData = node1.data;
154        node1.data = node2.data;
155        node2.data = tempData;
156    }
157
158    /**
159     * Fixes Red-Black Tree violations after insertion
160     */
161    fixAfterInsert(currentNode: RBTreeNode<T>): void {
162        let parent = null;
163        let grandParent = null;
164
165        // Fix violations while current node is not root, not black, and parent is red
166        while (currentNode !== this.root && currentNode.color !== 1 && currentNode.parent?.color === 0) {
167            parent = currentNode.parent;
168            grandParent = currentNode.parent.parent;
169
170            // Case A: Parent is left child of grandparent
171            if (parent === grandParent?.left) {
172                const uncle = grandParent.right;
173
174                // Case 1: Uncle is red - only recoloring needed
175                if (uncle && uncle.color === 0) {
176                    grandParent.color = 0;  // Set grandparent to red
177                    parent.color = 1;        // Set parent to black
178                    uncle.color = 1;         // Set uncle to black
179                    currentNode = grandParent;
180                } else {
181                    // Case 2: Current node is right child - left rotation needed
182                    if (currentNode === parent.right) {
183                        this.rotateLeft(parent);
184                        currentNode = parent;
185                        parent = currentNode.parent;
186                    }
187
188                    // Case 3: Current node is left child - right rotation needed
189                    this.rotateRight(grandParent);
190                    this.swapColor(parent!, grandParent);
191                    currentNode = parent!;
192                }
193            } else {
194                // Case B: Parent is right child of grandparent
195                const uncle = grandParent!.left;
196
197                // Case 1: Uncle is red - only recoloring needed
198                if (uncle != null && uncle.color === 0) {
199                    grandParent!.color = 0;  // Set grandparent to red
200                    parent.color = 1;        // Set parent to black
201                    uncle.color = 1;         // Set uncle to black
202                    currentNode = grandParent!;
203                } else {
204                    // Case 2: Current node is left child - right rotation needed
205                    if (currentNode === parent.left) {
206                        this.rotateRight(parent);
207                        currentNode = parent;
208                        parent = currentNode.parent;
209                    }
210
211                    // Case 3: Current node is right child - left rotation needed
212                    this.rotateLeft(grandParent!);
213                    this.swapColor(parent!, grandParent!);
214                    currentNode = parent!;
215                }
216            }
217        }
218        // Root must always be black
219        this.root!.color = 1;
220    }
221
222    /**
223     * Deletes one occurrence of the value from the tree
224     */
225    delete(val: T): boolean {
226        const node = this.find(val);
227        if (!node) return false;
228        node.count--;
229        if (!node.count) this.deleteNode(node);
230        return true;
231    }
232
233    /**
234     * Deletes all occurrences of the value from the tree
235     */
236    deleteAll(val: T): boolean {
237        const node = this.find(val);
238        if (!node) return false;
239        this.deleteNode(node);
240        return true;
241    }
242
243    /**
244     * Deletes a node from the tree and maintains Red-Black properties
245     */
246    deleteNode(nodeToDelete: RBTreeNode<T>): void {
247        // Find BST replacement node
248        function findBSTReplacement(node: RBTreeNode<T>): RBTreeNode<T> | null {
249            // Node has 2 children - find successor
250            if (node.left && node.right) return findSuccessor(node.right);
251            // Node is leaf
252            if (!node.left && !node.right) return null;
253            // Node has single child
254            return node.left ?? node.right;
255        }
256      
257        // Find in-order successor (leftmost node in right subtree)
258        function findSuccessor(node: RBTreeNode<T>): RBTreeNode<T> {
259            let current = node;
260            while (current.left) current = current.left;
261            return current;
262        }
263
264        const replacement = findBSTReplacement(nodeToDelete);
265      
266        // Check if both nodes are black (double black case)
267        const bothBlack = (replacement === null || replacement.color === 1) && nodeToDelete.color === 1;
268        const parent = nodeToDelete.parent!;
269
270        if (!replacement) {
271            // Node to delete is a leaf
272            if (nodeToDelete === this.root) {
273                this.root = null;  // Tree becomes empty
274            } else {
275                if (bothBlack) {
276                    // Both node and replacement are black - fix double black
277                    this.fixDoubleBlack(nodeToDelete);
278                } else {
279                    // One of them is red - make sibling red if exists
280                    if (nodeToDelete.sibling()) {
281                        nodeToDelete.sibling()!.color = 0;
282                    }
283                }
284                // Remove node from parent
285                if (nodeToDelete.isOnLeft()) parent.left = null;
286                else parent.right = null;
287            }
288            return;
289        }
290
291        if (!nodeToDelete.left || !nodeToDelete.right) {
292            // Node has exactly one child
293            if (nodeToDelete === this.root) {
294                // Replace root's data and remove child
295                nodeToDelete.data = replacement.data;
296                nodeToDelete.left = nodeToDelete.right = null;
297            } else {
298                // Replace node with its child
299                if (nodeToDelete.isOnLeft()) parent.left = replacement;
300                else parent.right = replacement;
301                replacement.parent = parent;
302              
303                if (bothBlack) this.fixDoubleBlack(replacement);  // Fix double black
304                else replacement.color = 1;  // Make replacement black
305            }
306            return;
307        }
308
309        // Node has 2 children - swap with successor and recurse
310        this.swapData(replacement, nodeToDelete);
311        this.deleteNode(replacement);
312    }
313
314    /**
315     * Fixes double black violation in Red-Black Tree
316     */
317    fixDoubleBlack(node: RBTreeNode<T>): void {
318        if (node === this.root) return;  // Reached root, done
319
320        const sibling = node.sibling();
321        const parent = node.parent!;
322      
323        if (!sibling) {
324            // No sibling - push double black up
325            this.fixDoubleBlack(parent);
326        } else {
327            if (sibling.color === 0) {
328                // Sibling is red
329                parent.color = 0;      // Make parent red
330                sibling.color = 1;     // Make sibling black
331              
332                if (sibling.isOnLeft()) this.rotateRight(parent);
333                else this.rotateLeft(parent);
334              
335                this.fixDoubleBlack(node);
336            } else {
337                // Sibling is black
338                if (sibling.hasRedChild()) {
339                    // Sibling has at least one red child
340                    if (sibling.left && sibling.left.color === 0) {
341                        if (sibling.isOnLeft()) {
342                            // Left-Left case
343                            sibling.left.color = sibling.color;
344                            sibling.color = parent.color;
345                            this.rotateRight(parent);
346                        } else {
347                            // Right-Left case
348                            sibling.left.color = parent.color;
349                            this.rotateRight(sibling);
350                            this.rotateLeft(parent);
351                        }
352                    } else {
353                        if (sibling.isOnLeft()) {
354                            // Left-Right case
355                            sibling.right!.color = parent.color;
356                            this.rotateLeft(sibling);
357                            this.rotateRight(parent);
358                        } else {
359                            // Right-Right case
360                            sibling.right!.color = sibling.color;
361                            sibling.color = parent.color;
362                            this.rotateLeft(parent);
363                        }
364                    }
365                    parent.color = 1;  // Make parent black
366                } else {
367                    // Sibling has two black children
368                    sibling.color = 0;  // Make sibling red
369                    if (parent.color === 1) this.fixDoubleBlack(parent);
370                    else parent.color = 1;  // Make parent black
371                }
372            }
373        }
374    }
375
376    /**
377     * Inserts a value into the tree
378     */
379    insert(data: T): boolean {
380        // Find insertion position
381        let parent = this.root;
382        while (parent) {
383            if (this.lt(data, parent.data)) {
384                if (!parent.left) break;
385                else parent = parent.left;
386            } else if (this.lt(parent.data, data)) {
387                if (!parent.right) break;
388                else parent = parent.right;
389            } else break;  // Found duplicate
390        }
391
392        // Create and insert new node
393        const newNode = new RBTreeNode(data);
394        if (!parent) {
395            this.root = newNode;
396        } else if (this.lt(newNode.data, parent.data)) {
397            parent.left = newNode;
398        } else if (this.lt(parent.data, newNode.data)) {
399            parent.right = newNode;
400        } else {
401            // Duplicate found - increment count
402            parent.count++;
403            return false;
404        }
405      
406        newNode.parent = parent;
407        this.fixAfterInsert(newNode);
408        return true;
409    }
410
411    /**
412     * Finds a node with the given data
413     */
414    find(data: T): RBTreeNode<T> | null {
415        let current = this.root;
416        while (current) {
417            if (this.lt(data, current.data)) {
418                current = current.left;
419            } else if (this.lt(current.data, data)) {
420                current = current.right;
421            } else break;  // Found
422        }
423        return current ?? null;
424    }
425
426    /**
427     * Generator for in-order traversal
428     */
429    *inOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
430        if (!root) return;
431        for (const value of this.inOrder(root.left!)) yield value;
432        yield root.data;
433        for (const value of this.inOrder(root.right!)) yield value;
434    }
435
436    /**
437     * Generator for reverse in-order traversal
438     */
439    *reverseInOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
440        if (!root) return;
441        for (const value of this.reverseInOrder(root.right!)) yield value;
442        yield root.data;
443        for (const value of this.reverseInOrder(root.left!)) yield value;
444    }
445}
446
447/**
448 * Ordered set implementation using Red-Black Tree
449 */
450class TreeSet<T = number> {
451    private _size: number;
452    private tree: RBTree<T>;
453    private compare: Compare<T>;
454  
455    constructor(
456        collection: T[] | Compare<T> = [],
457        compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
458    ) {
459        // Handle overloaded constructor
460        if (typeof collection === 'function') {
461            compare = collection;
462            collection = [];
463        }
464        this._size = 0;
465        this.compare = compare;
466        this.tree = new RBTree(compare);
467      
468        // Initialize with collection
469        for (const val of collection) this.add(val);
470    }
471
472    /**
473     * Returns the number of elements in the set
474     */
475    size(): number {
476        return this._size;
477    }
478
479    /**
480     * Checks if value exists in the set
481     */
482    has(val: T): boolean {
483        return !!this.tree.find(val);
484    }
485
486    /**
487     * Adds a value to the set
488     */
489    add(val: T): boolean {
490        const success = this.tree.insert(val);
491        this._size += success ? 1 : 0;
492        return success;
493    }
494
495    /**
496     * Removes a value from the set
497     */
498    delete(val: T): boolean {
499        const deleted = this.tree.deleteAll(val);
500        this._size -= deleted ? 1 : 0;
501        return deleted;
502    }
503
504    /**
505     * Returns the smallest value >= given value
506     */
507    ceil(val: T): T | undefined {
508        let current = this.tree.root;
509        let result = null;
510        while (current) {
511            if (this.compare(current.data, val) >= 0) {
512                result = current;
513                current = current.left;
514            } else {
515                current = current.right;
516            }
517        }
518        return result?.data;
519    }
520
521    /**
522     * Returns the largest value <= given value
523     */
524    floor(val: T): T | undefined {
525        let current = this.tree.root;
526        let result = null;
527        while (current) {
528            if (this.compare(val, current.data) >= 0) {
529                result = current;
530                current = current.right;
531            } else {
532                current = current.left;
533            }
534        }
535        return result?.data;
536    }
537
538    /**
539     * Returns the smallest value > given value
540     */
541    higher(val: T): T | undefined {
542        let current = this.tree.root;
543        let result = null;
544        while (current) {
545            if (this.compare(val, current.data) < 0) {
546                result = current;
547                current = current.left;
548            } else {
549                current = current.right;
550            }
551        }
552        return result?.data;
553    }
554
555    /**
556     * Returns the largest value < given value
557     */
558    lower(val: T): T | undefined {
559        let current = this.tree.root;
560        let result = null;
561        while (current) {
562            if (this.compare(current.data, val) < 0) {
563                result = current;
564                current = current.right;
565            } else {
566                current = current.left;
567            }
568        }
569        return result?.data;
570    }
571
572    /**
573     * Returns the smallest element in the set
574     */
575    first(): T | undefined {
576        return this.tree.inOrder().next().value;
577    }
578
579    /**
580     * Returns the largest element in the set
581     */
582    last(): T | undefined {
583        return this.tree.reverseInOrder().next().value;
584    }
585
586    /**
587     * Removes and returns the smallest element
588     */
589    shift(): T | undefined {
590        const firstElement = this.first();
591        if (firstElement === undefined) return undefined;
592        this.delete(firstElement);
593        return firstElement;
594    }
595
596    /**
597     * Removes and returns the largest element
598     */
599    pop(): T | undefined {
600        const lastElement = this.last();
601        if (lastElement === undefined) return undefined;
602        this.delete(lastElement);
603        return lastElement;
604    }
605
606    /**
607     * Iterator for the set
608     */
609    *[Symbol.iterator](): Generator<T, void, void> {
610        for (const val of this.values()) yield val;
611    }
612
613    /**
614     * Returns generator for keys (same as values for set)
615     */
616    *keys(): Generator<T, void, void> {
617        for (const val of this.values()) yield val;
618    }
619
620    /**
621     * Returns generator for values in ascending order
622     */
623    *values(): Generator<T, undefined, void> {
624        for (const val of this.tree.inOrder()) yield val;
625        return undefined;
626    }
627
628    /**
629     * Returns generator for values in descending order
630     */
631    *rvalues(): Generator<T, undefined, void> {
632        for (const val of this.tree.reverseInOrder()) yield val;
633        return undefined;
634    }
635}
636

Time and Space Complexity

Time Complexity:

__init__(): O(1) - Simply initializes two data structures
change(index, number): O(log m) where m is the number of indices associated with a particular number
- Checking if index exists in dictionary: O(1)
- Removing from SortedSet: O(log m)
- Adding to dictionary: O(1)
- Adding to SortedSet: O(log m)
find(number): O(1) - Accessing the first element of a SortedSet is constant time

Space Complexity: O(n) where n is the total number of unique index-number pairs stored

Dictionary self.d: O(n) - stores at most n index-number mappings
Dictionary of SortedSets self.g: O(n) - in total stores all indices across all numbers, which is at most n indices
The reference answer confirms the space complexity is O(n), where n is the number of numbers (or more precisely, the number of stored mappings)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Remove Old Index When Replacing

One of the most common mistakes is forgetting to remove the index from the old number's set when replacing a value at an existing index. This leads to stale data where an index appears in multiple numbers' sets.

Incorrect Implementation:

def change(self, index: int, number: int) -> None:
    # WRONG: Directly updating without cleaning up old mapping
    self.index_to_number[index] = number
    self.number_to_indices[number].add(index)

Problem: If index 2 initially contains number 10, and we change it to number 20, index 2 would incorrectly remain in both number_to_indices[10] and number_to_indices[20]. Calling find(10) would incorrectly return 2 even though 10 is no longer at that index.

Correct Solution:

def change(self, index: int, number: int) -> None:
    # Check if index already exists and clean up old mapping
    if index in self.index_to_number:
        old_number = self.index_to_number[index]
        self.number_to_indices[old_number].remove(index)
  
    self.index_to_number[index] = number
    self.number_to_indices[number].add(index)

2. Using Regular Set Instead of SortedSet

Using a regular set instead of SortedSet would make finding the minimum index inefficient.

Incorrect Implementation:

def __init__(self):
    self.index_to_number = {}
    # WRONG: Using regular set
    self.number_to_indices = defaultdict(set)

def find(self, number: int) -> int:
    indices = self.number_to_indices[number]
    # WRONG: This requires O(n) time to find minimum
    return min(indices) if indices else -1

Problem: Finding the minimum element in an unordered set requires O(n) time, where n is the number of indices for that number. This significantly degrades performance for numbers stored at many indices.

Correct Solution: Use SortedSet which maintains elements in sorted order, allowing O(1) access to the minimum element.

3. Not Handling Empty Set in Find Operation

Attempting to access the first element of an empty set will raise an IndexError.

Incorrect Implementation:

def find(self, number: int) -> int:
    # WRONG: Doesn't check if set is empty
    return self.number_to_indices[number][0]

Problem: If the number doesn't exist or all its indices have been replaced, accessing [0] on an empty SortedSet raises an IndexError.

Correct Solution:

def find(self, number: int) -> int:
    indices = self.number_to_indices[number]
    return indices[0] if indices else -1

4. Memory Leak from Not Cleaning Empty Sets

While not critical for functionality, continuously adding and removing indices without cleaning up empty sets can lead to memory inefficiency.

Enhanced Solution:

def change(self, index: int, number: int) -> None:
    if index in self.index_to_number:
        old_number = self.index_to_number[index]
        self.number_to_indices[old_number].remove(index)
        # Optional: Clean up empty sets to save memory
        if not self.number_to_indices[old_number]:
            del self.number_to_indices[old_number]
  
    self.index_to_number[index] = number
    self.number_to_indices[number].add(index)

This optimization removes empty sets from the dictionary, preventing unnecessary memory usage for numbers that no longer exist in the container.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know

2349. Design a Number Container System

Problem Description

Intuition

Solution Approach

Implementation Details:

Why This Works:

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

1. Forgetting to Remove Old Index When Replacing

2. Using Regular Set Instead of SortedSet

3. Not Handling Empty Set in Find Operation

4. Memory Leak from Not Cleaning Empty Sets

Recommended Readings