CODEWITHSUNDEEP
javaarraysalgorithmarraylistlongest-substring
Amogh Huilgol
Amogh Huilgol

Reputation: 1282

Longest sequence of numbers

I was recently asked this question in an interview for which i could give an O(nlogn) solution, but couldn't find a logic for O(n) . Can someone help me with O(n) solution?

In an array find the length of longest sequence of numbers

Example : Input : 2 4 6 7 3 1 Output: 4 (because 1,2,3,4 is a sequence even though they are not in consecutive positions)

The solution should also be realistic in terms of space consumed . i.e the solution should be realistic even with an array of 1 billion numbers

Upvotes: 2

Views: 633

Answers (2)

Miljen Mikic
Miljen Mikic

Reputation: 15241

Traverse the array once and build the hash map whose key is a number from the input array and value is a boolean variable indicating whether the element has been processed or not (initially all are false). Traverse once more and do the following: when you check number a, put value true for that element in the hash map and immediately check the hash map for the existence of the elements a-1 and a+1. If found, denote their values in the hash map as true and proceed checking their neighbors, incrementing the length of the current contigous subsequence. Stop when there are no neighbors, and update longest length. Move forward in the array and continue checking unprocessed elements. It is not obvious at the first glance that this solution is O(n), but there are only two array traversals and hash map ensures that every element of the input is processed only once.

Main lesson - if you have to reduce time complexity, it is often neccesary to use additional space.

Upvotes: 1

Peter Lawrey
Peter Lawrey

Reputation: 533520

For non-consecutive numbers you needs a means of sorting them in O(n). In this case you can use BitSet.

int[] ints = {2, 4, 6, 7, 3, 1};
BitSet bs = new BitSet();
IntStream.of(ints).forEach(bs::set); 

// you can search for the longer consecutive sequence.
int last = 0, max = 0;
do {
    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);

Upvotes: 3

Related Questions