Back to Arrays & Hashing
Medium
Longest Consecutive Sequence
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.
Examples
Input:nums = [100,4,200,1,3,2]
Output:4
The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Input:nums = [0,3,7,2,5,8,4,6,0,1]
Output:9
The longest consecutive sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8].
Constraints
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
Approach
Sort the array first. Then iterate through the array, comparing the current element to the previous one. If it is exactly one greater, we increment our current streak. If it is equal, we skip it. If it is more than one greater, we reset our streak to 1.
Complexity Analysis
Time Complexity
O(n log n)
Space Complexity
O(1) or O(n)
This approach does not meet the O(n) time complexity constraint, but it is a solid fallback.
Solution.java
class Solution { public int longestConsecutive(int[] nums) { if (nums.length == 0) return 0; Arrays.sort(nums); int longestStreak = 1; int currentStreak = 1; for (int i = 1; i < nums.length; i++) { if (nums[i] != nums[i-1]) { if (nums[i] == nums[i-1] + 1) { currentStreak += 1; } else { longestStreak = Math.max(longestStreak, currentStreak); currentStreak = 1; } } } return Math.max(longestStreak, currentStreak); }}