# using BFS from collections import deque from typing import List class Solution: def longestConsecutive(self, nums: List[int]) -> int: if not nums: return 0 # Convert nums to set for O(1) lookup num_set = set(nums) visited = set() max_length = 0 def bfs(num): queue = deque([num]) visited.add(num) sequence_length = 1 # Check both directions (left and right) left = right = num # Expand to left while left - 1 in num_set and left - 1 not in visited: left -= 1 queue.append(left) visited.add(left) sequence_length += 1 # Expand to right while right + 1 in num_set and right + 1 not in visited: right += 1 queue.append(right) visited.add(right) sequence_length += 1 return sequence_length # Try BFS from each number that hasn't been visited for num in nums: if num not in visited: max_length = max(max_length, bfs(num)) return max_length
Wow great vid and explanation!!
very nice explanation
Lovely explanation from a lovely person.
# using BFS
from collections import deque
from typing import List
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if not nums:
return 0
# Convert nums to set for O(1) lookup
num_set = set(nums)
visited = set()
max_length = 0
def bfs(num):
queue = deque([num])
visited.add(num)
sequence_length = 1
# Check both directions (left and right)
left = right = num
# Expand to left
while left - 1 in num_set and left - 1 not in visited:
left -= 1
queue.append(left)
visited.add(left)
sequence_length += 1
# Expand to right
while right + 1 in num_set and right + 1 not in visited:
right += 1
queue.append(right)
visited.add(right)
sequence_length += 1
return sequence_length
# Try BFS from each number that hasn't been visited
for num in nums:
if num not in visited:
max_length = max(max_length, bfs(num))
return max_length
Let's visualize how the BFS solution works with nums = [100,4,200,1,3,2]
Initial array: [100, 4, 200, 1, 3, 2]
Step-by-step visualization:
1. Convert to set: {1, 2, 3, 4, 100, 200}
visited = {}
2. Start with first number (100):
100 → Check: 99? No 101? No
Sequence: [100]
visited = {100}
Length = 1
max_length = 1
3. Next unvisited number (4):
4 → Check: 3? Yes 5? No
3 → Check: 2? Yes
2 → Check: 1? Yes
Sequence: [1, 2, 3, 4]
visited = {100, 1, 2, 3, 4}
Length = 4
max_length = 4
4. Next unvisited number (200):
200 → Check: 199? No 201? No
Sequence: [200]
visited = {100, 1, 2, 3, 4, 200}
Length = 1
max_length = 4
Visual representation:
Numbers on number line:
1 - 2 - 3 - 4 ... 100 ... 200
└─────────┘ │ │
4 1 1
└── Longest sequence
Sequence discovery:
100: ●
Length = 1
4: ● ─ ● ─ ● ─ ●
4 3 2 1
Length = 4
200: ●
Length = 1
Final Result: 4 (longest consecutive sequence: [1,2,3,4])