128. Longest Consecutive Sequence

📝 Problem Details

• Title: 128. Longest Consecutive Sequence
• Link: https://leetcode.com/problems/longest-consecutive-sequence/
• Difficulty: Medium
• Tags/Categories: Hashmap Arrays

💭What Were My Initial Thoughts?

- brute force / naive approach:
	- sort the array to find the longest consecutive sequence
	- there doesnt fit the constraint of needing an O(n) time solution

- using a hashset allows us to check if an element exists in O(1) time 
- we only need to start counting sequences from numbers that **do not have a smaller consecutive number**, ensuring that each sequence is counted only once.

💡 Explanation of Solution

1. inert all numbers into an unordered set
	- allows O(1) lookup to check if a number exists

2. iterate through the numbers in the array
	- if a number x has x-1 in the set, it means x is not the start of the sequence so we can skip it
	- if number x does not have x-1, it is the start of a new sequence
	- count how long this sequence extends by checking x+1, x+2, ... in the set

3. track the longest sequence found
	- store the maximum length found during this process

⌛ Complexity Analysis

Time Complexity: O(n)  
Space Complexity: O(n)  

💻 Implementation of Solution

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> set(nums.begin(), nums.end());
 
        int longest = 0;
 
        for(int i=0; i < nums.size(); i++) {
            if(!set.count(nums[i]-1)) {
                int length = 1;
 
                while(set.count(nums[i] + length)) { 
                    length++;
                }
 
                longest = max(longest, length);
            }
        }
 
        return longest;
 
    }
};