BL
U

122. Longest Consecutive Sequence in O(N)

Easy

Problem Description

Given an unsorted array of NN integers, find the length of the longest consecutive elements sequence in O(N)O(N) expected time using a hash set.

Input Format

  • •Line 1: An integer NN (0≤N≤1050 \le N \le 10^5).
  • •Line 2: NN space-separated integers. (Omitted if N=0N = 0).

Output Format

Print the length of the longest consecutive sequence.

Example 1:
Input:
6
100 4 200 1 3 2
Output:
4
Explanation: Longest consecutive sequence is [1, 2, 3, 4], length 4.
Example 2:
Input:
10
0 3 7 2 5 8 4 6 0 1
Output:
9
Explanation: Consecutive sequence from 0 to 8 has length 9.
Example 3:
Input:
0
Output:
0
Explanation: Empty array has length 0.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online