LeetCode 2336: Smallest Number in Infinite Set Solution

Master LeetCode problem 2336 (Smallest Number in Infinite Set), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2336. Smallest Number in Infinite Set

Medium

Hash Table Design Heap (Priority Queue)Ordered Set

Problem Explanation

Explanation

To solve this problem, we can maintain a priority queue (min-heap) to store the positive integers in our infinite set. When we need to pop the smallest integer, we can simply remove and return the top element from the priority queue. When we add a positive integer back into the set, we check if it is already in the set. If not, we add it to the priority queue. This way, we always have the smallest integer at the top of the priority queue.

Algorithm:
1. Initialize a priority queue to store positive integers.
2. Implement a constructor SmallestInfiniteSet() to initialize the object.
3. Implement the popSmallest() method to remove and return the smallest integer from the priority queue.
4. Implement the addBack(int num) method to add a positive integer back into the priority queue if it is not already present.
Time Complexity:
- For each operation (popSmallest and addBack), the time complexity is O(log n) where n is the number of elements in the priority queue.
Space Complexity:
- The space complexity is O(n) to store the elements in the priority queue.

Solution Code

import java.util.PriorityQueue;

class SmallestInfiniteSet {
    private PriorityQueue<Integer> pq;

    public SmallestInfiniteSet() {
        pq = new PriorityQueue<>();
    }

    public int popSmallest() {
        return pq.poll();
    }

    public void addBack(int num) {
        if (!pq.contains(num)) {
            pq.offer(num);
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2336 (Smallest Number in Infinite Set)?

This page provides optimized solutions for LeetCode problem 2336 (Smallest Number in Infinite Set) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2336 (Smallest Number in Infinite Set)?

The time complexity for LeetCode 2336 (Smallest Number in Infinite Set) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2336 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2336 in Java, C++, or Python.

Back to LeetCode Solutions