Longest Consecutive Badge Streak

Hard ⏱ 18 min 34% acceptance ★★★★☆ 4.4
Employees earn a numbered daily badge. Given an unsorted list of badge day-numbers (with possible duplicates), write longest_streak(days) returning the length of the longest run of consecutive numbers. Aim for O(n): use a set and only start counting from numbers that begin a run.

Examples

Example 1
Input
longest_streak([100, 4, 200, 1, 3, 2])
Output
4
Explanation

The run 1,2,3,4 has length 4.

Constraints

  • O(n log n) sorting is acceptable, O(n) with a set is ideal.
  • Empty input returns 0.

Topics

Setsalgorithm

Companies

GoogleMetaAmazon

Hints

Hint 1

A number n starts a run only if n-1 is absent from the set.

Hint 2

From each run start, count upward while n+1 is present.

← Detect Duplicate Matchups Same Inventory, Different Receipts →
Loading the Python runtime… Run executes your code and shows printed output; Submit checks your function against this problem's examples.