← all entries
A-009● Day 092026.05.11mediumleetcode #128neetcode150

Longest Consecutive Sequence

#array#hash-table#union-find
↗ leetcode #128 · longest-consecutive-sequence
01

Problem

· problem
P.009

Longest Consecutive Sequence

↗ leetcode #128

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.

constraints
  • · 0 ≤ nums.length ≤ 10⁵
  • · -10⁹ ≤ nums[i] ≤ 10⁹
  • · 배열에는 중복된 원소가 포함될 수 있음 / Array may contain duplicate elements
// paraphrased summary — see source for full text
examples
example 1input → output
[100,4,200,1,3,2]
4
example 2input → output
[0,3,7,2,5,8,4,6,0,1]
9
example 3input → output
[1,0,1,2]
3
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    What is the difference between consecutive elements in the sequence?
  • ☐
    Must the sequence appear in consecutive positions within the array?
  • ☐
    How should duplicate numbers in the array be handled?
  • ☐
    Why is the O(n) time constraint necessary if sorting would be simpler?
  • ☐
    Can you solve this in O(n) time without using a hash set?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Convert array to set
○
numSet = set(nums)
○
numSet = sorted(nums)
○
numSet = {n: True for n in nums}
step 2· Initialize longest sequence length
○
longest = 0
○
longest = 1
○
longest = float('-inf')
step 3· Iterate through each number in the set
○
for n in numSet:
○
for n in nums:
○
for i in range(len(numSet)):
step 4· Check if number is sequence start│ nested
○
if (n - 1) not in numSet:
○
if (n + 1) not in numSet:
○
if n not in visited:
step 5· Initialize and extend sequence length│ │ nested
○
length = 1
○
length = 0
○
length = len([x for x in numSet if x >= n])
step 6· Count consecutive numbers│ │ nested
○
while (n + length) in numSet:
○
while (n + length) in numSet and length < 100:
○
while (n - length) in numSet:
step 7· Update maximum│ │ nested
○
longest = max(length, longest)
○
longest = length
○
longest += length
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
class Solution:
2
    def longestConsecutive(self, nums: List[int]) -> int:
3
        numSet = set(nums)
4
        longest = 0
5
6
        for n in numSet:
7
            # check if its the start of a sequence
8
            if (n - 1) not in numSet:
9
                length = 1
10
                while (n + length) in numSet:
11
                    length += 1
12
                longest = max(length, longest)
13
        return longest
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[100,4,200,1,3,2]
→
4
case 2
[0,3,7,2,5,8,4,6,0,1]
→
9
case 3
[1,0,1,2]
→
3
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.