Fastest solution in python 60ms O(n) complexity


  • 0
    X

    Using two sets, one for the original list of numbers and the other for recording those visited numbers. For each n in num check if its neighboring numbers are in the list, and add those in the list to the visited set

    class Solution:
        # @param num, a list of integer
        # @return an integer
        def longestConsecutive(self, num):
            numlen, longest = len(num), 0
            numset, visited = set(num), set()
            for n in numset:
                if n in visited: continue
                visited.add(n)
                m, length = n + 1, 1
                while m in numset:
                    visited.add(m)
                    length, m = length + 1, m + 1
                m = n - 1
                while m in numset:
                    visited.add(m)
                    length, m = length + 1, m - 1
                longest = max(length, longest)
            return longest

  • 0
    D

    The same idea in java code

    public class Solution {
        public int longestConsecutive(int[] num) {
            
            HashSet<Integer> set = new HashSet<Integer>();
            for(int e: num){
                set.add(e);
            }
            int max = 0;
            for(int i:num){
                int count = 1;
                int left = i-1;
                int right = i+1;
                while(set.contains(left)){
                    count++;
                    set.remove(left);
                    left--;
                }
                while(set.contains(right)){
                    count++;
                    set.remove(right);
                    right++;
                }
                if(count > max) max = count;
            }
            return max;
       }
    }

Log in to reply
 

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