Longest Consecutive Subsequence

Problem Statement: Longest Consecutive Subsequence

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.

Example: arr[] = [1, 9, 3, 10, 4, 20, 2]

Output: 4

Explanation: The subsequence 1, 3, 4, 2 is the longest subsequence of consecutive elements

Approach 1: Brute Force

For each element in array, linearly search for consecutive elements greater and lesser than the current element. Keep a track of the current streak and the longest streak of consecutive elements in the array. Time Complexity: O(n³): The inner loops linearly search for consecutive elements. This search will be done as long as the streak will be and the longest a streak can be is n.

Since it is not the optimal one we need to think of the optimised version of it.

Crack your next tech interview with confidence!

Approach 2: Hashing

We can improve the time complexity of searching consecutive elements by using a hash table which can check the presence of consecutive elements in O(1) average. Consider each element to be a part of some sequence, and try to find the maximum length sequence you can generate which includes this number.

Algorithm:

1. Copy all the element in set first.

2. Count the previous consecutive element from this element and similar next consecutive elememts from this element

3. So maximum seqence from this element would be "prevCount + nextCount + 1".

4. Maximun of this sequence is result.

Trick: Trick is to keep deleting the numbers you visited once, If you dont do so, you will again try to find the sequence from a number , which is already part of some sequence. Complexity of program will change to O(n2) if you dont delete the elements.

#include<bits/stdc++.h>

using namespace std;
int longestConsecutive(vector < int > & nums) {
  set < int > hashSet;
  for (int num: nums) {
    hashSet.insert(num);
  }

  int longestStreak = 0;

  for (int num: nums) {
    if (!hashSet.count(num - 1)) {
      int currentNum = num;
      int currentStreak = 1;

      while (hashSet.count(currentNum + 1)) {
        currentNum += 1;
        currentStreak += 1;
      }

      longestStreak = max(longestStreak, currentStreak);
    }
  }

  return longestStreak;
}
int main() {
  vector<int> arr{100,200,1,2,3,4};
  int lon = longestConsecutive(arr);
  cout << "The longest consecutive sequence is " << lon << endl;

}

class Solution:
    def longest_consecutive(self, nums):
        if not nums:
            return 0
        
        num_set = set(nums)
        longest = 0
        for n in nums:
            if n-1 not in num_set:
                length = 0
                while n in num_set:
                    length += 1
                    n += 1
                longest = max(longest, length)
        return longest
ob1 = Solution()
print(ob1.longest_consecutive([1, 9, 3, 10, 4, 20, 2]))

Time Complexity: O(n)

Auxiliary Space: O(n), Since we are using hashmap for storing

💡 Follow up: Try to solve it using sorting