Longest Consecutive Sequence

https://leetcode.com/problems/longest-consecutive-sequence/description/

Intuition

Top of the morning lads,
The question asks us to find the length of the longest consecutive integer sequence with a caveat to do this within O(n) time complexity.

The caveat eliminates sorting as an option, which leaves us with either using hashing or two pointer (or some top shelf logic which I would never comprehend in my small mind). Two pointer doesn’t help much in this question (probably can, but I was clueless how to use two pointer here), so hashing is logically the way to go forward.

Now, to the CORE OF THE INTUITION:
If we could store all of the elements in someplace where we can find the next and previous number for the element without needing to iterate over the array again and again that would solve our problem.

Problems:

1. Store the numbers (while treating duplicate values in same way)
2. Find if next and previous numbers for a given number is in the given array.
3. Return the highest count

A HashSet allows to store all the elements while taking care of duplicates. Searching in HashSet takes O(1) which allows to search if the array contains the next and previous values without needing to traverse the entire array. Using HashSet seems more logical than using HashMap as we are not storing any value corresponding to the key.

Approach

Now for the approach:

1. Store all the numbers in HashSet.
2. FOR number (say prefix) in HashSet:
        IF (prefix is the first in the sequence and no other number in array is smaller than prefix):
            WHILE(HashSet includes NEXT Number (say suffix)):
                Increase suffix by 1
            set the COUNT to 
                MAX(count, last num in seq (stored in suffix) - first num in seq (stored in prefix))
3. Return COUNT

Complexity

• Time complexity:

Time to add numbers in HashSet : O(N)
Time to check for prefix : O(1)
Time to check for suffix : O(1)
Number of time check for prefix and suffix : Once for every sequence

Overall Time Complexity : O(N)

• Space complexity:

Extra Space needed for HashSet : O(N)

Code

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for(int number : nums){
            set.add(number);
        }

        int count = 0;
                for(int prefix : set){
                    if(!set.contains(prefix-1)){
                        int suffix = prefix + 1;
                        while(set.contains(suffix)){
                            suffix = suffix + 1;
                        }
                        count = Math.max(count, suffix-prefix);
                    }         
                }
                return count;
            }
        }

P.S. If you found this useful, please share your support with comments and claps. If you feel this can be useful to someone you know, please feel free to share this publication and story. Join my journey on DSA on my github where I am journaling all the questions I have solved and commented on: StrugglingCOderDSA.

Cheers,
Your Struggling COder;