Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Longest Consecutive Sequence

LeetCode #128Medium
Unordered · longest run of consecutive integers in O(n)

Given an unsorted array of integers, return the length of the longest sequence of consecutive integers (in any order). Solve it in O(n) time.

Asked atGoogleFacebookAmazon
step 1 / 24
100
4
200
1
3
2
[0][1][2][3][4][5]
Brute force · sort
▸
1given arr
2sort arr ascending
3streak ← 1;  best ← 1
4for i ← 1 to n − 1:
5    if arr[i] == arr[i−1] + 1: streak++  else if arr[i] != arr[i−1]: streak ← 1
6    best ← max(best, streak)
7return best
state
  • input{100,4,200,1,3,2}

line 1We want the longest run of consecutive integers; their order in the array does not matter. First idea: sort the numbers so consecutive values sit next to each other.