We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Smallest Number in Infinite Set

Number: 2413

Difficulty: Medium

Paid? No

Companies: Google, Uber, Amazon

Problem Description

Design a data structure that initially contains all positive integers. The data structure supports two operations: popSmallest(), which removes and returns the smallest number in the set, and addBack(num), which adds a number back into the set if it is not presently contained. The challenge is to manage these operations efficiently without explicitly storing an infinite set.

Key Insights

  • Use a min-heap to efficiently track and retrieve the smallest number that has been added back.
  • Maintain a variable (e.g., nextAvailable) to track the next number in the natural sequence that has not yet been popped.
  • Use a hash set to prevent duplicate additions into the min-heap.
  • When popSmallest() is called, compare the top of the heap with the nextAvailable value to decide which number to return.

Space and Time Complexity

Time Complexity: O(log n) for popSmallest() and addBack() calls (where n is the size of the heap) in the worst case, though average operations tend to be faster. Space Complexity: O(m) where m is the number of integers currently added back into the heap, which is bounded by the number of addBack operations.

Solution

The solution uses a combination of a min-heap and a pointer. The pointer (nextAvailable) starts at 1, representing the smallest integer not yet popped. The addBack function re-inserts a number into our min-heap if it has already been removed, ensuring no duplicate entries are added by checking an auxiliary hash set. When popSmallest() is executed, we first check the heap: if it’s non-empty and holds a number smaller than nextAvailable, pop and return that number; otherwise, return nextAvailable and increment it. This approach ensures that we efficiently track the smallest available number from our infinite set.

Code Solutions

import heapq

class SmallestInfiniteSet:
    def __init__(self):
        # Next number from the infinite set that hasn't been popped
        self.next_available = 1
        # Min-heap to store numbers that have been added back
        self.heap = []
        # Set to quickly check if a number is already in the heap
        self.added_back = set()

    def popSmallest(self):
        # If there are numbers added back, use the smallest among them
        if self.heap and self.heap[0] < self.next_available:
            smallest = heapq.heappop(self.heap)
            self.added_back.remove(smallest)
            return smallest
        # Otherwise return the next available number
        result = self.next_available
        self.next_available += 1
        return result

    def addBack(self, num):
        # Only add num back if it was already popped
        if num < self.next_available and num not in self.added_back:
            heapq.heappush(self.heap, num)
            self.added_back.add(num)
← Back to All Questions