LeetCode Entry

2336. Smallest Number in Infinite Set

25.04.2023 medium 2023 kotlin

Let's implement a sparse array.

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 substack

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)\)