-
Notifications
You must be signed in to change notification settings - Fork 0
039 — Longest Consecutive Sequence
LeetCode 128 · Medium. Given an unsorted array of integers nums, return the length of the longest run of consecutive integers (e.g., [100, 4, 200, 1, 3, 2] contains the consecutive run 1, 2, 3, 4, so the answer is 4) — the elements don't need to be consecutive in the array, just consecutive in value.
Imagine a box of numbered puzzle pieces dumped on a table, and you need to find the longest unbroken chain you can build (piece 7 connects to 8, which connects to 9, and so on). One approach: line every piece up in numeric order first, then walk the line counting how long each unbroken run is — reliable, but you paid the cost of fully ordering the whole table first. A sharper approach: for every piece, ask one quick question — "is there a piece labeled one less than me anywhere on the table?" If yes, skip it — you're not the start of a chain, someone else will count you when they walk forward from their start. If no piece is one less, you're a chain's true starting piece, so start walking forward (+1, +1, +1...) as far as the chain goes, and that's your chain's length. Every piece only ever gets "walked" as part of exactly one chain — the one it truly starts.
"Longest run of consecutive [values]", especially with a hint like "can you do it in O(n)?", is the signal for the hash-set-with-start-detection trick: put every value into a set for O(1) membership checks, then only ever start counting a sequence from a value that has no predecessor in the set (i.e., value - 1 isn't present). That "only count from true starts" rule is what keeps the total work linear instead of re-walking the same chain from every one of its members.
Sort the array, then walk through it once counting the length of each unbroken run of consecutive values (skipping duplicates).
func longestConsecutiveBruteForce(_ nums: [Int]) -> Int {
guard !nums.isEmpty else { return 0 }
let sorted = nums.sorted()
var longest = 1
var current = 1
for i in 1..<sorted.count {
if sorted[i] == sorted[i - 1] {
continue // duplicate, doesn't break or extend a run
} else if sorted[i] == sorted[i - 1] + 1 {
current += 1
longest = max(longest, current)
} else {
current = 1 // run broken, restart count
}
}
return longest
}Big-O: O(n log n) time, dominated by the sort; the scan afterward is O(n). O(n) space for the sorted copy of the array.
Put every number in a hash set. For each number that has no predecessor in the set (meaning it's the start of a sequence), walk forward counting how far the consecutive run extends.
func longestConsecutive(_ nums: [Int]) -> Int {
let numSet = Set(nums)
var longest = 0
for num in numSet {
guard !numSet.contains(num - 1) else {
continue // num - 1 exists, so num is NOT the start of its sequence — skip it
}
var length = 1
var current = num
while numSet.contains(current + 1) {
current += 1
length += 1
}
longest = max(longest, length)
}
return longest
}Big-O: O(n) time — building the set is O(n), and although there's a while loop nested inside the for loop, the inner loop only ever runs for numbers that are true sequence starts; every number gets visited by the inner while loop at most once across the entire function, since it's only ever walked forward from its sequence's start. O(n) space for the set.
The brute force pays an O(n log n) sorting tax to get numbers into an order where "is the next value present?" becomes "look at the next array slot." The hash set gets the same O(1) "is this value present?" answer without any ordering at all — but naively checking every number's forward chain would degrade back to O(n²) (imagine starting a full walk from every element of a long run). The fix is the predecessor check: only start walking forward from values that have no value - 1 in the set. That guarantees each element is only ever visited by exactly one chain's walk — the one it's the true start of — which is what keeps the total work across all chains linear instead of quadratic.
-
Hash Maps & Hash Sets — the
O(1)membership checks this solution depends on entirely. - Arrays & Strings — the input array and the sorted-array baseline in the brute force.
- Big-O Notation — for the "each element visited at most once overall" amortized-linear argument above.
-
Sliding Window — disclosed as a loose fit, not a natural one: there's no window being shrunk from the left here — every element is visited by the inner
whileloop at most once total across the whole function, so there's nothing to contract. The only thread connecting it to this chapter is the forward walk from each true sequence-start (while numSet.contains(current + 1) { current += 1; length += 1 }inlongestConsecutive), which is the same "expand the right edge while a condition holds" growth Sliding Window covers — just missing the "shrink from the left" half that makes a window a window.
Longest Consecutive Sequence is puzzle pieces on a table — only start walking a chain from a piece with no predecessor, so every piece gets counted by exactly one walk.
For nums = [1, 2, 0, 1] (note the duplicate 1), trace through the optimal solution: which values become the set numSet, which value(s) qualify as sequence starts (no predecessor in the set), and what length does each start's forward walk produce? What's the final answer, and why doesn't the duplicate 1 cause any double-counting?
⬅️ Previous: Encode and Decode Strings · Next: Valid Palindrome ➡️