128. Longest Consecutive Sequence

Problem Statement

Pattern:

---

Naive Solution

Freq Array / HashSet Approach

public int longestConsecutive1 (int[] nums){
	if(nums.length == 0) return 0;
	HashSet<Integer> set = new HashSet<>();
	int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
	for(int num: nums) {
		min = Math.min(min, num);
		max = Math.max(max, num);
		set.add(num);
	}
	int count = 0, maxCount = 1;
	for (int i = min; i <= max; i++) {
		if(set.contains(i)) count++;
		else count = 0;
		maxCount = Math.max(maxCount, count);
	}
	return maxCount;
}

solution will fail if the range of nums[i] > 10^8,

Notes

• Here we store an array into a set, and find the min and max of the array
• we start from min, and iterate to max, update count whenever set.contains is true for a consecutive set of integers.
• This is a very bad solution. better to sort array and find longest subsequnce as long as nums.length < 10^7

Optimised Solution

Set, but we keep all searching operations within the set.

public int longestConsecutive (int[] nums) {  
   Set<Integer> set = new HashSet<>();  
   for (int num : nums) set.add(num);  
   int maxLen = 0;  
   for(int num : set) {  
      if(!set.contains(num-1)) {  // start at the smallest no. of the subsequence  
         int next = num+1;  
         while(set.contains(next)) next++;   // find the end of the subsequence  
         maxLen = Math.max(maxLen, next-num);    // update max  
      }  
   }   return maxLen;  
}

Notes

• store all the elements into a set.
• iterate over set elements
  • find the start of a consecutive sequence !set.contains(num-1)
    • find the length of the sequence, and update max.