Longest Consecutive Sequence — Problem Statement & Solution Guide
Problem Description
Given an unsorted array of integers, find the length of the longest consecutive sequence.
Examples
Input
[0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output
9
Explanation: Step-by-step: with input [0, 3, 7, 2, 5, 8, 4, 6, 0, 1], we first remove duplicates by converting the array to a set. Then we find the minimum number in the set. We iterate over the set starting from the minimum number and check if the current number plus one is in the set. If it is, we increment the sequence length. We keep doing this until we find a number that is not in the set or we have checked all numbers in the set. The length of the longest sequence is the maximum sequence length found.
Input
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Output
10
Explanation: Step-by-step: with input [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], we first remove duplicates by converting the array to a set. Then we find the minimum number in the set. We iterate over the set starting from the minimum number and check if the current number plus one is in the set. If it is, we increment the sequence length. We keep doing this until we find a number that is not in the set or we have checked all numbers in the set. The length of the longest sequence is the maximum sequence length found.
Constraints
- 0 <= n <= 10^5
- -10^9 <= arr[i] <= 10^9
Optimal Approach & Strategy
Use HashSet. For each element, check if it's the start of a sequence (if num-1 is not in set). If it is, count upwards in the set. Time O(N), Space O(N).
Brute Force Approach
Sort the array and count consecutive elements. Time O(N log N).
Verified Code Solutions
function longestConsecutive(nums) { let numSet = new Set(nums); let longestStreak = 0; for (let num of numSet) { if (!numSet.has(num - 1)) { let currentNum = num; let currentStreak = 1; while (numSet.has(currentNum + 1)) { currentNum += 1; currentStreak += 1; } longestStreak = Math.max(longestStreak, currentStreak); } } return longestStreak; }class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) {
return 0;
}
Set<Integer> numSet = new HashSet<>();
for (int num : nums) {
numSet.add(num);
}
int maxLength = 0;
for (int num : numSet) {
if (!numSet.contains(num - 1)) {
int currentNum = num;
int currentLength = 1;
while (numSet.contains(currentNum + 1)) {
currentNum += 1;
currentLength += 1;
}
maxLength = Math.max(maxLength, currentLength);
}
}
return maxLength;
}
}def longestConsecutive(self, nums: list[int]) -> int:
if not nums:
return 0
num_set = set(nums)
max_length = 0
for num in num_set:
if num - 1 not in num_set:
current_num = num
current_length = 1
while current_num + 1 in num_set:
current_num += 1
current_length += 1
max_length = max(max_length, current_length)
return max_lengthfunction longestConsecutive(nums) { let numSet = new Set(nums); let longestStreak = 0; for (let num of numSet) { if (!numSet.has(num - 1)) { let currentNum = num; let currentStreak = 1; while (numSet.has(currentNum + 1)) { currentNum += 1; currentStreak += 1; } longestStreak = Math.max(longestStreak, currentStreak); } } return longestStreak; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.