Solution For Longest Consecutive Sequence

The Longest Consecutive Sequence problem on LeetCode can be solved using the concept of hashing. The problem statement is as follows.

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,

Input: [100, 4, 200, 1, 3, 2] Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

To solve this problem, we can follow the below steps.

1. Create a hash set and add all the elements of the input array to the set.

2. Initialize a variable maxLength to store the length of the longest consecutive sequence found so far.

3. Iterate through the input array and for each element i, we will check if i – 1 is present in the hash set. If it is present, then it means that i is not the start of a sequence, so we can skip this iteration and move on to the next element.

4. If i – 1 is not present in the hash set, then it means that i is the start of a sequence. So we will iterate through the hash set and find the length of the consecutive sequence starting from i. We will update maxLength if the length of this sequence is greater than maxLength.

5. After iterating through all the elements in the input array, we will return maxLength.

The Python code for the solution is as follows.

“`
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
numSet = set(nums)
maxLength = 0

    for num in nums:
        if num - 1 not in numSet:
            currLength = 1
            while num + 1 in numSet:
                currLength += 1
                num += 1
            maxLength = max(maxLength, currLength)

    return maxLength

“`

Time Complexity: O(n), where n is the length of the input array.

Space Complexity: O(n), where n is the length of the input array, since we are using a hash set to store all the elements of the input array.

Step by Step Implementation For Longest Consecutive Sequence

class Solution {
    public int longestConsecutive(int[] nums) {
        Set set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int longestStreak = 0;
        for (int num : set) {
            if (!set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                while (set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        return longestStreak;
    }
}

def longestConsecutive(nums): 
    
    # check for empty list 
    if len(nums)==0: 
        return 0

    # sort the list 
    nums.sort() 

    # initialize variables 
    max_count = 1
    count = 1

    # traverse the list 
    for i in range(1,len(nums)): 

        # if current number is equal to previous number, 
        # increment the count 
        if nums[i]==nums[i-1]: 
            count += 1

        # if not equal, then update the max_count 
        # if count is greater than max_count 
        else: 
            if count > max_count: 
                max_count = count 
            count = 1

    # return the max_count 
    return max_count

var longestConsecutive = function(nums) {
    // we need to sort the array first
    nums.sort((a, b) => a - b);
    
    // we will keep track of the longest sequence and the current sequence
    let longest = 0,
        current = 0;
    
    // iterate through the array
    for (let i = 0; i < nums.length; i++) {
        // if the current number is one more than the previous number,
        // that means the current sequence is still going
        if (nums[i] === nums[i - 1] + 1) {
            current++;
        } else if (nums[i] === nums[i - 1]) { // if the current number is the same as the previous number, do nothing
            continue;
        } else { // otherwise, the current sequence has ended
            longest = Math.max(longest, current); // update the longest sequence if necessary
            current = 1; // reset the current sequence
        }
    }
    
    // return the longest sequence
    return Math.max(longest, current);
};

class Solution {
public:
    int longestConsecutive(vector& nums) {
        // edge case
        if (nums.size() == 0) {
            return 0;
        }
        
        // sort the array
        sort(nums.begin(), nums.end());
        
        // keep track of the longest sequence
        int longest = 1;
        int current = 1;
        
        // iterate through the array
        for (int i = 1; i < nums.size(); i++) {
            // if the current number is equal to the previous number + 1
            if (nums[i] == nums[i-1] + 1) {
                // increment the current counter
                current++;
            } 
            // if the current number is not equal to the previous number + 1
            else {
                // check if the current counter is greater than the longest counter
                if (current > longest) {
                    // if so, set the longest counter equal to the current counter
                    longest = current;
                }
                // reset the current counter
                current = 1;
            }
        }
        // check if the current counter is greater than the longest counter
        if (current > longest) {
            // if so, set the longest counter equal to the current counter
            longest = current;
        }
        
        // return the longest counter
        return longest;
    }
};

public int LongestConsecutive(int[] nums) {

// if the array is empty, return 0
if (nums.Length == 0) {
    return 0;
}

// sort the array
Array.Sort(nums);

// keep track of the longest streak
int longestStreak = 1;

// for each number in the array
for (int i = 1; i < nums.Length; i++) {
    // if the number is part of a streak
    if (nums[i] == nums[i-1]+1) {
        // increment the streak length
        longestStreak++;
    }
    // if the number is not part of a streak
    else {
        // reset the streak length
        longestStreak = 1;
    }
}

// return the longest streak
return longestStreak;
}