Java Programming – Longest Consecutive Subsequence

Given an array of integers, find the length of the longest sub-sequence 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.

One Solution is to first sort the array and find the longest subarray with consecutive elements. Time complexity of this solution is O(nLogn). Thanks to Hao.W for suggesting this solution here.

We can solve this problem in O(n) time using an Efficient Solution. The idea is to use Hashing. We first insert all elements in a Hash. Then check all the possible starts of consecutive subsequences. Below is complete algorithm.

1) Create an empty hash.
2) Insert all array elements to hash.
3) Do following for every element arr[i]
....a) Check if this element is the starting point of a 
       subsequence.  To check this, we simply look for
       arr[i] - 1 in hash, if not found, then this is
       the first element a subsequence.  
    
       If this element is a first element, then count 
       number of elements in the consecutive starting 
       with this element.

       If count is more than current res, then update    
       res.

[pastacode lang=”java” manual=”%2F%2F%20Java%20program%20to%20find%20longest%20consecutive%20subsequence%0Aimport%20java.io.*%3B%0Aimport%20java.util.*%3B%0A%20%0Aclass%20ArrayElements%0A%7B%0A%20%20%20%20%2F%2F%20Returns%20length%20of%20the%20longest%20consecutive%20subsequence%0A%20%20%20%20static%20int%20findLongestConseqSubseq(int%20arr%5B%5D%2Cint%20n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20HashSet%3CInteger%3E%20S%20%3D%20new%20HashSet%3CInteger%3E()%3B%0A%20%20%20%20%20%20%20%20int%20ans%20%3D%200%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Hash%20all%20the%20array%20elements%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20%20%20%20S.add(arr%5Bi%5D)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20check%20each%20possible%20sequence%20from%20the%20start%0A%20%20%20%20%20%20%20%20%2F%2F%20then%20update%20optimal%20length%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20if%20current%20element%20is%20the%20starting%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20element%20of%20a%20sequence%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(!S.contains(arr%5Bi%5D-1))%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Then%20check%20for%20next%20elements%20in%20the%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20sequence%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20j%20%3D%20arr%5Bi%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while%20(S.contains(j))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20j%2B%2B%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20update%20%20optimal%20length%20if%20this%20length%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20is%20more%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(ans%3Cj-arr%5Bi%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ans%20%3D%20j-arr%5Bi%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%20ans%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Testing%20program%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20arr%5B%5D%20%3D%20%20%7B1%2C%209%2C%203%2C%2010%2C%204%2C%2020%2C%202%7D%3B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20arr.length%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22Length%20of%20the%20Longest%20consecutive%20subsequence%20is%20%22%20%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20findLongestConseqSubseq(arr%2Cn))%3B%0A%20%20%20%20%7D%0A%7D” message=”Java Program” highlight=”” provider=”manual”/]

Output:

Length of the Longest contiguous subsequence is 4

Time Complexity: At first look, time complexity looks more than O(n). If we take a closer look, we can notice that it is O(n) under the assumption that hash insert and search take O(1) time. The function S.find() inside the while loop is called at most twice for every element. For example, consider the case when all array elements are consecutive. In this case, the outer find is called for every element, but we go inside the if condition only for the smallest element. Once we are inside the if condition, we call find() one more time for every other element.