Returning the lowest integer not in a list in SQL
sql, sqlite
Solution
Because SQL works on sets, the intermediate `SELECT DISTINCT a AS x FROM t ORDER BY a` is redundant.
The basic technique of looking for a gap in a column of integers is to find where the current entry plus 1 does not exist. This requires a self-join of some sort.
Your query is not far off, but I think it can be simplified to:
SELECT MIN(a) + 1
FROM t
WHERE a + 1 NOT IN (SELECT a FROM t)
The NOT IN acts as a sort of self-join. This won't produce anything from an empty table, but should be OK otherwise.
Problem
Supposed you have a table `T(A)` with only positive integers allowed, like: ``` 1,1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18 ``` In the above example, the result is `10`. We always can use `ORDER BY` and `DISTINCT` to sort and remove duplicates. However, to find the lowest integer not in the list, I came up with the following `SQL` query: ``` select list.x + 1 from (select x from (select distinct a as x from T order by a)) as list, T where list.x + 1 not in T limit 1; ``` My idea is start a `counter` and 1, check if that counter is in `list`: if it is, return it, otherwise increment and look again. However, I have to start that counter as 1, and then increment. That query works most of the cases, by there are some corner cases like in `1`. How can I accomplish that in `SQL` or should I go about a completely different direction to solve this problem?