Leetcode daily # 25.04.2023

[2336. Smallest Number in Infinite Set]

25.04.2023

2336. Smallest Number in Infinite Set medium

class SmallestInfiniteSet() {
    val links = IntArray(1001) { it + 1 }

    fun popSmallest(): Int {
        val smallest = links[0]
        val next = links[smallest]
        links[smallest] = 0
        links[0] = next
        return smallest
    }

    fun addBack(num: Int) {
        if (links[num] == 0) {
            var maxLink = 0
            while (links[maxLink] <= num) maxLink = links[maxLink]
            val next = links[maxLink]
            links[maxLink] = num
            links[num] = next
        }
    }

}

blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/191

Intuition

Given the constraints, we can hold every element as a link node to another in an Array. This will give us O(1) time for pop operation, but O(n) for addBack in the worst case.
A more asymptotically optimal solution, is to use a TreeSet and a single pointer to the largest popped element.

Approach

Let’s implement a sparse array.

Complexity

• Time complexity:
  O(1) - for pop
  O(n) - constructor and addBack

• Space complexity:
  O(n)