LeetCode 128 - Longest Consecutive Sequence

This is a Medium array problem: return the length of the longest consecutive sequence without sorting. Counting from every value repeats the same sequence, so this solution only starts from values that have no predecessor.

---

Problem link and explanation

• Problem link: 128. Longest Consecutive Sequence
• Summary: Given an integer array nums, return the length of the longest sequence of consecutive integer values.

For example:

nums = [100, 4, 200, 1, 3, 2]

The longest consecutive sequence is [1, 2, 3, 4], so the answer is 4. The values are not sorted in the input, but the sequence is based on the numeric values themselves.

---

Approach

Sorting would make adjacent comparisons easy, but it costs O(n log n). Using a set avoids that sorting cost by checking value existence in average constant time.

First, convert nums into a set.

num_set = set(nums)

Then iterate through the values, but do not start counting from every number. If the current value is num and num - 1 exists in the set, num is already in the middle of another consecutive sequence. For example, if the current value is 3 and 2 exists, there is no reason to start from 3 because the same sequence can be counted from its earlier value.

if num - 1 in num_set:
    continue

If num - 1 does not exist, num is the starting point of a sequence. From there, keep increasing cur_num while the value exists in the set.

streak = 0
cur_num = num

while cur_num in num_set:
    streak += 1
    cur_num += 1

The code has a while loop inside a for loop, but the total work is still linear. Middle values are skipped by the predecessor check, so the same consecutive sequence is not counted again from every element.

---

Troubleshooting

My first version iterated over nums in the outer for loop instead of iterating over num_set. I was already using a set for lookups, so that looked harmless at first, but nums can still contain duplicates and the same starting value can be processed more than once.

If a duplicated value is also the start of a sequence, the while loop counts the same consecutive range again each time that value appears in nums. Switching the outer loop to num_set removes those duplicate starting points and keeps each sequence start processed once.

---

Complexity analysis

• Time complexity: O(n)

  • Building the set costs O(n). The outer loop over num_set and the sequence-extension loops together do at most about 2n lookups, which reduces to O(n) after dropping constants.

• Space complexity: O(n)

  • The set stores the input values and scales with the input size.

The key condition is the starting-point check. By counting only when num - 1 does not exist, the solution avoids sorting and keeps the total number of lookups linear.

---

Optimized code

from typing import List, Set

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set: Set[int] = set(nums)
        max_streak = 0

        for num in num_set:
            if num - 1 in num_set:
                continue

            streak = 0
            cur_num = num

            while cur_num in num_set:
                streak += 1
                cur_num += 1

            max_streak = max(streak, max_streak)

        return max_streak

---

Summary and reflection

The set gives fast existence checks, but the main detail is choosing where a sequence is allowed to start. If the previous value exists, the current value is part of a sequence that can be counted earlier. Starting only from values with no predecessor keeps the solution at O(n) time without sorting.