Skip to content

Longest Consecutive Sequence

11/21/2013

Longest Consecutive Sequence
Total Accepted: 2702 Total Submissions: 10637

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

	public static int longestConsecutive(int[] num) {
	     if(num.length == 1 || num.length == 0){
	    	 return num.length; 
	     }
    	 HashMap<Integer, Integer> h = new HashMap<Integer, Integer>();
    	 
    	 for(int i=0; i<num.length; i++){
    		 h.put(num[i],1);
    	 }
    	 int res = Integer.MIN_VALUE;
    	 
    	 int j = 0;
    	 while( j<num.length ){
    		 int max = 0;
    		 int m = num[j];
    		 int n = num[j]+1;
    		 
    		 while(h.keySet().contains(m)){
    			 h.remove(m);
    		 
    			 m--;
    			 max ++;
    		 }
    		 
    		 while(h.keySet().contains(n)){
    			 h.remove(n);
    	 
    			 n++;
    			 max ++;
    		 }
    		 
    		 if(max > res){
    			 res = max;
    		 }
    		 j++;
    	 }
    	 return res;
	  }


Advertisements
Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: