java - Longest sequence of numbers -

i asked question in interview give o(nlogn) solution, couldn't find logic o(n) . can me o(n) solution?

in array find length of longest sequence of numbers

example : input : 2 4 6 7 3 1 output: 4 (because 1,2,3,4 sequence though not in consecutive positions)

the solution should realistic in terms of space consumed . i.e solution should realistic array of 1 billion numbers

for non-consecutive numbers needs means of sorting them in o(n). in case can use bitset.

int[] ints = {2, 4, 6, 7, 3, 1}; bitset bs = new bitset(); intstream.of(ints).foreach(bs::set);   // can search longer consecutive sequence. int last = 0, max = 0; {     int set = bs.nextsetbit(last);     int clear = bs.nextclearbit(set + 1);     int len = clear - set;     if (len > max)         max = len;     last = clear; } while (last > 0); system.out.println(max);