Given an int array which might contain duplicates, find the largest subset of it which form a sequence.
Ex: {1,6,10,4,7,9,5}
then ans is 4,5,6,7
Sorting is an obvious solution. Can this be done in O(n) time ??
Thanks in advance
Given an int array which might contain duplicates, find the largest subset of it which form a sequence.
Ex: {1,6,10,4,7,9,5}
then ans is 4,5,6,7
Sorting is an obvious solution. Can this be done in O(n) time ??
Thanks in advance
Finally did it with the help of a friend β¦Here goes the solution using HashMap ::
Solution Using HashMap O(n) complexity
Explanation ::
One run with one hash table:
Keep in hash table using the numbers as keys of a structure containing two numbers: the first (F) and the last (L) element of a possible chain. Only first and last element of the chain need to be properly updated. When you insert an element N in the table check also for the neighbors (N-1 and N+1). We will call β(N)->Fβ The number stored as first of a possible chain in the Nth position and β(N)->Lβ the number stored as last of the chain. Possible cases are:
The number is already there => Do nothing.
No neighbors => make a single-node chain storing the number as first and last in its own position:
(N)->F = N
(N)->L = N
(N)->F = (N-1)->F
((N-1)->F)->L = N
(N)->L = (N+1)->L
((N+1)->L)->F = N
((N+1)->L)->F = (N-1)-F
Each time you update a chain you can easily compute the length. Keep track of the largest one storing in a couple variables its length and its first element and updating as required.
Can this be optimized further ? Where are the high rated coders