2336. Smallest Number in Infinite Set
Problem Description
You need to implement a data structure that represents an infinite set containing all positive integers [1, 2, 3, 4, 5, ...]
.
The SmallestInfiniteSet
class should support the following operations:
-
Constructor
SmallestInfiniteSet()
: Initializes the object to contain all positive integers starting from 1. -
Pop Smallest
popSmallest()
: Removes and returns the smallest integer currently in the set. For example, if the set contains[1, 2, 3, ...]
, calling this method would remove and return1
, leaving the set as[2, 3, 4, ...]
. -
Add Back
addBack(num)
: Adds a positive integernum
back into the set, but only if it's not already present. This is useful when you want to restore a number that was previously popped.
The key challenge is efficiently managing which numbers have been removed from the infinite set and which have been added back. While the set conceptually contains all positive integers, you need to track the state changes caused by the pop and add operations.
For example:
- Initially, the set contains
[1, 2, 3, 4, 5, ...]
- After calling
popSmallest()
, it returns1
and the set becomes[2, 3, 4, 5, ...]
- After calling
popSmallest()
again, it returns2
and the set becomes[3, 4, 5, ...]
- After calling
addBack(1)
, the set becomes[1, 3, 4, 5, ...]
- The next
popSmallest()
would return1
Intuition
Since we need to track an "infinite" set of positive integers with operations to remove the smallest element and add elements back, we need to think about what actually changes in our set.
Initially, the set contains all positive integers [1, 2, 3, 4, ...]
. When we pop elements, we create "gaps" in this sequence. For instance, if we pop 1
and 2
, our set becomes [3, 4, 5, ...]
. If we then add back 1
, it becomes [1, 3, 4, 5, ...]
.
The key insight is that we don't actually need to store an infinite set. We only need to track which numbers have been removed from the initial sequence and haven't been added back yet. Since the problem constraints typically limit the number of operations (and based on the solution using range(1, 1001)
), we can work with a finite range.
We need a data structure that:
- Maintains elements in sorted order (to quickly find the smallest)
- Allows efficient removal of the minimum element
- Allows efficient insertion of elements
An ordered set (like SortedSet
in Python) is perfect for this because:
- It automatically maintains elements in sorted order
- The first element
s[0]
is always the smallest - Both insertion and removal operations are
O(log n)
Instead of conceptually thinking about tracking removed elements, we can flip our perspective: maintain a set of all available numbers. Start with a finite range like [1, 1000]
(sufficient for the problem constraints), and when popSmallest()
is called, remove the smallest element from our set. When addBack(num)
is called, add the number back to our set if it was previously removed.
This approach elegantly handles all cases - the set maintains order automatically, duplicate prevention is built-in (sets don't allow duplicates), and we always have immediate access to the smallest element.
Learn more about Heap (Priority Queue) patterns.
Solution Approach
The solution uses an ordered set data structure to efficiently manage the infinite set operations. Here's how each component works:
Data Structure Choice
We use a SortedSet
(an ordered set implementation) initialized with elements from 1
to 1000
. This range is sufficient based on the problem constraints. The ordered set maintains elements in sorted order automatically, which is crucial for finding the smallest element quickly.
self.s = SortedSet(range(1, 1001))
Implementation Details
1. Initialization (__init__
)
- Create a
SortedSet
containing all integers from1
to1000
- Time Complexity:
O(n × log n)
wheren = 1000
- The set starts with all possible values we might need
2. Pop Smallest (popSmallest
)
- Access the first element using index
s[0]
- this is always the smallest due to the sorted property - Remove this element from the set using
remove()
- Return the removed element
- Time Complexity:
O(log n)
for the removal operation
def popSmallest(self) -> int:
x = self.s[0] # Get the smallest element
self.s.remove(x) # Remove it from the set
return x # Return the removed element
3. Add Back (addBack
)
- Simply add the number back to the set using
add()
- The
SortedSet
automatically:- Maintains the sorted order
- Handles duplicates (won't add if already present)
- Time Complexity:
O(log n)
for the insertion operation
def addBack(self, num: int) -> None:
self.s.add(num) # Add the number back to the set
Why This Works
The elegance of this solution lies in treating the "infinite set" as a finite ordered collection of available numbers. Since we're limited by the problem constraints (numbers up to 1000), we can:
- Pre-populate all possible values
- Remove numbers when popped
- Add them back when requested
The SortedSet
handles all the complexity of maintaining order and ensuring efficient operations, making the implementation clean and straightforward.
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a concrete example to see how the solution works:
Initial State:
- We create a
SmallestInfiniteSet
- The
SortedSet
contains:[1, 2, 3, 4, 5, ..., 1000]
Operation 1: popSmallest()
- Current set:
[1, 2, 3, 4, 5, ...]
- Access
s[0]
which is1
(the smallest element) - Remove
1
from the set - Return
1
- New set:
[2, 3, 4, 5, 6, ...]
Operation 2: popSmallest()
- Current set:
[2, 3, 4, 5, 6, ...]
- Access
s[0]
which is now2
(the new smallest) - Remove
2
from the set - Return
2
- New set:
[3, 4, 5, 6, 7, ...]
Operation 3: popSmallest()
- Current set:
[3, 4, 5, 6, 7, ...]
- Access
s[0]
which is3
- Remove
3
from the set - Return
3
- New set:
[4, 5, 6, 7, 8, ...]
Operation 4: addBack(1)
- Current set:
[4, 5, 6, 7, 8, ...]
- Add
1
to the set - The
SortedSet
automatically places it in the correct position - New set:
[1, 4, 5, 6, 7, ...]
Operation 5: popSmallest()
- Current set:
[1, 4, 5, 6, 7, ...]
- Access
s[0]
which is1
(it's back as the smallest!) - Remove
1
from the set - Return
1
- New set:
[4, 5, 6, 7, 8, ...]
Operation 6: addBack(2)
- Current set:
[4, 5, 6, 7, 8, ...]
- Add
2
to the set - The
SortedSet
automatically maintains sorted order - New set:
[2, 4, 5, 6, 7, ...]
Operation 7: addBack(2)
(duplicate attempt)
- Current set:
[2, 4, 5, 6, 7, ...]
- Try to add
2
to the set - Since
2
is already present, the set remains unchanged - New set:
[2, 4, 5, 6, 7, ...]
(no change)
This example demonstrates how the SortedSet
elegantly handles:
- Always maintaining sorted order (smallest element is always at index 0)
- Efficient removal and insertion operations
- Automatic duplicate prevention
- The illusion of an "infinite set" while actually working with a finite range
Solution Implementation
1from sortedcontainers import SortedSet
2
3class SmallestInfiniteSet:
4 def __init__(self):
5 # Initialize a sorted set containing integers from 1 to 1000
6 # This represents the "infinite" set of positive integers
7 self.sorted_set = SortedSet(range(1, 1001))
8
9 def popSmallest(self) -> int:
10 # Get the smallest element (first element in sorted set)
11 smallest = self.sorted_set[0]
12
13 # Remove the smallest element from the set
14 self.sorted_set.remove(smallest)
15
16 # Return the smallest element that was removed
17 return smallest
18
19 def addBack(self, num: int) -> None:
20 # Add the number back to the set
21 # SortedSet automatically handles duplicates (won't add if already exists)
22 self.sorted_set.add(num)
23
24
25# Your SmallestInfiniteSet object will be instantiated and called as such:
26# obj = SmallestInfiniteSet()
27# param_1 = obj.popSmallest()
28# obj.addBack(num)
29
1class SmallestInfiniteSet {
2 // TreeSet to maintain sorted unique integers in ascending order
3 private TreeSet<Integer> availableNumbers = new TreeSet<>();
4
5 /**
6 * Constructor initializes the set with integers from 1 to 1000
7 * representing the smallest positive integers in the infinite set
8 */
9 public SmallestInfiniteSet() {
10 // Populate the set with initial values 1 through 1000
11 for (int i = 1; i <= 1000; i++) {
12 availableNumbers.add(i);
13 }
14 }
15
16 /**
17 * Removes and returns the smallest integer from the infinite set
18 * @return the smallest available integer
19 */
20 public int popSmallest() {
21 // Remove and return the first (smallest) element from the TreeSet
22 return availableNumbers.pollFirst();
23 }
24
25 /**
26 * Adds a number back to the infinite set if it's not already present
27 * @param num the integer to add back to the set
28 */
29 public void addBack(int num) {
30 // Add the number back to the set (TreeSet handles duplicates automatically)
31 availableNumbers.add(num);
32 }
33}
34
35/**
36 * Your SmallestInfiniteSet object will be instantiated and called as such:
37 * SmallestInfiniteSet obj = new SmallestInfiniteSet();
38 * int param_1 = obj.popSmallest();
39 * obj.addBack(num);
40 */
41
1class SmallestInfiniteSet {
2public:
3 // Constructor: Initialize the set with integers from 1 to 1000
4 SmallestInfiniteSet() {
5 for (int i = 1; i <= 1000; ++i) {
6 available_numbers.insert(i);
7 }
8 }
9
10 // Remove and return the smallest integer from the infinite set
11 int popSmallest() {
12 // Get the smallest element (first element in ordered set)
13 int smallest = *available_numbers.begin();
14
15 // Remove the smallest element from the set
16 available_numbers.erase(available_numbers.begin());
17
18 return smallest;
19 }
20
21 // Add a number back to the infinite set if not already present
22 void addBack(int num) {
23 // Insert the number (set automatically handles duplicates)
24 available_numbers.insert(num);
25 }
26
27private:
28 // Ordered set to maintain available numbers in sorted order
29 std::set<int> available_numbers;
30};
31
32/**
33 * Your SmallestInfiniteSet object will be instantiated and called as such:
34 * SmallestInfiniteSet* obj = new SmallestInfiniteSet();
35 * int param_1 = obj->popSmallest();
36 * obj->addBack(num);
37 */
38
1// Type alias for comparison function
2type CompareFunction<T> = (left: T, right: T) => number;
3
4// Global TreeSet instance to store the infinite set
5let infiniteSet: TreeSet<number>;
6
7// Initialize the smallest infinite set with numbers 1 to 1000
8function initializeSmallestInfiniteSet(): void {
9 infiniteSet = new TreeSet<number>();
10 for (let i = 1; i <= 1000; i++) {
11 infiniteSet.add(i);
12 }
13}
14
15// Remove and return the smallest integer from the infinite set
16function popSmallest(): number {
17 return infiniteSet.shift()!;
18}
19
20// Add a number back to the infinite set if it's not already present
21function addBack(num: number): void {
22 infiniteSet.add(num);
23}
24
25// Red-Black Tree Node class
26class RBTreeNode<T = number> {
27 data: T;
28 count: number; // Number of duplicates for this value
29 left: RBTreeNode<T> | null;
30 right: RBTreeNode<T> | null;
31 parent: RBTreeNode<T> | null;
32 color: number; // 0 = RED, 1 = BLACK
33
34 constructor(data: T) {
35 this.data = data;
36 this.left = null;
37 this.right = null;
38 this.parent = null;
39 this.color = 0; // New nodes are RED by default
40 this.count = 1;
41 }
42
43 // Get the sibling of this node
44 sibling(): RBTreeNode<T> | null {
45 if (!this.parent) return null;
46 return this.isOnLeft() ? this.parent.right : this.parent.left;
47 }
48
49 // Check if this node is the left child of its parent
50 isOnLeft(): boolean {
51 return this === this.parent!.left;
52 }
53
54 // Check if this node has at least one red child
55 hasRedChild(): boolean {
56 return (
57 Boolean(this.left && this.left.color === 0) ||
58 Boolean(this.right && this.right.color === 0)
59 );
60 }
61}
62
63// Red-Black Tree implementation
64class RBTree<T> {
65 root: RBTreeNode<T> | null;
66 lessThan: (left: T, right: T) => boolean;
67
68 constructor(compare: CompareFunction<T> = (left: T, right: T) => (left < right ? -1 : left > right ? 1 : 0)) {
69 this.root = null;
70 this.lessThan = (left: T, right: T) => compare(left, right) < 0;
71 }
72
73 // Perform left rotation on the given node
74 rotateLeft(pivotNode: RBTreeNode<T>): void {
75 const rightChild = pivotNode.right!;
76 pivotNode.right = rightChild.left;
77
78 if (pivotNode.right) {
79 pivotNode.right.parent = pivotNode;
80 }
81
82 rightChild.parent = pivotNode.parent;
83
84 if (!pivotNode.parent) {
85 this.root = rightChild;
86 } else if (pivotNode === pivotNode.parent.left) {
87 pivotNode.parent.left = rightChild;
88 } else {
89 pivotNode.parent.right = rightChild;
90 }
91
92 rightChild.left = pivotNode;
93 pivotNode.parent = rightChild;
94 }
95
96 // Perform right rotation on the given node
97 rotateRight(pivotNode: RBTreeNode<T>): void {
98 const leftChild = pivotNode.left!;
99 pivotNode.left = leftChild.right;
100
101 if (pivotNode.left) {
102 pivotNode.left.parent = pivotNode;
103 }
104
105 leftChild.parent = pivotNode.parent;
106
107 if (!pivotNode.parent) {
108 this.root = leftChild;
109 } else if (pivotNode === pivotNode.parent.left) {
110 pivotNode.parent.left = leftChild;
111 } else {
112 pivotNode.parent.right = leftChild;
113 }
114
115 leftChild.right = pivotNode;
116 pivotNode.parent = leftChild;
117 }
118
119 // Swap colors between two nodes
120 swapColor(node1: RBTreeNode<T>, node2: RBTreeNode<T>): void {
121 const tempColor = node1.color;
122 node1.color = node2.color;
123 node2.color = tempColor;
124 }
125
126 // Swap data between two nodes
127 swapData(node1: RBTreeNode<T>, node2: RBTreeNode<T>): void {
128 const tempData = node1.data;
129 node1.data = node2.data;
130 node2.data = tempData;
131 }
132
133 // Fix Red-Black Tree properties after insertion
134 fixAfterInsert(currentNode: RBTreeNode<T>): void {
135 let parentNode = null;
136 let grandParentNode = null;
137
138 // Continue fixing until we reach root or find a valid configuration
139 while (currentNode !== this.root && currentNode.color !== 1 && currentNode.parent?.color === 0) {
140 parentNode = currentNode.parent;
141 grandParentNode = currentNode.parent.parent;
142
143 // Case A: Parent is left child of grandparent
144 if (parentNode === grandParentNode?.left) {
145 const uncleNode = grandParentNode.right;
146
147 // Case 1: Uncle is RED - only recoloring needed
148 if (uncleNode && uncleNode.color === 0) {
149 grandParentNode.color = 0;
150 parentNode.color = 1;
151 uncleNode.color = 1;
152 currentNode = grandParentNode;
153 } else {
154 // Case 2: Current node is right child - left rotation needed
155 if (currentNode === parentNode.right) {
156 this.rotateLeft(parentNode);
157 currentNode = parentNode;
158 parentNode = currentNode.parent;
159 }
160
161 // Case 3: Current node is left child - right rotation needed
162 this.rotateRight(grandParentNode);
163 this.swapColor(parentNode!, grandParentNode);
164 currentNode = parentNode!;
165 }
166 } else {
167 // Case B: Parent is right child of grandparent
168 const uncleNode = grandParentNode!.left;
169
170 // Case 1: Uncle is RED - only recoloring needed
171 if (uncleNode != null && uncleNode.color === 0) {
172 grandParentNode!.color = 0;
173 parentNode.color = 1;
174 uncleNode.color = 1;
175 currentNode = grandParentNode!;
176 } else {
177 // Case 2: Current node is left child - right rotation needed
178 if (currentNode === parentNode.left) {
179 this.rotateRight(parentNode);
180 currentNode = parentNode;
181 parentNode = currentNode.parent;
182 }
183
184 // Case 3: Current node is right child - left rotation needed
185 this.rotateLeft(grandParentNode!);
186 this.swapColor(parentNode!, grandParentNode!);
187 currentNode = parentNode!;
188 }
189 }
190 }
191
192 // Root must always be BLACK
193 this.root!.color = 1;
194 }
195
196 // Delete a single occurrence of the value
197 delete(value: T): boolean {
198 const nodeToDelete = this.find(value);
199 if (!nodeToDelete) return false;
200
201 nodeToDelete.count--;
202 if (!nodeToDelete.count) {
203 this.deleteNode(nodeToDelete);
204 }
205 return true;
206 }
207
208 // Delete all occurrences of the value
209 deleteAll(value: T): boolean {
210 const nodeToDelete = this.find(value);
211 if (!nodeToDelete) return false;
212
213 this.deleteNode(nodeToDelete);
214 return true;
215 }
216
217 // Delete a node from the tree
218 deleteNode(nodeToDelete: RBTreeNode<T>): void {
219 // Find replacement node using BST delete rules
220 const replacementNode = this.findBSTReplacement(nodeToDelete);
221
222 // Check if both nodes are BLACK
223 const bothBlack = (replacementNode === null || replacementNode.color === 1) && nodeToDelete.color === 1;
224 const parentNode = nodeToDelete.parent!;
225
226 if (!replacementNode) {
227 // Node to delete is a leaf
228 if (nodeToDelete === this.root) {
229 this.root = null;
230 } else {
231 if (bothBlack) {
232 // Both nodes are BLACK - fix double black
233 this.fixDoubleBlack(nodeToDelete);
234 } else {
235 // One node is RED - make sibling RED if exists
236 if (nodeToDelete.sibling()) {
237 nodeToDelete.sibling()!.color = 0;
238 }
239 }
240
241 // Remove node from tree
242 if (nodeToDelete.isOnLeft()) {
243 parentNode.left = null;
244 } else {
245 parentNode.right = null;
246 }
247 }
248 return;
249 }
250
251 if (!nodeToDelete.left || !nodeToDelete.right) {
252 // Node has one child
253 if (nodeToDelete === this.root) {
254 // Replace root with child
255 nodeToDelete.data = replacementNode.data;
256 nodeToDelete.left = null;
257 nodeToDelete.right = null;
258 } else {
259 // Replace node with child
260 if (nodeToDelete.isOnLeft()) {
261 parentNode.left = replacementNode;
262 } else {
263 parentNode.right = replacementNode;
264 }
265 replacementNode.parent = parentNode;
266
267 if (bothBlack) {
268 this.fixDoubleBlack(replacementNode);
269 } else {
270 replacementNode.color = 1;
271 }
272 }
273 return;
274 }
275
276 // Node has two children - swap with successor and delete
277 this.swapData(replacementNode, nodeToDelete);
278 this.deleteNode(replacementNode);
279 }
280
281 // Find replacement node for BST deletion
282 private findBSTReplacement(node: RBTreeNode<T>): RBTreeNode<T> | null {
283 // Two children - find inorder successor
284 if (node.left && node.right) {
285 return this.findSuccessor(node.right);
286 }
287
288 // Leaf node
289 if (!node.left && !node.right) {
290 return null;
291 }
292
293 // Single child
294 return node.left ?? node.right;
295 }
296
297 // Find the inorder successor (leftmost node in right subtree)
298 private findSuccessor(node: RBTreeNode<T>): RBTreeNode<T> {
299 let current = node;
300 while (current.left) {
301 current = current.left;
302 }
303 return current;
304 }
305
306 // Fix double black violation in Red-Black Tree
307 fixDoubleBlack(node: RBTreeNode<T>): void {
308 // Base case: reached root
309 if (node === this.root) return;
310
311 const siblingNode = node.sibling();
312 const parentNode = node.parent!;
313
314 if (!siblingNode) {
315 // No sibling - push double black up
316 this.fixDoubleBlack(parentNode);
317 } else {
318 if (siblingNode.color === 0) {
319 // Sibling is RED
320 parentNode.color = 0;
321 siblingNode.color = 1;
322
323 if (siblingNode.isOnLeft()) {
324 this.rotateRight(parentNode);
325 } else {
326 this.rotateLeft(parentNode);
327 }
328
329 this.fixDoubleBlack(node);
330 } else {
331 // Sibling is BLACK
332 if (siblingNode.hasRedChild()) {
333 // Sibling has at least one RED child
334 if (siblingNode.left && siblingNode.left.color === 0) {
335 if (siblingNode.isOnLeft()) {
336 // Left-Left case
337 siblingNode.left.color = siblingNode.color;
338 siblingNode.color = parentNode.color;
339 this.rotateRight(parentNode);
340 } else {
341 // Right-Left case
342 siblingNode.left.color = parentNode.color;
343 this.rotateRight(siblingNode);
344 this.rotateLeft(parentNode);
345 }
346 } else {
347 if (siblingNode.isOnLeft()) {
348 // Left-Right case
349 siblingNode.right!.color = parentNode.color;
350 this.rotateLeft(siblingNode);
351 this.rotateRight(parentNode);
352 } else {
353 // Right-Right case
354 siblingNode.right!.color = siblingNode.color;
355 siblingNode.color = parentNode.color;
356 this.rotateLeft(parentNode);
357 }
358 }
359 parentNode.color = 1;
360 } else {
361 // Sibling has two BLACK children
362 siblingNode.color = 0;
363
364 if (parentNode.color === 1) {
365 this.fixDoubleBlack(parentNode);
366 } else {
367 parentNode.color = 1;
368 }
369 }
370 }
371 }
372 }
373
374 // Insert a new value into the tree
375 insert(data: T): boolean {
376 // Find insertion position
377 let parentNode = this.root;
378 while (parentNode) {
379 if (this.lessThan(data, parentNode.data)) {
380 if (!parentNode.left) break;
381 parentNode = parentNode.left;
382 } else if (this.lessThan(parentNode.data, data)) {
383 if (!parentNode.right) break;
384 parentNode = parentNode.right;
385 } else {
386 // Value already exists - increment count
387 parentNode.count++;
388 return false;
389 }
390 }
391
392 // Create and insert new node
393 const newNode = new RBTreeNode(data);
394
395 if (!parentNode) {
396 this.root = newNode;
397 } else if (this.lessThan(newNode.data, parentNode.data)) {
398 parentNode.left = newNode;
399 } else if (this.lessThan(parentNode.data, newNode.data)) {
400 parentNode.right = newNode;
401 } else {
402 parentNode.count++;
403 return false;
404 }
405
406 newNode.parent = parentNode;
407 this.fixAfterInsert(newNode);
408 return true;
409 }
410
411 // Find a node with the given value
412 find(data: T): RBTreeNode<T> | null {
413 let currentNode = this.root;
414
415 while (currentNode) {
416 if (this.lessThan(data, currentNode.data)) {
417 currentNode = currentNode.left;
418 } else if (this.lessThan(currentNode.data, data)) {
419 currentNode = currentNode.right;
420 } else {
421 return currentNode;
422 }
423 }
424
425 return null;
426 }
427
428 // Generator for in-order traversal
429 *inOrder(rootNode: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
430 if (!rootNode) return;
431
432 yield* this.inOrder(rootNode.left!);
433 yield rootNode.data;
434 yield* this.inOrder(rootNode.right!);
435 }
436
437 // Generator for reverse in-order traversal
438 *reverseInOrder(rootNode: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
439 if (!rootNode) return;
440
441 yield* this.reverseInOrder(rootNode.right!);
442 yield rootNode.data;
443 yield* this.reverseInOrder(rootNode.left!);
444 }
445}
446
447// TreeSet implementation using Red-Black Tree
448class TreeSet<T = number> {
449 private _size: number;
450 private tree: RBTree<T>;
451 private compare: CompareFunction<T>;
452
453 constructor(
454 collection: T[] | CompareFunction<T> = [],
455 compare: CompareFunction<T> = (left: T, right: T) => (left < right ? -1 : left > right ? 1 : 0)
456 ) {
457 // Handle overloaded constructor
458 if (typeof collection === 'function') {
459 compare = collection;
460 collection = [];
461 }
462
463 this._size = 0;
464 this.compare = compare;
465 this.tree = new RBTree(compare);
466
467 // Add initial collection
468 for (const value of collection) {
469 this.add(value);
470 }
471 }
472
473 // Get the size of the set
474 size(): number {
475 return this._size;
476 }
477
478 // Check if value exists in the set
479 has(value: T): boolean {
480 return !!this.tree.find(value);
481 }
482
483 // Add a value to the set
484 add(value: T): boolean {
485 const wasSuccessful = this.tree.insert(value);
486 if (wasSuccessful) {
487 this._size++;
488 }
489 return wasSuccessful;
490 }
491
492 // Delete a value from the set
493 delete(value: T): boolean {
494 const wasDeleted = this.tree.deleteAll(value);
495 if (wasDeleted) {
496 this._size--;
497 }
498 return wasDeleted;
499 }
500
501 // Find the smallest value >= given value
502 ceil(value: T): T | undefined {
503 let currentNode = this.tree.root;
504 let result = null;
505
506 while (currentNode) {
507 if (this.compare(currentNode.data, value) >= 0) {
508 result = currentNode;
509 currentNode = currentNode.left;
510 } else {
511 currentNode = currentNode.right;
512 }
513 }
514
515 return result?.data;
516 }
517
518 // Find the largest value <= given value
519 floor(value: T): T | undefined {
520 let currentNode = this.tree.root;
521 let result = null;
522
523 while (currentNode) {
524 if (this.compare(value, currentNode.data) >= 0) {
525 result = currentNode;
526 currentNode = currentNode.right;
527 } else {
528 currentNode = currentNode.left;
529 }
530 }
531
532 return result?.data;
533 }
534
535 // Find the smallest value > given value
536 higher(value: T): T | undefined {
537 let currentNode = this.tree.root;
538 let result = null;
539
540 while (currentNode) {
541 if (this.compare(value, currentNode.data) < 0) {
542 result = currentNode;
543 currentNode = currentNode.left;
544 } else {
545 currentNode = currentNode.right;
546 }
547 }
548
549 return result?.data;
550 }
551
552 // Find the largest value < given value
553 lower(value: T): T | undefined {
554 let currentNode = this.tree.root;
555 let result = null;
556
557 while (currentNode) {
558 if (this.compare(currentNode.data, value) < 0) {
559 result = currentNode;
560 currentNode = currentNode.right;
561 } else {
562 currentNode = currentNode.left;
563 }
564 }
565
566 return result?.data;
567 }
568
569 // Get the smallest value in the set
570 first(): T | undefined {
571 return this.tree.inOrder().next().value;
572 }
573
574 // Get the largest value in the set
575 last(): T | undefined {
576 return this.tree.reverseInOrder().next().value;
577 }
578
579 // Remove and return the smallest value
580 shift(): T | undefined {
581 const firstValue = this.first();
582 if (firstValue === undefined) return undefined;
583
584 this.delete(firstValue);
585 return firstValue;
586 }
587
588 // Remove and return the largest value
589 pop(): T | undefined {
590 const lastValue = this.last();
591 if (lastValue === undefined) return undefined;
592
593 this.delete(lastValue);
594 return lastValue;
595 }
596
597 // Iterator implementation
598 *[Symbol.iterator](): Generator<T, void, void> {
599 yield* this.values();
600 }
601
602 // Get all keys (same as values for a set)
603 *keys(): Generator<T, void, void> {
604 yield* this.values();
605 }
606
607 // Get all values in ascending order
608 *values(): Generator<T, undefined, void> {
609 yield* this.tree.inOrder();
610 return undefined;
611 }
612
613 // Get all values in descending order
614 *rvalues(): Generator<T, undefined, void> {
615 yield* this.tree.reverseInOrder();
616 return undefined;
617 }
618}
619
620// TreeMultiSet implementation (allows duplicates)
621class TreeMultiSet<T = number> {
622 private _size: number;
623 private tree: RBTree<T>;
624 private compare: CompareFunction<T>;
625
626 constructor(
627 collection: T[] | CompareFunction<T> = [],
628 compare: CompareFunction<T> = (left: T, right: T) => (left < right ? -1 : left > right ? 1 : 0)
629 ) {
630 // Handle overloaded constructor
631 if (typeof collection === 'function') {
632 compare = collection;
633 collection = [];
634 }
635
636 this._size = 0;
637 this.compare = compare;
638 this.tree = new RBTree(compare);
639
640 // Add initial collection
641 for (const value of collection) {
642 this.add(value);
643 }
644 }
645
646 // Get the total size of the multiset
647 size(): number {
648 return this._size;
649 }
650
651 // Check if value exists in the multiset
652 has(value: T): boolean {
653 return !!this.tree.find(value);
654 }
655
656 // Add a value to the multiset (allows duplicates)
657 add(value: T): boolean {
658 this.tree.insert(value);
659 this._size++;
660 return true;
661 }
662
663 // Delete a single occurrence of the value
664 delete(value: T): boolean {
665 const wasSuccessful = this.tree.delete(value);
666 if (wasSuccessful) {
667 this._size--;
668 }
669 return wasSuccessful;
670 }
671
672 // Count occurrences of a value
673 count(value: T): number {
674 const node = this.tree.find(value);
675 return node ? node.count : 0;
676 }
677
678 // Find the smallest value >= given value
679 ceil(value: T): T | undefined {
680 let currentNode = this.tree.root;
681 let result = null;
682
683 while (currentNode) {
684 if (this.compare(currentNode.data, value) >= 0) {
685 result = currentNode;
686 currentNode = currentNode.left;
687 } else {
688 currentNode = currentNode.right;
689 }
690 }
691
692 return result?.data;
693 }
694
695 // Find the largest value <= given value
696 floor(value: T): T | undefined {
697 let currentNode = this.tree.root;
698 let result = null;
699
700 while (currentNode) {
701 if (this.compare(value, currentNode.data) >= 0) {
702 result = currentNode;
703 currentNode = currentNode.right;
704 } else {
705 currentNode = currentNode.left;
706 }
707 }
708
709 return result?.data;
710 }
711
712 // Find the smallest value > given value
713 higher(value: T): T | undefined {
714 let currentNode = this.tree.root;
715 let result = null;
716
717 while (currentNode) {
718 if (this.compare(value, currentNode.data) < 0) {
719 result = currentNode;
720 currentNode = currentNode.left;
721 } else {
722 currentNode = currentNode.right;
723 }
724 }
725
726 return result?.data;
727 }
728
729 // Find the largest value < given value
730 lower(value: T): T | undefined {
731 let currentNode = this.tree.root;
732 let result = null;
733
734 while (currentNode) {
735 if (this.compare(currentNode.data, value) < 0) {
736 result = currentNode;
737 currentNode = currentNode.right;
738 } else {
739 currentNode = currentNode.left;
740 }
741 }
742
743 return result?.data;
744 }
745
746 // Get the smallest value in the multiset
747 first(): T | undefined {
748 return this.tree.inOrder().next().value;
749 }
750
751 // Get the largest value in the multiset
752 last(): T | undefined {
753 return this.tree.reverseInOrder().next().value;
754 }
755
756 // Remove and return the smallest value
757 shift(): T | undefined {
758 const firstValue = this.first();
759 if (firstValue === undefined) return undefined;
760
761 this.delete(firstValue);
762 return firstValue;
763 }
764
765 // Remove and return the largest value
766 pop(): T | undefined {
767 const lastValue = this.last();
768 if (lastValue === undefined) return undefined;
769
770 this.delete(lastValue);
771 return lastValue;
772 }
773
774 // Iterator implementation
775 *[Symbol.iterator](): Generator<T, void, void> {
776 yield* this.values();
777 }
778
779 // Get all keys (includes duplicates)
780 *keys(): Generator<T, void, void> {
781 yield* this.values();
782 }
783
784 // Get all values including duplicates in ascending order
785 *values(): Generator<T, undefined, void> {
786 for (const value of this.tree.inOrder()) {
787 let occurrences = this.count(value);
788 while (occurrences--) {
789 yield value;
790 }
791 }
792 return undefined;
793 }
794
795 // Get all values including duplicates in descending order
796 *rvalues(): Generator<T, undefined, void> {
797 for (const value of this.tree.reverseInOrder()) {
798 let occurrences = this.count(value);
799 while (occurrences--) {
800 yield value;
801 }
802 }
803 return undefined;
804 }
805}
806
807// Initialize the infinite set on module load
808initializeSmallestInfiniteSet();
809
Time and Space Complexity
Time Complexity:
__init__()
:O(n)
wheren = 1000
, as it creates a SortedSet with 1000 elementspopSmallest()
:O(log n)
for accessing the smallest element and removing it from the SortedSetaddBack()
:O(log n)
for adding an element back to the SortedSet while maintaining sorted order
Space Complexity: O(n)
where n
represents the maximum number of elements stored in the set. Initially, the set stores 1000 elements (from 1 to 1000), so the space complexity is O(1000) = O(n)
. Even though elements can be popped and added back, the maximum space used is bounded by the initial range of values, making the overall space complexity O(n)
.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Dependency on External Library
The solution relies on sortedcontainers.SortedSet
, which isn't part of Python's standard library. This can cause issues in coding interviews or platforms that don't support external libraries.
Solution: Implement using standard library components:
import heapq
class SmallestInfiniteSet:
def __init__(self):
self.next_num = 1 # Track the next consecutive number
self.added_back = [] # Min heap for numbers added back
self.added_set = set() # Track what's in the heap to avoid duplicates
def popSmallest(self) -> int:
if self.added_back:
smallest = heapq.heappop(self.added_back)
self.added_set.remove(smallest)
return smallest
else:
smallest = self.next_num
self.next_num += 1
return smallest
def addBack(self, num: int) -> None:
if num < self.next_num and num not in self.added_set:
heapq.heappush(self.added_back, num)
self.added_set.add(num)
2. Memory Inefficiency with Pre-population
Pre-populating 1000 elements wastes memory when only a few operations are performed. If the problem constraints change to allow larger numbers, this approach becomes impractical.
Solution: Use a lazy approach that tracks only the numbers that have been removed or added back, using a pointer for the next consecutive number in the infinite sequence.
3. Not Handling Edge Cases in addBack
A common mistake is not checking whether the number being added back:
- Was actually removed before (is less than the current smallest consecutive number)
- Is already in the set (duplicate addition)
Solution: Always validate:
def addBack(self, num: int) -> None:
# Only add if it was previously popped and not already added back
if num < self.next_num and num not in self.added_set:
heapq.heappush(self.added_back, num)
self.added_set.add(num)
4. Incorrect Assumption About Number Range
Assuming numbers will always be within 1-1000 without verifying problem constraints can lead to failures if larger numbers are added back.
Solution: Either clarify constraints or implement a dynamic approach that doesn't rely on a fixed range, using the combination of a counter and heap as shown above.
Which of these properties could exist for a graph but not a tree?
Recommended Readings
https assets algo monster cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue is a data structure
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!