Framework Thinking - Neetcode 150 - Longest Consecutive Sequence
1. Problem (short restatement)
-
Given an unsorted array of integers nums, return the length of the longest sequence of consecutive integers (the integers must be consecutive, but order in the array doesn’t matter).
-
Example: nums = [100, 4, 200, 1, 3, 2] → longest consecutive sequence is [1,2,3,4] → return 4.
2. Clarifying questions
-
What are the input constraints? (n max, integer range)
-
Can numbers repeat? (Are duplicates allowed? If yes, how should they be handled?)
-
Are negative numbers allowed? (Usually yes — they count as normal integers.)
-
Is an empty array possible? (Return 0 for empty.)
-
Expected time/space tradeoff? (Is O(n) time and O(n) extra space acceptable?)
3. Work through example (use several, including edge cases)
-
[100, 4, 200, 1, 3, 2] → answer 4 (1,2,3,4)
-
[] → 0
-
[1] → 1
-
[1,2,2,3] → 3 (duplicates ignored; sequence 1,2,3)
-
[9,1,4,7,3,-1,0,5,8,-1,6] → 7 (-1,0,1 or 3,4,5,6,7,8,9 → 7)
-
Large contiguous block: [1000000, 999999, 1000001] → 3 (negative and large values handled similarly)
4. Brainstorm 2–3 solutions
4.1. Sort Array
-
Sort the array, then scan and count consecutive run lengths (skip duplicates).
-
Time: O(n log n) due to sort.
-
Space: O(1) or O(n) depending on sort implementation.
4.2. Hash set (optimal)
-
Put all unique numbers into a set.
-
For each number x that is the start of a sequence (i.e. x-1 not in set), iterate x, x+1, x+2, … while in set and count length. Track max.
-
Each number is visited at most once in the inner loop.
-
Time: O(n)
-
Space: O(n).
4.3. Union-Find
-
Map values to indices, union adjacent values, then find largest set size => Condtiion: Different 1
-
Time: O(n α(n))
-
Space: O(n).
Where does α(n) come from?
Let’s visualize:
-
Imagine we keep joining elements into sets with Union-Find.
-
Without optimizations, find() could take O(n) in the worst case (a tall chain).
-
But with path compression, every time you call find(), the structure flattens — all nodes on that path now directly point to the root.
-
After many operations, the height of any tree becomes incredibly small — so small that we can’t express its growth with normal functions like log(n).
That’s where Ackermann’s function and its inverse α(n) come in.
4.4. Counting Sort [min(nums), max(nums)]
-
Time complexity: O(R).
-
Space complexity: O(R)
5. Implement solutions
5.1. Brute Force
-
Start a num.
-
Continue to find num + 1, num + 2,… => Until to find the continuous increase.
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
res = 0
store = set(nums)
for num in nums:
streak, curr = 0, num
while curr in store:
streak += 1
curr += 1
res = max(res, streak)
return res
-
Time complexity: O(N^2).
-
Space complexity: O(N).
5.2. Sorting
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if not nums:
return 0
res = 0
nums.sort()
curr, streak = nums[0], 0
i = 0
while i < len(nums):
# Reset count if do not increase more
if curr != nums[i]:
curr = nums[i]
streak = 0
# Continue to skip 3 if [3,3,4,5,6]
while i < len(nums) and nums[i] == curr:
i += 1
# Counting
streak += 1
curr += 1
res = max(res, streak)
return res
-
Time complexity: O(NlogN).
-
Space complexity: O(1) or O(N) depending on the sorting algorithm.
5.3. Hash Set
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
numSet = set(nums)
longest = 0
for num in numSet:
if (num - 1) not in numSet:
length = 1
while (num + length) in numSet:
length += 1
longest = max(length, longest)
else:
# Wait for num - 1
return longest
-
Time complexity: O(N).
-
Space complexity: O(N).
5.4. Hash Map
Step 1: What the algorithm stores
-
mp[x] = the length of the consecutive sequence that x belongs to.
-
But — to stay efficient — we only really care about the first and last number of each sequence.
-
For every interval [L, R], we store:
mp[L] = mp[R] = length_of_sequence
Step 2: We want to update the start and end of the new merged sequence
Let:
left sequence = [L … num-1]
→ its length = mp[num - 1]
right sequence = [num+1 … R]
→ its length = mp[num + 1]
=> After inserting num, we merge them into [L … R].
We need to update:
mp[L] = mp[R] = total_length
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
mp = defaultdict(int)
res = 0
for num in nums:
if not mp[num]:
mp[num] = mp[num - 1] + mp[num + 1] + 1
mp[num - mp[num - 1]] = mp[num]
mp[num + mp[num + 1]] = mp[num]
res = max(res, mp[num])
return res
-
Time complexity: O(N).
-
Space complexity: O(N).
5.5. Union Find
5.5.1. Idea
- 🔹 Before any union
parent = [0, 1, 2, 3, 4, 5]
size = [1, 1, 1, 1, 1, 1]
- 🔹 Union(3,5) # connecting 1 and 2
find(3) = 3
find(5) = 5
→ Different roots, merge them.
parent = [0, 1, 2, 3, 4, 3]
size = [1, 1, 1, 2, 1, 1]
- 🔹 Union(4,1) # connecting 3 and 4
find(4) = 4
find(1) = 1
→ Different roots, attach 1 → 4.
parent = [0, 4, 2, 3, 4, 3]
size = [1, 1, 1, 2, 2, 1]
- 🔹 Union(5,4) # connecting (1,2) with (3,4)
find(5) → 3 (since parent[5] = 3)
find(4) → 4
→ Different roots, attach smaller tree → larger tree.
parent = [0, 4, 2, 3, 3, 3]
size = [1, 1, 1, 4, 2, 1]
=> The other of union do not matter, only 1 the same node is ok.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return
# union by size
if self.size[px] < self.size[py]:
px, py = py, px
self.parent[py] = px
self.size[px] += self.size[py]
def get_max_size(self):
return max(self.size) if self.size else 0
class Solution:
def longestConsecutive(self, nums: list[int]) -> int:
if not nums:
return 0
nums = list(set(nums)) # remove duplicates
index = {num: i for i, num in enumerate(nums)} # map num -> index in UF
uf = UnionFind(len(nums))
for num in nums:
if num + 1 in index:
uf.union(index[num], index[num + 1])
return uf.get_max_size()
5.5.2. Dry run
- num = 100
→ 101 not in index → no union.
- num = 4
→ 5 not in index → no union.
- num = 200
→ 201 not in index → no union.
- num = 1
→ 2 exists! → union(index[1], index[2]) = union(3, 5)
parent = [0,1,2,3,4,3]
size = [1,1,1,2,1,1]
- num = 3
→ 4 exists! → union(index[3], index[4]) = union(4, 1)
parent = [0,4,2,3,4,3]
size = [1,1,1,2,2,1]
- num = 2
→ 3 exists! → union(index[2], index[3]) = union(5, 4)
parent = [0,4,2,3,3,3]
size = [1,1,1,4,2,1]
✅ Merged {1,2} and {3,4} → now {1,2,3,4} (size = 4)
5.5.3. Why we only need to join with num + 1, but not num - 1
- Because if existed num - 1 => you can loop to array and you will find num - 1 and union vs component from num.
5.5.4. Time complexity
-
First optimization: Union by Rank (or Size), merge small tree to large tree.
-
Second optimization: Path Compression => Whenever you do a find(x), you make every node on the path point directly to the root.
-
Time complexity: Total = O(N × α(N)) ≈ O(N) (α(N) ≤ 5)
-
Space complexity: O(N) — parent[], size[], and hash map
5.6. Counting Sort
class Solution:
def longestConsecutive(self, nums: list[int]) -> int:
if not nums:
return 0
mn, mx = min(nums), max(nums)
n = mx - mn + 1
# Counting sort-like presence array
present = [False] * n
for num in nums:
present[num - mn] = True
# Scan for longest consecutive True streak
longest = curr = 0
for exist in present:
if exist:
curr += 1
longest = max(longest, curr)
else:
curr = 0
return longest
-
Time complexity: O(N) when fill the value + O(R) when loop to scan
-
Space complexity: O(R)