Logo for ammarahmed.ca
Medium
May 25, 2025
#arrays
#math

128. Longest Consecutive Sequence

Problem

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.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

  • 0 <= nums.length <= 105
    • -109 <= nums[i] <= 109

      Approach

      We can start by creating a hashmap to store which numbers occur in the array. After this, we iterate over the numbers. For each number, we check if the value one less than it occurs in the array via the hashmap. If it doesn't, we know we are the start of a sequence. Once we know we are at the start of a sequence, we iterate as long as there is a value exactly one more than that in the array, keep track of the count. We update the max value with this count.

      Edge Cases

      The first edge case is when there are no values in the array, we want to simply return 0.

      The next edge case occurs with the time complexity. If there are duplicates of the start of a sequence, without proper handling, we'll run unnecessary iterations. For example, if a sequence starts with 0 and has a length of 100, and we have two zeroes in the array, we'll run that 100 length iteration twice. To mitigate this, we want to mark in the hash map if the start of a sequence has already been processed and check for that mark before iterating over the sequence and override it.

      In our case, we do this by marking with a boolean value in the hashmap since we are using a boolean map.

      Complexity

      Time: O(n)

      It might look like it's not O(n) because we have a nested loop, however, there is an important consideration. We only go down that nested loop if it's the start of a sequence, otherwise, we keep marching forward. Therefore, in the worst case, when all values are consecutive, we only go down the nested loop once, maintaining O(n)

      Space: O(n)

      We create a hashmap of size n.

      Solution

      1func longestConsecutive(nums []int) int { 2 // Edge case check 3 if len(nums) == 0 { 4 return 0 5 } 6 7 // Creating hash map 8 freq := make(map[int]bool) 9 for _, num := range nums { 10 if _, exists := freq[num]; !exists { 11 freq[num] = true 12 } 13 } 14 15 // Intialize to 1 because we already handled the case if its zero 16 ans := 1 17 for _, num := range nums { 18 // If there is no previous value, start of a sequence 19 if _, prevExists := freq[num - 1]; !prevExists { 20 if !freq[num] { // Check if the current value is marked as false (we've already processed this sequence start) 21 continue 22 } 23 freq[num] = false // Mark the sequence start as processed 24 25 // Find the length of the sequence 26 count := 0 27 _, hasNext := freq[num + count] 28 for hasNext { 29 count++ 30 _, hasNext = freq[num + count] 31 } 32 // Update answer 33 ans = max(ans, count) 34 } 35 } 36 37 return ans 38} 39