Problem overview
The method longestConsecutive receives an unsorted array of integers, nums, and returns the length of the longest run of consecutive integers that can be found among its values. The run does not have to appear in order or in adjacent positions in the array. Duplicates count once.
For [100, 4, 200, 1, 3, 2] the values 1, 2, 3, 4 form a run of length 4, so the answer is 4. For [0, 2, 0, 1, 2, 3, 1] the run 0, 1, 2, 3 also has length 4, even though 0, 1 and 2 each appear twice.
Approach: only start counting at the beginning of a run
The statement asks for O(n) time and O(n) extra space. Sorting the array and scanning it would be simple, but sorting costs O(n log n).
A hash set gives constant-time answers to "is this number present?". With it, you can extend a run directly: from a value v, check v + 1, then v + 2, and so on, until a number is missing.
Doing that from every value would be slow, because a run of length L would be walked L times, once from each of its members. The fix is a single question per value: is value - 1 in the set? If it is, this value is in the middle of a run, and that run will be measured when the loop reaches its real start. Only a value with no predecessor starts a walk.
Every number then belongs to exactly one run, and is walked once from that run's start. The total work is proportional to the number of distinct values.
On the first example, the set is {100, 4, 200, 1, 3, 2}. Only 100, 200 and 1 have no predecessor. The walks give lengths 1, 1 and 4, and the best is 4. The values 4, 3 and 2 are skipped because each has its predecessor in the set.
Step by step
- Start the result at 0. That is also the correct answer for an empty array.
- Build the set.
valuesis aSet<number>created fromnums. The constructor keeps each value once and takesO(n)time. - Loop over the set, not over
nums. Duplicates are already gone, so none is processed twice. - Find the starts of runs. The condition is
!values.has(value - 1). - Begin counting at 1. The run already contains
valueitself. - Walk forward. While
values.has(value + sequenceLength)is true, the next number exists, so incrementsequenceLength. The loop stops at the first missing number. - Keep the best. Set
resultto the larger of itself andsequenceLength. - Return
resultonce the loop is over.
The solution in TypeScript
class Solution {
longestConsecutive(nums: number[]): number {
let result = 0;
let values = new Set<number>(nums);
for (let value of values) {
if (!values.has(value - 1)) {
let sequenceLength = 1;
while (values.has(value + sequenceLength)) {
sequenceLength++;
}
result = Math.max(result, sequenceLength);
}
}
return result;
}
}- The type argument.
Set<number>(nums)builds a set from an array. The argument is checked by the compiler and erased afterwards. for...ofworks on sets directly. It yields the values, in insertion order. The set is not modified inside the loop, so there is nothing to worry about while iterating.- Arithmetic on numbers.
value - 1andvalue + sequenceLengthare ordinary number arithmetic. Negative values need no special handling, and-2, -1, 0is a run of length 3. - Precision. Integers are exact up to
Number.MAX_SAFE_INTEGER, which is 9007199254740991. Beyond that,value + 1can equalvalueand the walk would not end. Inputs for this lesson are far below that limit.
The sorting alternative
For comparison, here is the sorting version, which needs O(n log n) time:
function lcsSort(nums: number[]): number {
if (nums.length === 0) return 0;
const sorted = [...new Set(nums)].sort((a, b) => a - b);
let best = 1, run = 1;
for (let i = 1; i < sorted.length; i++) {
run = sorted[i] === sorted[i - 1] + 1 ? run + 1 : 1;
best = Math.max(best, run);
}
return best;
}It also returns 4 for both examples and 0 for an empty array. It removes duplicates with a set first, so equal neighbours cannot break a run. The set-only solution above avoids the sort entirely, and that is what brings the time down to O(n).
Complexity
Time: O(n). Building the set is O(n). The outer loop visits each distinct value once. The inner while runs only from run starts, and it takes one step for each member of that run, so across the whole loop it takes at most one step per distinct value. All set operations are constant time on average.
Space: O(n). The set holds up to n values.
Edge cases and common mistakes
- Empty array. The loop never runs and the answer is
0. - One distinct value.
[5, 5, 5]gives1. - Duplicates. Looping over the set means a repeated value never inflates a run.
- Skipping the predecessor test. The answer is still right, but on an input like
1, 2, ..., nevery value would start a walk and the time would grow toO(n²). - Starting the length at 0. The run would be one short.
- Sorting with
sort()and no comparator. If you ever solve this by sorting, remember that the default order is by string.[10, 9, 1].sort()gives[1, 10, 9]. Use(a, b) => a - b.
Testing
[100, 4, 200, 1, 3, 2]gives4.[0, 2, 0, 1, 2, 3, 1]gives4.[]gives0.[5, 5, 5]gives1.[-2, -1, 0]gives3.