Longest Consecutive Sequence
Medium About 20 min Free, no account needed
Find the length of the longest run of consecutive integers hiding in an unsorted array.
The brief
Given an unsorted array of integers nums, return the length of the longest
sequence of consecutive integers present in it. The elements may appear in any
order; duplicates count once.
[100, 4, 200, 1, 3, 2]contains1, 2, 3, 4, the answer is4.- An empty array has answer
0.
The obvious approach extends a run from every element and answers "is v + 1 present?"
by scanning the whole array each time. On the hidden test, 200,000 consecutive
values, that nested scanning is far too slow. You will need each value to be visited
only a constant number of times, O(n) overall.
Starter code
using System;
public class Solution
{
// TODO: return the length of the longest run of consecutive integers present in nums.
public int LongestConsecutive(int[] nums)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Hash maps and sets
- Trade memory for constant-time lookups, membership tests and frequency counts.
Related katas
- Contiguous Array Medium Free Longest subarray holding as many zeros as ones.
- Degree of an Array Medium Free Find the shortest contiguous slice whose most-frequent-element count matches the whole array.
- Find All Anagram Start Indices Medium Free Every position where an anagram of the pattern begins.
- Count Quadruples Summing to Target Medium Free Count index quadruples that sum to a target - without the quadruple loop.