Java solution O(N)


  • 0
    H
         * Should be O(N).
         * Each element in the array is first inserted into the set.
         * Either the element is detected if exists or not, then get removed.
         * Or the element is detected, removed, detected again.
         * So every element will be detected at most twice.
         * */
        public int longestConsecutive(int[] nums)
        {
            Set<Integer> numSet = new HashSet<>();
            Arrays.stream(nums).forEach(numSet::add);
            int numLen = 0;
            for(int i = 0; i < nums.length; i++)
            {
                if(numSet.isEmpty()) break;
                int curNum = nums[i], curLen = 0;
                while (numSet.contains(curNum))
                {
                    numSet.remove(curNum);
                    curNum++;
                    curLen++;
                }
    
                curNum = nums[i] - 1;
                while (numSet.contains(curNum))
                {
                    numSet.remove(curNum);
                    curNum--;
                    curLen++;
                }
                numLen = Math.max(numLen, curLen);
            }
            return numLen;
        }
    

Log in to reply
 

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