Easy to understand JAVA solution using TreeSet


  • -1
    S

    TreeSet is already sorted....so it's fairly easy to just utilize this property.

    public class LongestConsecutiveSequence {
    public int longestConsecutive(int[] nums) {
    	if (nums.length == 0) return 0;
    	
    	Set<Integer> set = new TreeSet<Integer>();
    	
    	for (int i = 0; i < nums.length; ++i) {
    		set.add(nums[i]);
    	}
    	
    	int thisLength = 1, longest = 1;
    
    	Iterator<Integer> element = set.iterator();
    	int i = element.next();
    	
    	while (element.hasNext()) {
    		int j = element.next();
    		if (j == i + 1) {
    			++thisLength;
    			i = j;
    			continue;
    		}
    		if (thisLength > longest)
    			longest = thisLength;
    		thisLength = 1;
    		i = j;
    	}
    	
    	if (thisLength > longest) longest = thisLength;
    	return longest;
    	
    }
    

    }


  • 2
    M

    I think populating a TreeSet takes O(nlogn), which is as expensive as sorting the array.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.