progress

~/problems / Arrays & hashing / Hash maps and counting

Longest Consecutive Sequence

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium ~25 min

Write longest_consecutive(nums) that returns the length of the longest run of integers x, x+1, x+2, ... whose values all appear somewhere in nums. Positions don't matter, only which values are present.

  • 0 <= len(nums) <= 2 * 10^5; values are in [-10^9, 10^9]; duplicates may appear.
  • ⭐ Bonus: counting upward from every element is O(n²) on some inputs and still passes; a speed test with 200,000 values earns a star in O(n).
longest_consecutive([10, 4, 12, 5, 11, 6, 13, 7])   # 4   (4, 5, 6, 7 and 10..13 are both length 4)
longest_consecutive([3, 3, 2])                      # 2
longest_consecutive([])                             # 0
Show hint

put the values in a set. Counting upward from every value repeats work; which values are the only ones worth starting a count from?

Topic: Hash maps and counting. Counter/defaultdict, complement lookups, prefix-sum + hash map.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc