Taro Logo

Smallest Number in Infinite Set

Medium
Asked by:
Profile picture
0 views
Topics:
Greedy AlgorithmsArrays

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.
Try coding it in LeetCodeLeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Regarding the `addBack(num)` method, if I call it with a number that has never been popped, for example `addBack(10)` immediately after initialization, is this number considered 'already in the set' and thus the operation should be a no-op?
  2. When `popSmallest` is called, it should return the overall smallest available integer. Does this mean it should be the minimum of any numbers that have been explicitly added back via `addBack`, and the smallest positive integer that has not yet been returned by `popSmallest`?
  3. The constraints state that `num` for `addBack` will be between 1 and 1000. Is it safe to assume all test case inputs will adhere to this, or should I implement validation for out-of-range or non-positive values?
  4. The problem refers to an 'infinite set', but the number of calls is limited to 1000. Does this imply that the internal state I need to manage will also be bounded? For instance, will the number of elements I need to track separately (e.g., those added back) be at most 1000?
  5. Are there any concurrency considerations for this class? For instance, could `popSmallest` and `addBack` be called concurrently from multiple threads on the same object?

Brute Force Solution

Approach

The brute force strategy imagines an infinite line of all positive numbers starting from one. To find the smallest available number, it walks down this line from the beginning, checking each number one by one to see if it has been previously taken.

Here's how the algorithm would work step-by-step:

  1. First, we need a way to remember which numbers have been taken. We can keep a separate collection just for the numbers that have been removed.
  2. When we need to find the smallest available number, we start our search at the number one.
  3. We check our collection of removed numbers to see if one is in it. If it's not, then one is our answer.
  4. If one has been removed, we move on and check the number two in the same way. Then we check three, and so on.
  5. We continue this process, checking every whole number in order, until we find the first one that is not in our collection of removed numbers.
  6. Once we find this smallest available number, we must add it to our collection of removed numbers to mark it as taken for the future.
  7. If we are asked to add a number back, we first look through our entire collection of removed numbers.
  8. If the number we're adding back is found in our collection, we take it out, making it available again.

Code Implementation

class SmallestInfiniteSet:
    def __init__(self):
        self.next_available_positive_integer = 1
        self.returned_numbers_collection = []

    def popSmallest(self):
        smallest_number_candidate = self.next_available_positive_integer

        # We must exhaustively check the returned numbers in case a smaller one was added back.

        for number in self.returned_numbers_collection:
            if number < smallest_number_candidate:
                smallest_number_candidate = number
        
        # This logic correctly updates state based on where the smallest number was found.

        if smallest_number_candidate in self.returned_numbers_collection:
            self.returned_numbers_collection.remove(smallest_number_candidate)
        else:
            self.next_available_positive_integer += 1
        
        return smallest_number_candidate

    def addBack(self, number_to_add_back):
        # A number can only be added back if it was popped and is not already in the returned list.

        if number_to_add_back < self.next_available_positive_integer and number_to_add_back not in self.returned_numbers_collection:
            self.returned_numbers_collection.append(number_to_add_back)

Big(O) Analysis

Time Complexity
O(n²) – Let n be the number of items that have been popped from the set. The `popSmallest` operation drives the complexity, as it must find the first positive integer not in the collection of `n` removed numbers. This involves an outer loop that searches starting from 1, and for each candidate number, it must scan the entire list of `n` removed items in an inner loop. In the worst-case scenario, the algorithm checks n+1 candidates, resulting in approximately (n+1) * n total checks, which simplifies to O(n²).
Space Complexity
O(N) – The primary contributor to auxiliary space is the collection used to remember which numbers have been taken. Let N represent the total number of operations performed. In the worst-case scenario, consisting of N calls to pop the smallest number, this collection will grow to store N distinct integers. Therefore, the space required is directly proportional to the number of pop operations, leading to a space complexity of O(N).

Optimal Solution

Approach

The core idea is to treat the infinite numbers as a continuous stream and handle any returned numbers separately. We keep track of the next available number in the stream and maintain a special, sorted group for numbers that are added back. To find the smallest, we just pick the smaller of the two: the next in the stream or the smallest from the special group.

Here's how the algorithm would work step-by-step:

  1. Imagine all positive integers as a long, unending line starting from 1. We'll keep a marker on the first number in this line that we haven't given out yet. This marker starts at 1.
  2. We also need a separate place to hold any numbers that are given back to us. Think of this as a special holding pen, where we always keep the numbers sorted from smallest to largest.
  3. When asked for the smallest number, we first check if our special holding pen has any numbers in it.
  4. If the holding pen is empty, the answer is simply the number our marker is pointing to in the long line. We provide this number and then move our marker to the next one.
  5. If the holding pen is not empty, we have two candidates for the smallest number: the first number in our sorted holding pen, and the number our marker points to in the long line.
  6. We compare these two candidates and provide whichever one is smaller. If we took the number from the holding pen, we remove it. If we took it from the long line, we advance our marker.
  7. When a number is returned to the set, we only accept it under two conditions: it must be smaller than the number our marker currently points to, and it must not already be in our holding pen.
  8. If we accept the returned number, we place it in the holding pen, making sure the pen remains sorted so the smallest number is always at the front and easy to find.

