Find the biggest interval that has all its members in list in O(n) [duplicate]

Question

I was asked this in an interview. Given a list of integers, How can we find the biggest interval that has all its members in the given list?

E.g. given list 1,3,5,7,4,6,10 then answer would be [3, 7]. Because it has all the elements between 3 and 7.

I tried to answer but I wasn't convincing. The approach I took was to first sort the list and then check it for the biggest interval. But I was asked to do so in O(n).

Answer 1

I know a solution based on hashing and dynamic programming. Let f(x) be the hash function. The trick is the hash-table value. Consider the longest interval contained in the list, which either starts or ends with x. Then h[f(x)] = y, where y is the other end of that interval. Note that length of that interval will be abs( x - y ) + 1. The algorithm description will make clear why to store that value.

Move over the list. Let i be current index, x := list[ i ] - current number. Now

1. if h[f(x)] is not empty, then we've met number x before. Nothing to do, continue.

2. Check h[f(x-1)] and h[f(x+1)].

2.1. If they're both not empty, that means we've already met x-1 and x+1, and we know some intervals [a..x-1] and [x+1..b] which we've already met in the list. We know it because a=h[f(x-1)] and b=h[f(x+1)] by definition of h. Now when we got x, it means that we now have met the whole interval [a,b], so we update values as follows: h[f(a)] := b and h[f(b)] := a.
Also set h[f(x)] to some value (let's say x, not to impact the answer), just so that next time we meet x in the list, we ignore it. x has already done his job.

2.2. If only one of them is set, let's say h[f(x-1)] = a, that means we've already met some interval [a..x-1], and now it's extended with x. Update will be h[f(a)] := x and h[f(x)] := a.

2.3. If none of them is set, that means we've met neither x-1, nor x+1, and the biggest interval containing x we've already met is the single [x] itself. So set h[f(x)] := x.

Finally, to get the answer, pass over the whole list and take maximum abs( x - h[f(x)] ) + 1 for all x.

Answer 2

If sorting is not desirable, you can use a combination of hash map and Disjoint-set data structure.

For each element in the list create a node and insert it into hash map with key = element's value. Then query the hash map for value+1 and value-1. If anything is found, combine current node with set(s) where adjacent nodes belong. When finished with the list, the largest set corresponds to the biggest interval.

Time complexity is O(N * α(N)) where α(N) is inverse Ackermann function.

Edit: Actually Disjoint-set is too powerful for this simple task. Solution by Grigor Gevorgyan does not use it. So it is simpler and more efficient.