128. Longest Consecutive Sequence

#Better Solution


Runtime    15 ms
Beats      93.34%


Memory     57.4 MB
Beats      50.15%


class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length <=1)
          return nums.length;
        Arrays.sort(nums);
        int ans=1,res=1;
        for(int i=1;i<nums.length;i++){
          if(nums[i] == nums[i-1]+1){
            ans++;
            if(ans>res)
              res=ans;
          }else if(nums[i] == nums[i-1]){}
           else{
             ans=1;
           }
        }
        return res;
    }
}

#Optimal Solution


Runtime    24 ms
Beats      75.31%


Memory     56.6 MB
Beats      67.42%

class Solution {
    public int longestConsecutive(int[] a) {
        int n = a.length;
        if (n == 0)
            return 0;

        int longest = 1;
        Set<Integer> set = new HashSet<>();

        for (int i = 0; i < n; i++) {
            set.add(a[i]);
        }

        for (int it : set) {
            if (!set.contains(it - 1)) {
                int cnt = 1;
                int x = it;
                while (set.contains(x + 1)) {
                    x = x + 1;
                    cnt = cnt + 1;
                }
                longest = Math.max(longest, cnt);
            }
        }
        return longest;
    }
}