Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Arrays

Longest Consecutive Sequence

Medium · Arrays · Asked at Google, Amazon, Microsoft, Uber

Print the length of the longest sequence of consecutive integers that can be formed from the array values (order in the array does not matter).

Input

First line: n. Second line: n space-separated integers.

Output

The length of the longest consecutive sequence.

Constraints

Put everything in a hash set and only start counting from numbers whose predecessor is missing — O(n).

Example 1

Input

6
100 4 200 1 3 2

Output

4

Example 2

Input

10
0 3 7 2 5 8 4 6 0 1

Output

9

Hints

  1. Sorting gives O(n log n). A hash set can do it in O(n).
  2. Only start counting from x when x − 1 is not in the set — then x begins a sequence.

Approach

Put every value in a hash set (duplicates disappear). For each x whose predecessor x − 1 is missing, count upward x, x+1, x+2… while they are in the set. Each number is visited by at most one such count, so the total work is O(n). (Sorting and scanning is a simpler O(n log n) alternative.)

Complexity: O(n) average time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    unordered_set<long long> s;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        s.insert(x);
    }
    int best = 0;
    for (long long x : s) {
        if (s.count(x - 1)) continue;
        int len = 1;
        while (s.count(x + len)) len++;
        best = max(best, len);
    }
    cout << best << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
s = set(data[1 : data[0] + 1])
best = 0
for x in s:
    if x - 1 in s:
        continue
    length = 1
    while x + length in s:
        length += 1
    best = max(best, length)
print(best)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Set<Long> s = new HashSet<>();
        for (int i = 0; i < n; i++) s.add(sc.nextLong());
        int best = 0;
        for (long x : s) {
            if (s.contains(x - 1)) continue;
            int len = 1;
            while (s.contains(x + len)) len++;
            best = Math.max(best, len);
        }
        System.out.println(best);
    }
}

Solve Longest Consecutive Sequence online · All practice problems