LeetCode Question - 128. Longest Consecutive Sequence ππ»
5th July 2022 | π Daily LeetCode Challenge - #5
About the Series
Problem-solving is a key skill set for any tech-related stuff you might be working on.
When it comes to developers it's one of the most crucial skills which is needed in almost any day-to-day code you might be writing.
So, this series of blogs is all about practicing Daily LeetCode Challenges & Problem-solving. π
Problem Statement
Given an unsorted array of integers
nums
, return the length of the longest consecutive elements sequence.You must write an algorithm that runs in
O(n)
time.
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Video Explanation
Solution
Algorithm
- we create a
numsMap
and store all the values in the map. - Now Iterate through the
nums
array and check if it is the starting point of a consecutive sequence of values or not. ie.num-1
exists or not. If it doesnβt exist that means it can be starting value of the sequence. - Now check whether the next consecutive value exists or not in a while loop and increment the value of the current sequence length.
- Compare the longest sequence length with the current sequence length whichever is maximum will be stored in longest sequence length
- Finally return the longest sequence length.
Code in JS π§βπ»
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function (nums) {
var numsMap = new Map();
for (const num of nums) {
numsMap.set(num);
}
var longestSequence = 0;
for (const num of nums) {
if (!numsMap.has(num - 1)) {
var currentSequence = 1;
var currentNum = num;
while (numsMap.has(currentNum + 1)) {
currentNum++;
currentSequence++;
}
longestSequence = Math.max(longestSequence, currentSequence);
}
}
return longestSequence;
};
Time Complexity : O(n)
Space Complexity: O(1)
Similar Questions for practice
Now it is time to try some similar questions
- Binary Tree Longest Consecutive Sequence
- Find Three Consecutive Integers That Sum to a Given Number
- Maximum Consecutive Floors Without Special Floors
You can find me on the web π
Add your solution or approach in the comments below. Also, show your love by Sharing the blog. π€
βBelieve you can and youβre halfway there.β
~ Theodore Roosevelt