Code Implementation

class SmallestInfiniteSet:
    def __init__(self):
        # Tracks the next integer from the infinite sequence that has not yet been popped.

        self.next_sequential_integer = 1

        # A min-heap stores numbers added back, while a set ensures uniqueness and fast lookups.

        self.re_added_numbers_min_heap = []
        self.re_added_numbers_set = set()

    def popSmallest(self) -> int:
        # Decide whether the smallest number is from the re-added pool or the continuous sequence.

        if self.re_added_numbers_min_heap and self.re_added_numbers_min_heap[0] < self.next_sequential_integer:
            smallest_re_added_number = heapq.heappop(self.re_added_numbers_min_heap)
            self.re_added_numbers_set.remove(smallest_re_added_number)
            return smallest_re_added_number
        
        # If re-added numbers aren't smaller, take the next integer from the main sequence.

        popped_from_sequence = self.next_sequential_integer
        self.next_sequential_integer += 1
        return popped_from_sequence

    def addBack(self, number_to_add: int) -> None:
        # Only re-add a number if it's smaller than the sequence counter and not already present.

        if number_to_add < self.next_sequential_integer and number_to_add not in self.re_added_numbers_set:
            heapq.heappush(self.re_added_numbers_min_heap, number_to_add)
            self.re_added_numbers_set.add(number_to_add)

Big(O) Analysis

Time Complexity
O(log k) – Let k be the number of elements in the special holding pen for returned numbers. The primary cost of the operations is driven by maintaining this pen in a sorted order. When popping the smallest number, if the number comes from the pen, removing it from an efficient sorted structure like a min-heap requires O(log k) operations. Similarly, when adding a number back, inserting it into the pen while preserving the sorted property also takes O(log k) time. Therefore, the time complexity for the main operations is logarithmic with respect to the number of elements returned to the set.
Space Complexity
O(N) – The space complexity is determined by the "special holding pen" used to store numbers that are added back to the set. This corresponds to an auxiliary data structure, typically a min-heap or a sorted set, which holds the returned numbers. If we define N as the total number of `addBack` operations, in the worst-case scenario, this holding pen could store up to N distinct numbers. Consequently, the memory required grows linearly with the number of `addBack` calls, resulting in O(N) auxiliary space.

Edge Cases

Calling `addBack` with a number that has not been previously popped from the set.
How to Handle:
The implementation ignores this operation as the number is already considered part of the infinite set of available integers.
Calling `addBack(num)` multiple times for the same number before it is popped again.
How to Handle:
An auxiliary hash set tracks added-back numbers to prevent duplicate entries in the data structure, making the redundant calls no-ops.
A very small number is added back after a long sequence of `popSmallest` calls.
How to Handle:
A min-heap ensures the globally smallest number is always returned, correctly prioritizing the small added-back number over the next larger sequential integer.
The pool of added-back numbers becomes empty, and `popSmallest` is called.
How to Handle:
The solution seamlessly transitions from returning numbers from the added-back pool to drawing from the main continuous sequence of integers.
Calling `addBack` on a newly initialized set before any elements are removed.
How to Handle:
Since all positive integers are already present, the logic correctly identifies that the number is in the set and the operation has no effect.
A number is immediately added back right after it has been popped.
How to Handle:
The solution correctly removes the number and then places it into the collection of added-back items, making it available for the next `popSmallest` call.
The total number of operations reaches the specified maximum constraint of 1000 calls.
How to Handle:
Using a min-heap and hash set ensures all operations have efficient time complexities, scaling well up to the given constraints.
The number passed to `addBack` is the smallest possible value, which is 1.
How to Handle:
The logic is generalized for any positive integer and correctly handles re-inserting 1, making it the top priority to be popped next.
Taro Footer Icon
Taro Footer Logo
Explore Interview QuestionsTaro 75Google Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Interview ExperiencesOpenAI Interview ExperiencesAnthropic Interview ExperiencesPerplexity Interview ExperiencesWindsurf Interview ExperiencesMistral AI Interview Experiences
Explore TrendingLayoffsPerformance Improvement PlanSystem DesignInterpersonal CommunicationTech Lead
ProductGreat DiscussionsPerksTopics
CompanyPrivacy PolicyTerms & ConditionsSupport
Taro iOS appTaro Android app
LinkedIn IconTwitter IconYouTube Icon
Copyright © Taro