Subsequence Problem

general
, ,
1

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 :slight_smile:

1 Like
2

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

  • Only the left neighbor is present => The number becomes the last element in the chain. Get the first element of the chain from the left neighbor and update the chain info:
    (N)->L = N

(N)->F = (N-1)->F

((N-1)->F)->L = N

  • Only right neighbor is present => Similar to previous
    (N)->F = N

(N)->L = (N+1)->L

((N+1)->L)->F = N

  • Both neighbors are present => Link two chains updating the first of the left and last element of the right:
    ((N-1)->F)->L = (N+1)->L

((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.

3

Can this be optimized further ? Where are the high rated coders :smiley: