23. Longest consecutive subsequence

23. Longest consecutive subsequence

Problem link :- click here

package programs;

import java.util.*;

public class Array__23
{

	static int longestConsecutiveSubsequence(int arr[], int n)
	{
		HashSet<Integer> hash_set = new HashSet<>();
		
		//adding all the elements of the array to the hash_set
		for(int i=0; i<n; i++)
			hash_set.add(arr[i]);

		int max = 0;          //our result
		
		//iterating through the array
		for(int i=0; i<n; i++)
		{
			//hash_set.contains(arr[i]-1)   -> 
			//                    means arr[i] is not the starting point
			//hence we are going to the starting point 
			//                    by using not(!) in the same condition
			if(!hash_set.contains(arr[i]-1))
			{
				//taking first element in 'j'
				int j = arr[i];
				
				//we are checking if next consecutive element is present in  the array
				//starting from arr[i]
				while( hash_set.contains(j) )
					j++;
				
				//'while' loop will break only when 'j' is not present in the array
				//which in-turn means the array contains all the elements 
				//from    arr[i]    to     j-1
				//so the number of elements in consecutive is ( j-arr[i] )
				
				max = Math.max(max, j-arr[i]);
			}
		}
		return max;
	}
	
	public static void main(String[] args)
	{
		int n, i, ans;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the size of the array :");
		n = s.nextInt();
		int array[] = new int[n];
		System.out.println("Enter the elements of the array :");
		for(i=0; i<n; i++)
			array[i] = s.nextInt();
		
		System.out.println("Given Array : ");
		print_array(array);
		
		ans = longestConsecutiveSubsequence(array, n);
		System.out.println("\n\nLongest Consecutive Subsequence : " + ans);
	}

	static void print_array(int arr[])
	{
		for(int i=0; i<arr.length; i++)
			System.out.print(arr[i] + " ");
	}
}

Time complexity :- O(n)
Space complexity :- O(1)