MediumNo. 0128
Longest Consecutive Sequence — LeetCode 128 Python Solution
- Pattern
- Union-Find
- Topics
- Union Find, Array, Hash Table
- On study lists
- Blind 75, NeetCode 150 and Top Interview 150
- Reading time
- 2 min
- Source
- leetcode.com
The 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
- Input
- nums = [100,4,200,1,3,2]
- Output
- 4
- Explanation
- The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Python solution
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 ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 128. Longest Consecutive Sequence is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0721 | Accounts Merge | Medium |
| 0839 | Similar String Groups | Hard |
| 0924 | Minimize Malware Spread | Hard |
| 0928 | Minimize Malware Spread II | Hard |
| 0952 | Largest Component Size by Common Factor | Hard |
| 0959 | Regions Cut By Slashes | Medium |
Frequently asked questions
- How hard is LeetCode 128. Longest Consecutive Sequence?
LeetCode 128. Longest Consecutive Sequence is rated Medium on LeetCode.
- What is the time complexity of LeetCode 128. Longest Consecutive Sequence?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 128. Longest Consecutive Sequence?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 128. Longest Consecutive Sequence cover?
LeetCode 128. Longest Consecutive Sequence is tagged Union Find, Array and Hash Table on LeetCode.