We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Consecutive Sequence

Difficulty: Medium

Problem Description

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

Key Insights

  • The longest consecutive sequence can be found without sorting the array.
  • A hash set is useful for O(1) average time complexity lookups.
  • An optimal approach involves checking for each number if it's the start of a sequence.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a hash set to store all the elements of the array. Then, we iterate through each number in the array, and for each number, we check if it is the start of a consecutive sequence (i.e., if the number just before it is not in the set). If it is the start, we count how many consecutive numbers exist in the set starting from that number. This approach ensures that each number is processed only once, allowing us to achieve O(n) time complexity.

Code Solutions

def longestConsecutive(nums):
    num_set = set(nums)  # Store all numbers in a set for O(1) lookups
    longest_streak = 0

    for num in num_set:
        # Check if it's the start of a sequence
        if num - 1 not in num_set:
            current_num = num
            current_streak = 1

            # Count consecutive numbers
            while current_num + 1 in num_set:
                current_num += 1
                current_streak += 1

            longest_streak = max(longest_streak, current_streak)

    return longest_streak
← Back to All Questions