Longest Consecutive Sequence in an Array
The problem
Given an array nums of n integers.
Return the length of the longest sequence of consecutive integers. The integers in this sequence can appear in any order.
Input: nums = [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The longest sequence of consecutive elements in the array is [1, 2, 3, 4], which has a length of 4. This sequence can be formed regardless of the initial order of the elements in the array.
Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1] Output: 9 Explanation: The longest sequence of consecutive elements in the array is [0, 1, 2, 3, 4, 5, 6, 7, 8], which has a length of 9.
Input: nums = [1, 9, 3, 10, 4, 20, 2]
-
1 <= nums.length <= 105 - ** **-109 <= nums[i] <= 109
cpp
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
}
};java
class Solution {
public int longestConsecutive(int[] nums) {
}
}python
class Solution:
def longestConsecutive(self, nums):javascript
class Solution {
longestConsecutive(nums){
}
}csharp
public class Solution
{
public int LongestConsecutive(int[] nums)
{
}
}go
func longestConsecutive(nums []int) int {
//your code goes here
}Stuck? Show a way to structure it+
- 01Insert numbers into a set
- 02For each value, test whether value-1 is absent
- 03Extend forward to count that run
- 04Keep the maximum length
Reference answer
Then expect these follow-ups
How would you return the sequence itself?
Tests: implementation extension
What assumptions underlie expected O(1) hashing?
Tests: follow-up reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question