smallest-number-in-infinite-set

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

Algorithms

You have a set which contains all positive integers <code>[1, 2, 3, 4, 5, ...]</code>.

Implement the <code>SmallestInfiniteSet</code> class:

<ul>
	<li><code>SmallestInfiniteSet()</code> Initializes the SmallestInfiniteSet object to contain all positive integers.</li>
	<li><code>int popSmallest()</code> Removes and returns the smallest integer contained in the infinite set.</li>
	<li><code>void addBack(int num)</code> Adds a positive integer <code>num</code> back into the infinite set, if it is not already in the infinite set.</li>
</ul>

&nbsp;
Example 1:

<pre>
Input
[&quot;SmallestInfiniteSet&quot;, &quot;addBack&quot;, &quot;popSmallest&quot;, &quot;popSmallest&quot;, &quot;popSmallest&quot;, &quot;addBack&quot;, &quot;popSmallest&quot;, &quot;popSmallest&quot;, &quot;popSmallest&quot;]
[[], [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.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= num &lt;= 1000</code></li>
	<li>At most <code>1000</code> calls will be made in total to <code>popSmallest</code> and <code>addBack</code>.</li>
</ul>