Longest Consecutive SubArray

Given an array of unsorted integers, find the length of the longest sub-sequence (or subarray) such that elements in the subsequence are consecutive integers, the consecutive numbers can be in any order.

Examples:

Input: arr[] = {1, 9, 3, 10, 4, 20, 2}
Output: 4
 The subsequence 1, 3, 4, 2 is the longest subsequence of consecutive elements

Input: arr[] = {36, 41, 56, 35, 44, 33, 34, 92, 43, 32, 42}
Output: 5
The subsequence 36, 35, 33, 34, 32 is the longest subsequence
of consecutive elements.

Ans:

Simple Solution is to first sort the array and find the longest subarray with consecutive elements. Time complexity of this solution is O(nLogn). 

Linear Time O(n) Solution:

The idea is to use Hashing. We first insert all elements to a HashSet. Then check all the possible starts of consecutive subsequences. Below is the algorithm.

• Create an empty HashSet.
• Insert all array elements to HashSet.
• Do following for every element arr[i]
• Check if this element is the starting point of a subsequence. To check this, we simply look for arr[i] – 1 in the hashset, if not found, then this is the first element in a subsequence.
• If this element is the first element, then count number of elements in the consecutive starting with this element. Iterate from arr[i] + 1 till the last element that can be found.
• If the count is more than the previous longest subsequence found, then update this.

// Returns length of the longest consecutive subsequence

    Public static int findLongestConseqSubseq(int arr[],int n)

    {

        HashSet<Integer> S = new HashSet<Integer>();

        int longest = 0;

  

        // Hash all the array elements

        for (int i=0; i<n; ++i)

            S.add(arr[i]);

  

        // check each possible sequence from the start

        // then update optimal length

        for (int i=0; i<n; ++i)

        {

            // if current element is the starting

            // element of a sequence

            if (!S.contains(arr[i]-1))

            {

                // Then check for next elements in the

                // sequence

                int j = arr[i];

                while (S.contains(j))

                    j++;

  

                // update  optimal length if this length

                // is more

                if (longest <j-arr[i])

                    longest = j-arr[i];

            }

        }

        return longest;

    }