128. Longest Consecutive Sequence

2024, Apr 17 One min read

1. Description

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.

2. Example

Example 1

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Example 3

Input: nums = [1,0,1,2]
Output: 3

3. Constraints

0 <= nums.length <= 10$^{5}$
-10$^{9}$ <= nums[i] <= 10$^{9}$

4. Solutions

Hash Table

n = nums.size()
Time complexity: O(n)
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int longestConsecutive(const vector<int> &nums) {
        unordered_set<int> values(nums.begin(), nums.end());

        int max_length = 0;
        for (int num : values) {
            if (values.find(num - 1) == values.end()) {
                int value = num;
                int length = 1;

                while (values.find(value + 1) != values.end()) {
                    ++value;
                    ++length;
                }

                max_length = max(max_length, length);
            }
        }

        return max_length;
    }
};

Search

Tags