One Java solution


  • 18
    R
    public int longestConsecutive(int[] num) {
        Set<Integer> set = new HashSet<Integer>(num.length);
        for (int n: num) {
        	set.add(n);
        }
        
        int maxLength = 0;
        for (int n: num) {
        	if (set.contains(n)) {
        		int length = 1;
            	int next = n - 1;
            	while (set.contains(next)) {
            		length++;
            		set.remove(next);
            		next--;
            	}
            	next = n+1;
            	while (set.contains(next)) {
            		length++;
            		set.remove(next);
            		next++;
            	}
            	
            	if (length > maxLength) {
            		maxLength = length;
            	}
        	}
        }
        
        return maxLength;
    }
    

    The basic idea is put all integers into a set. Iterate all the integers and for every integer try to find its consecutive numbers in the set and accumulate the length. The trick is remove the integer whenever it has been visited, which makes the process O(n) because every integer will only be visited once.


  • 0
    B

    Will this approach fail when num contains Integer.MAX_VALUE?


  • 0
    R

    Yes, didn't consider much about corner cases but only provided a general thought. It can be fixed by checking MAX_VALUE before ++ and MIN_VALUE before --, or simply use long instead of int.


  • 0
    G

    I did write a similar code. But, I got java.util.ConcurrentModificationException. Is it working for you ? Its happening because we remove the key from set while iterating on the key.


  • 0
    R

    When you're iterating a set or map, you can only remove items by the iterator.


  • 0
    S
    This post is deleted!

  • 0
    G

    Can we remove if (set.contains(n)) ? because n should be in the set


  • 0
    R

    @gilbert2 we can't remove if (set.contains(n)) because set keeps removing elements, so set.contains(n) could be false.


  • 0

    same idea. My python code.

    class Solution(object):
        def longestConsecutive(self, nums):
            num_set = set(nums)
            res = 0
            while num_set:
                num = num_set.pop()
                i = 0
                while num + i + 1 in num_set:
                    num_set.remove(num + i + 1)
                    i += 1
                j = 0
                while num - j - 1 in num_set:
                    num_set.remove(num - j - 1)
                    j += 1
                res = max(res, i+j+1)
            return res
    

Log in to reply
 

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