Longest Consecutive Sequence

The problem

You are given an unsorted array nums of whole numbers (call its length n). Find the longest run of values that follow each other with no gap, like 4, 5, 6, 7. Return the length of that run.

The values can sit anywhere in the array, in any order. Only the values matter, not their positions. Aim for O(n) time.

Example 1

Input: nums = [8, 3, 10, 1, 9, 2, 7]

Output: 4

7, 8, 9 and 10 are all present, so that run has length 4. The run 1, 2, 3 has length 3.

nums

803110213942576

Example 2

Input: nums = [5, 5, 6]

Output: 2

The two 5s count as one value. The run is 5, 6.

Example 3

Input: nums = []

Output: 0

An empty array has no run at all.

Constraints

• 0 ≤ n ≤ 100,000
• −1,000,000,000 ≤ nums[i] ≤ 1,000,000,000

Clarifying questions

Do the values have to be next to each other in the array?

No. Only the values must be consecutive. Their positions do not matter.

How do repeated values count?

Once. [5, 5, 6] has a run of length 2, not 3.

Can the array be empty?

Yes. Then the answer is 0.

Can values be negative?

Yes. A run can cross zero, like −1, 0, 1.

Spot the pattern

The question for each value is “is the next value here?”. Searching the array for it is slow, but a hash set answers it in one step. The real trick is to avoid counting the same run many times: only start counting at a value whose previous value is missing, because that value is where a run begins.

Solutions

Sort and scanO(n log n)Hash setO(n)

Show all

This problem has two approaches worth showing. Counting up from every value without the start check is O(n²); the hash set approach explains why that one check fixes it.

Sort and scan O(n log n)

The idea

Sort the numbers. Then every run of consecutive values sits side by side, in order.

Walk the sorted array and keep the length of the current run. If a number is one more than the number before it, the run grows. If it is equal, skip it: a repeat neither grows nor breaks the run. Otherwise the run breaks, and a new run of length 1 starts. Keep the best length seen.

Walkthrough

nums

803110213942576

sorted

102132738495106

1. if not nums: return 0
2. nums.sort()
3. best = run = 1
4. for i in range(1, len(nums)):
5. if nums[i] == nums[i - 1]:
6. continue
7. if nums[i] == nums[i - 1] + 1:
8. run += 1
9. else:
10. run = 1
11. best = max(best, run)
12. return best

Sort the numbers. Then every run of consecutive values sits side by side.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Sort, then scan: after sorting, a run of consecutive values sits side by side.
    // The sort costs O(n log n) and dominates the O(n) scan.
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        Arrays.sort(nums);
        int best = 1, run = 1;
        for (int i = 1; i < nums.length; i++) {
            // A repeated value neither grows nor breaks the run.
            if (nums[i] == nums[i - 1]) continue;
            if (nums[i] == nums[i - 1] + 1) run++;
            else run = 1;
            best = Math.max(best, run);
        }
        return best;
    }
}

Big O

