</>Ali · LeetCode
#0128·MediumArrays

Longest Consecutive Sequence

LeetCode #128 · Medium · Arrays · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

Hash Set

Strategy

  1. 1Insert all numbers into a hash set for O(1) lookups.
  2. 2For each number, check if it's the start of a sequence (n-1 not in set).
  3. 3If it's a start, count consecutive numbers (n+1, n+2, ...) in the set.
  4. 4Track the maximum sequence length found.
Time
O(n)
each number is visited at most twice
Space
O(n)
the hash set
Problem description(from LeetCode)

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.

Examples

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

Constraints

  • •0 <= nums.length <= 10^5
  • •-10^9 <= nums[i] <= 10^9

C++ Solution

solution.cpp
class Solution {
public:
int longestConsecutive(vector<int> &nums) {
    unordered_set<int> numSet(nums.begin(), nums.end());
    int longest = 0;
    for (auto &num : numSet) {
      // if this is the start of the sequence
      if (!numSet.count(num - 1)) {
        int length = 1;
        while (numSet.count(num + length)) ++length;
        longest = max(longest, length);
      }
    }
    return longest;
  }
};

More Arrays problems