Longest consecutive subsequence

Given an array of positive 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 1:

Input:
N = 7
a[] = {2,6,1,9,4,5,3}
Output:
6
Explanation:
The consecutive numbers here
are 1, 2, 3, 4, 5, 6. These 6 
numbers form the longest consecutive
subsquence.

Example 2:

Input:
N = 7
a[] = {1,9,3,10,4,20,2}
Output:
4
Explanation:
1, 2, 3, 4 is the longest
consecutive subsequence.

method 1 : sorting

1)sort the array.

2)now traverse through the array and check if a[i]=a[i-1]+1 ,if its true increment the counter (int c) and take a element (int mc in below code) to store the Longest consecutive subsequence found till now

3)in case if it does not follow the above condition than go to else and make counter again to 1

4)to handle duplicate elements we have used if else , if duplicate elements are present just go to the next element without changing anything

5) then return mc at the end.

c++ implementation:

int findLongestConseqSubseq(int a[], int n)
    {
      sort(a,a+n);
      
      int c=1;int mc=1;
      for(int i=1;i<n;i++)
      {
          if(a[i]==a[i-1]+1)
          {
              c++;
              if(c>mc)
              mc=c;
          }
          else if(a[i]==a[i-1])
          continue;
          else
          {
             c=1; 
          }
          
         
      }
      return mc;
    }

Time Complexity: O(nlogn) 

space Complexity: O(1) 

method 2 :hashing

1)take a set and insert all elements in it ,now the elements will be sorted and even duplicate elements will be removed

2)now traverse the set and put all elements in an array.

2)now traverse this above array  and check if a[i]=a[i-1]+1 ,if its true increment the counter (int c) and take a element (int mc in below code) to store the Longest consecutive subsequence found till now

3)in case if it does not follow the above condition than go to else and make counter again to 1

5) then return mc at the end.

c++ implementation:

int findLongestConseqSubseq(int a[], int n)
    {
      set<int>s(a,a+n);
      int z=0;
      for(auto x=s.begin();x!=s.end();x++)
      {
          a[z]=*x;
          z++;   
      }

      int c=1;int mc=1;
      for(int i=1;i<z;i++)
      {
          if(a[i]==a[i-1]+1)
          {
              c++;
              if(c>mc)
              mc=c;
          }
          else
          {
             c=1; 
          }
          
         
      }
      return mc;
    }

Time Complexity: O(n) 

space Complexity: O(n)