Time O(n log n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Two parts do the work. The sort on line 2 is one line, but it takes about n × log₂ n steps. The scan loop then does a few comparisons per run, which is 1 step each.

   1. if not nums: return 0
   2. nums.sort()
   3. best = run = 1
   4. for i in range(1, len(nums)):
   5. if nums[i] == nums[i - 1]:
   6. continue
   7. if nums[i] == nums[i - 1] + 1:
   8. run += 1
   9. else:
   10. run = 1
   11. best = max(best, run)
   12. return best

2. 2 Count the runs on Example 1

   Example 1 has 7 numbers. The sort takes about 7 × log₂ 7 ≈ 7 × 2.8 ≈ 20 steps. The scan runs 6 times, for i from 1 to 6.

   part	sort	scan
   steps on Example 1	about 7 × log₂ 7 ≈ 20	6

3. 3 Write the count for any n

   n log n + (n − 1)

   Check it with Example 1: about 20 + 6 = 26 steps.

4. 4 Keep only the part that grows fastest

   • Drop the n − 1. n log n always ends up bigger than n, so the sort is the biggest part.

   What is left is n log n. That misses the O(n) goal, so we need a way to skip the sort.

   So the time is O(n log n).

5. S Space: count the extra memory the same way

   The scan keeps only best, run and i, so the code itself needs O(1) extra memory. The sort may use some memory of its own inside your language, from log n up to n.

   bestruni

Hash set O(n)

The idea

Put every number in a hash set. A hash set is a collection that answers “is this value inside?” in one step on average.

Now go through the values. For each value number, first ask: is number − 1 in the set? If yes, number sits in the middle of a run, and that run will be counted from its own start. Skip it. If no, number is the start of a run. Count up: number + 1, number + 2, and so on, until a value is missing.

That one check is what makes it fast. Without it, a run of length 1,000 would be counted again from every one of its 1,000 values.

Why it never misses the answer: every run has exactly one start, the value whose previous value is missing. The loop reaches that start and counts the whole run from it.

Walkthrough

nums

803110213942576

number line

123···78910·

best

0

1. values = set(nums)
2. best = 0
3. for number in values:
4. if number - 1 in values:
5. continue
6. length = 1
7. while number + length in values:
8. length += 1
9. best = max(best, length)
10. return best

Put every number in a hash set. Now "is v here?" takes one step for any v. A set can hand back its values in any order; here we take them in input order.

← BackStep →Play1 / 16

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Hash set, counting up only from the start of each run.
    // Each number is checked once in the outer loop and once inside its run: O(n) time, O(n) memory.
    public int longestConsecutive(int[] nums) {
        Set<Integer> values = new HashSet<>();
        for (int number : nums) values.add(number);
        int best = 0;
        for (int number : values) {
            // If number - 1 exists, number is in the middle of a run. Its start will count it.
            if (values.contains(number - 1)) continue;
            int length = 1;
            while (values.contains(number + length)) length++;
            best = Math.max(best, length);
        }
        return best;
    }
}

Big O

Time O(n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The work is set lookups, each 1 step on average. The outer loop does one lookup per value. The inner while loop does one lookup per step up a run. It looks like a loop inside a loop, so the question is how often the inner loop really runs.

   1. values = set(nums)
   2. best = 0
   3. for number in values:
   4. if number - 1 in values:
   5. continue
   6. length = 1
   7. while number + length in values:
   8. length += 1
   9. best = max(best, length)
   10. return best

2. 2 Count the runs on Example 1

   Example 1 has 7 values. The outer loop runs 7 times. Only 1 and 7 start a run. From 1 the while loop steps up 2 times (to 2 and 3). From 7 it steps up 3 times (to 8, 9 and 10).

   7 + 2 + 3 = 12 runs, plus one last failed check per start.

   	x = 8	x = 3	x = 10	x = 1	x = 9	x = 2	x = 7
   role	skip	skip	skip	start	skip	skip	start
   while runs	0	0	0	2	0	0	3

   total

   7 outer runs + 5 while runs = 12

3. 3 Write the count for any n

   The while loop only runs from the start of a run, and it steps once onto each other value of that run. Every value belongs to exactly one run, so across the whole loop it steps onto each value at most once:

   n (outer) + at most n (while steps) + at most n (failed checks) ≤ 3n

   Check it with Example 1: 7 + 5 + 2 = 14, below 3 × 7 = 21.

4. 4 Keep only the part that grows fastest

   Drop the 3. A fixed number of lookups per value does not change how the work grows. What is left is n, even with a loop inside a loop.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The set holds up to n values, so the space is O(n). best, number and length are a fixed few.

   values (n numbers)bestnumberlength

Common mistake

Looping over the array instead of the set

If the input has many copies of a run start, like 100,000 copies of 1 next to 2, 3, 4, looping over the array counts that run once per copy. That is O(n²) again. Loop over the set, which holds each value once.

Tested at the limits

2,000 random arrays of 0 to 10 numbers from a tiny range, so repeats, gaps and runs are common, and the empty array comes up too. The sort and scan and the hash set gave the same answer every time.

Largest inputs	Result
100,000 numbers (the most allowed): one run of 60,000 plus 40,000 repeats, shuffled. Hash set.	0.01 s, and about 2.5 MB of extra memory: the set of 60,000 different numbers, which is the O(n) space.
100,000 numbers, same input. Sort and scan.	0.03 s, and about 0.4 MB of extra memory: it sorts in place, and the sort borrows a little room of its own.