# 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) {
}
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;
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]