RTE logo
← Back to DSA map
Arrays & Hashing

Longest Consecutive Sequence

Length of the longest run of consecutive numbers, in a single pass.

Medium

Problem

Given an unsorted array of numbers, return the length of the longest run of consecutive numbers. Your solution must look at each number only a constant number of times - roughly one pass, written O(n).

  • The numbers must be consecutive: 1, 2, 3, 4.
  • Their order in the array does not matter.
  • Solve it in O(n) time.

Examples

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
The sequence is [1, 2, 3, 4].
Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9
Input: nums = []
Output: 0

Approach

Time O(n)Space O(n)
  1. Put every number in a Set, which also removes duplicates.
  2. For each number, check whether num - 1 is in the set. If it is, this number is in the middle of a run, so skip it.
  3. If num - 1 is missing, num starts a run: count upward while num + 1, num + 2, ... are in the set.
  4. Keep the longest run you have seen. Each number gets counted at most once as part of a run, so the whole thing stays one pass.

Brute force: Sort first, then scan for runs. Simple, but sorting alone costs more than one pass, so it misses what the problem asks for.

Common mistakes

  • Counting upward from every number, instead of only from the ones that start a run, makes you re-walk the same runs again and again.
  • Iterate over the set, not the array, so duplicate values are not counted twice.

Step through it

Pick an input and play the algorithm step by step. The highlighted line in the code follows each step, and you can edit the code to experiment.

LONGEST SEQ
Solution · JS
Set · num=— best=0
Nums
1000
41
2002
13
34
25
Set
100
4
200
1
3
2
length 0
best 0
current —
current streak appears here
Num
—
Current
—
Length
0
Best
0
Set
6
0 / 0
1×
Execution log
steps appear here…

Solution

The same approach in JavaScript, Python, and Java. Each is a complete program that prints the examples above - JavaScript runs here, so edit it and try your own input.

Edit and run it here

JavaScript solution

Loading...

Output

Run code to see output...

Comments

Sign in to leave a comment. Your name and photo come from Google; nothing else is shared.

Loading comments...