In this guide, you will get 128. Longest Consecutive Sequence LeetCode Solution with the best time and space complexity. The solution to Longest Consecutive Sequence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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
Constraints:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
128. Longest Consecutive Sequence LeetCode Solution in C++
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int ans = 0;
unordered_set<int> seen{nums.begin(), nums.end()};
for (int num : nums) {
// `num` is the start of a sequence.
if (seen.contains(num - 1))
continue;
int length = 1;
while (seen.contains(++num))
++length;
ans = max(ans, length);
}
return ans;
}
}; /* code provided by PROGIEZ */
128. Longest Consecutive Sequence LeetCode Solution in Java
class Solution {
public int longestConsecutive(int[] nums) {
int ans = 0;
Set<Integer> seen = Arrays.stream(nums).boxed().collect(Collectors.toSet());
for (int num : nums) {
// `num` is the start of a sequence.
if (seen.contains(num - 1))
continue;
int length = 1;
while (seen.contains(++num))
++length;
ans = Math.max(ans, length);
}
return ans;
}
} // code provided by PROGIEZ
128. Longest Consecutive Sequence LeetCode Solution in Python
class Solution:
def longestConsecutive(self, nums: list[int]) -> int:
ans = 0
seen = set(nums)
for num in nums:
# `num` is the start of a sequence.
if num - 1 in seen:
continue
length = 0
while num in seen:
num += 1
length += 1
ans = max(ans, length)
return ans # code by PROGIEZ
