2336. Smallest Number in Infinite Set

Smallest Number in Infinite Set (LeetCode 2336) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Design (General/Specific) subpattern.

How to solve Smallest Number in Infinite Set

Smallest Number in Infinite Set is a Data Structure Design problem, part of Design Patterns. Design and implement data structures: LRU cache, LFU cache, HashMap, and specialized structures.

Work towards the solution in these steps:

1. Based on the constraints, what is the maximum element that can possibly be popped?
2. Maintain whether elements are in or not in the set. How many elements do we consider?

The reference solution runs in O(log n) time and O(k) space.

The Smallest Number in Infinite Set solution and editorial walks through the full approach with reference code.

Problem statement

You have a set which contains all positive integers [1, 2, 3, 4, 5, ...].

Implement the SmallestInfiniteSet class:

- SmallestInfiniteSet() Initializes the SmallestInfiniteSet object to contain all positive integers.

- int popSmallest() Removes and returns the smallest integer contained in the infinite set.

- void addBack(int num) Adds a positive integer num back into the infinite set, if it is not already in the infinite set.

Example 1:

Input ["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"] [[], [2], [], [], [], [1], [], [], []] Output [null, null, 1, 2, 3, null, 1, 4, 5]

Explanation SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet(); smallestInfiniteSet.addBack(2); // 2 is already in the set, so no change is made. smallestInfiniteSet.popSmallest(); // return 1, since 1 is the smallest number, and remove it from the set. smallestInfiniteSet.popSmallest(); // return 2, and remove it from the set. smallestInfiniteSet.popSmallest(); // return 3, and remove it from the set. smallestInfiniteSet.addBack(1); // 1 is added back to the set. smallestInfiniteSet.popSmallest(); // return 1, since 1 was added back to the set and // is the smallest number, and remove it from the set. smallestInfiniteSet.popSmallest(); // return 4, and remove it from the set. smallestInfiniteSet.popSmallest(); // return 5, and remove it from the set.

Constraints:

- 1 <= num <= 1000

- At most 1000 calls will be made in total to popSmallest and addBack.

Topics and companies

Topics: Hash Table, Design, Heap (Priority Queue), Ordered Set.

How to practise Smallest Number in Infinite Set on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(log n) time and O(k) space.

Open Smallest Number in Infinite Set in the code editor, or read the Smallest Number in Infinite Set editorial for a worked solution with its approach and complexity analysis.

Where Smallest Number in Infinite Set sits in the DSA pattern sheet

• Design Patterns pattern guide
• Design (General/Specific) subpattern
• The full DSA patterns sheet

Problems related to Smallest Number in Infinite Set

Other problems that use the same Design (General/Specific) and Design Patterns techniques:

• All O`one Data Structure — Hard, same subpattern
• Design a Stack With Increment Operation — Medium, same subpattern
• Design a Text Editor — Hard, same subpattern
• Design Circular Deque — Medium, same subpattern
• Design Circular Queue — Medium, same subpattern
• Design Compressed String Iterator — Easy, same subpattern

Smallest Number in Infinite Set FAQ