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

Longest Consecutive Sequence

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.
  • Aim for O(n). Counting upward from every element is O(n²) on some inputs, and the tests include one.
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