Find the biggest interval that has all its members

Question

This question already has answers here:

Finding contiguous ranges in arrays (8 answers)

Longest Consecutive Sequence in an Unsorted Array [duplicate] (8 answers)

Closed 6 years ago.

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

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.

Answer 2

I think I would have sorted them into lists of consecutive integers (assuming each number can appear only once)

take first number

if the number 1 lower than or 1 higher than a number in an existing list?

yes: pre/post pend existing list

no : create a new list starting with the current number

if there are more numbers, return to top

display the longest list

Answer 3

I crafted a very straightforward solution using a HashSet. Since contains and remove are O(1) operations, you can simply create a new interval from a random set item and 'expand' the interval it until you discover its full size, removing items from the set as you go along. The removal is key, because this is what prevents you from 'repeating' any intervals.

It might help to think about it this way - the list has K intervals, whose sizes add up to N. Your task, then, is to discover what these intervals are, without repeating any intervals or items. This is why the HashSet is perfect for the job - you can efficiently remove items from the set as you expand your intervals. Then all you need to do is keep track of the largest interval as you go along.

1. Put the list into a HashSet
2. While the set is non-empty:
   1. remove an item at random from the set
   2. Define a new interval from that item
   3. Expand the interval as follows:
      1. Define i = interval.start-1
      2. While the set contains i, remove i from the set and decrement both i and interval.start
      3. Repeat step 2 in the other direction (expand up from interval.end)
   4. If the expanded interval is larger than the previously largest interval, record the new interval as the largest interval
3. Return the largest interval

Here is the solution in Java:

public class BiggestInterval {

    static class Interval {
        int start;
        int end;

        public Interval(int base) {
            this(base,base);
        }

        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }

        public int size() {
            return 1 + end - start;
        }

        @Override
        public String toString() {
            return "[" + start + "," + end + "]";
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(biggestInterval(Arrays.asList(1,3,5,7,4,6,10)));
    }

    public static Interval biggestInterval(List<Integer> list) {
        HashSet<Integer> set = new HashSet<Integer>(list);
        Interval largest = null;

        while(set.size() > 0) {
            Integer item = set.iterator().next();
            set.remove(item);

            Interval interval = new Interval(item);
            while(set.remove(interval.start-1)) {
                interval.start--;
            }
            while(set.remove(interval.end+1)) {
                interval.end++;
            }

            if (largest == null || interval.size() > largest.size()) {
                largest = interval;
            }
        }

        return largest;
    }
}

Answer 4

You can trade off space to get this in linear time.

1. Scan the list for the smallest and largest values, S and L.
2. Use an array of booleans or a bitvector, A, large enough to hold (L - S + 1) entries.
3. Go through the list again, setting the appropriate element of A to true when you see it.
4. Now, A is sorted. Go through A and find the largest consecutive set of true values.

The first steps are linear in your list. The last is linear in the size of A, which could be large relative to your list if you have just a few values which are far apart. But, since you're dealing with ints, A is bounded.