#128

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Longest Consecutive Sequence

Find the length of the longest consecutive elements sequence in an unsorted array using array scanning and hash lookup.

Problem Statement

You are given an unsorted array of integers. The task is to find the length of the longest consecutive elements sequence. The sequence should contain elements that follow one another without interruption. The algorithm must achieve O(n) time complexity to handle large input sizes efficiently.

The solution requires an efficient approach, utilizing a hash table for constant time lookups. By scanning the array and verifying consecutive sequences, the problem can be solved in linear time. Avoid brute force methods which can lead to inefficiency.

Examples

Example 1

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

Output: 4

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 details omitted.

Example 3

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

Output: 3

Example details omitted.

Constraints

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

Solution Approach

Array Scanning and Hash Lookup

The solution involves iterating through the array and using a hash set to store unique elements. For each element, you check if it's the start of a consecutive sequence. By scanning once and performing constant-time lookups, this approach guarantees O(n) time complexity.

Hash Table for Fast Lookup

A hash set allows constant-time membership checking, enabling quick identification of consecutive elements. This ensures that you can track the sequence length efficiently without needing nested loops, maintaining optimal time complexity even for large inputs.

Edge Case Handling

Special edge cases, like an empty array or a single-element array, must be handled separately. The algorithm should quickly return 0 or 1 for these cases, avoiding unnecessary computation. This attention to edge cases ensures robustness.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the number of elements in the array, because we only scan through the array once. Space complexity is also O(n), due to the hash set used to store elements for quick lookup.

What Interviewers Usually Probe

Do you understand how to use a hash table for constant-time lookups?
Can you explain why this solution guarantees O(n) time complexity?
Will you consider edge cases such as empty arrays or single-element arrays?

Common Pitfalls or Variants

Common pitfalls

Relying on brute force methods like sorting or nested loops leads to suboptimal O(n log n) or O(n^2) time complexity.
Forgetting to handle edge cases, like arrays with one element or empty arrays, can lead to incorrect results.
Not using the hash table efficiently, such as by repeatedly checking for consecutive numbers instead of storing them all for quick lookups.

Follow-up variants

Find the longest consecutive sequence in a sorted array.
Determine the longest consecutive subsequence in an array of integers with duplicates.
Implement a solution using Union-Find to track consecutive sequences.

FAQ

What is the time complexity of the Longest Consecutive Sequence problem?

The optimal solution has a time complexity of O(n), where n is the number of elements in the array, due to the use of hash lookups.

How do you handle edge cases in the Longest Consecutive Sequence problem?

Edge cases such as an empty array or an array with only one element should be handled early to avoid unnecessary processing.

What data structure is used to efficiently solve the Longest Consecutive Sequence problem?

A hash set is used to store elements for fast lookup, enabling the solution to check consecutive sequences in constant time.

Can you solve the Longest Consecutive Sequence problem without sorting?

Yes, sorting the array is unnecessary. The problem can be solved using hash lookups, which ensures optimal time complexity of O(n).

Why does the Longest Consecutive Sequence solution need O(n) time?

The algorithm needs to scan the array once and check for consecutive sequences using constant-time hash lookups, making it efficient with a time complexity of O(n).

terminal

Solution

Solution 1: Hash Table

We can use a hash table $\textit{s}$ to store all the elements in the array, a variable $\textit{ans}$ to record the length of the longest consecutive sequence, and a hash table $\textit{d}$ to record the length of the consecutive sequence each element $x$ belongs to.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        ans = 0
        d = defaultdict(int)
        for x in nums:
            y = x
            while y in s:
                s.remove(y)
                y += 1
            d[x] = d[y] + y - x
            ans = max(ans, d[x])
        return ans

Solution 2: Hash Table (Optimization)

Similar to Solution 1, we use a hash table $\textit{s}$ to store all the elements in the array and a variable $\textit{ans}$ to record the length of the longest consecutive sequence. However, we no longer use a hash table $\textit{d}$ to record the length of the consecutive sequence each element $x$ belongs to. During the iteration, we skip elements where $x-1$ is also in the hash table $\textit{s}$. If $x-1$ is in the hash table $\textit{s}$, then $x$ is definitely not the start of a consecutive sequence, so we can directly skip $x$.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        ans = 0
        d = defaultdict(int)
        for x in nums:
            y = x
            while y in s:
                s.remove(y)
                y += 1
            d[x] = d[y] + y - x
            ans = max(ans, d[x])
        return ans

Continue Practicing

#721 accounts merge #839 similar string groups #924 minimize malware spread