Longest Reading Streak

Hardhash mapAlso known as Longest Consecutive Sequence

A reading app numbers days from its launch: day 0 is launch day, day 1 the day after, and people who tested it early have negative days. Every time you read, the app logs the day number. The log syncs from your phone and your tablet, so it arrives jumbled, and a day you read twice appears twice.

The app wants to show your best ever streak: the longest run of back-to-back days on which you read at least once.

Your task

Write longestStreak(days). Return the length of the longest run of consecutive whole numbers d, d + 1, ..., d + L - 1 that all appear in days. Repeated day numbers count once.

An empty log returns 0. Aim for O(n) time: sorting works but costs O(n log n).

longestStreak(days: int[]) → int

Examples

Example 1

Input

days = [12, 4, 10, 5, 11, 13, 3, 11]

Output

Why

Days 10, 11, 12, 13 make a streak of 4. Days 3, 4, 5 make a streak of 3. Day 11 appears twice, but it is still one day, so the answer is 4, not 5.

Example 2

Input

days = [-1, 7, 1, 0, -2]

Output

Why

Days -2, -1, 0, 1 are back to back, a streak of 4 that runs across launch day. Day 7 stands alone.

Example 3

Input

days = []

Output

Why

No reading at all, so the best streak is 0.

Constraints

0 ≤ days.length ≤ 100,000
-1,000,000,000 ≤ days[i] ≤ 1,000,000,000

Start with brute force

For each day, count upward from it, checking whether d + 1, d + 2 and so on appear by scanning the log each time.

Each check is a scan of n entries, and a single long streak gets recounted from every one of its days. That is O(n³) in the worst case, hopeless for 100,000 entries. Even with a set to make each check O(1), starting from every day still recounts a streak of length L about L²/2 times: one streak of 100,000 days costs 5 billion steps.

Hints

0 of 4 shown

Hint 1
In the first example, which day numbers could be the first day of a streak? What is true about the day before each of them?
Hint 2
A day d starts a streak exactly when d - 1 is not in the log. Days 3 and 10 start streaks; days 4, 5, 11, 12 and 13 do not.
Hint 3
If you could ask "is this day in the log?" in one step, then from each starting day you could count upward until the streak breaks. Which structure answers that question in one step, and also removes the duplicates?
Hint 4
Put every day into a hash set. For each day d in the set, skip it if d - 1 is also in the set. Otherwise count d, d + 1, d + 2, ... while they are in the set, and keep the longest count. Because counting only starts at streak beginnings, every day is counted once.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Two ideas fit together here. First, a hash set lets you ask "did I read on day x?" in one step, and it removes repeats for free. Second, only count a streak from its first day, the one whose previous day is missing. Then each streak is walked exactly once.

Trace [12, 4, 10, 5, 11, 13, 3, 11]. The set is {12, 4, 10, 5, 11, 13, 3}.

12: 11 is in the set, so 12 is mid-streak. Skip.
4: 3 is in the set. Skip.
10: 9 is missing, so 10 starts a streak. Count 11, 12, 13 (all present), then 14 is missing. Length 4. best = 4.
5 and 11 and 13: each has its previous day in the set. Skip.
3: 2 is missing, so count up: 4, 5, then 6 is missing. Length 3. best stays 4.

Why is this O(n) when there is a loop inside a loop? The inner while only runs from streak starts, and each day belongs to exactly one streak. So across the whole run, the inner loop steps over each day once. Loop over the set, not the original list, or a repeated starting day would recount its whole streak.

Reference solution

function longestStreak(days) {
  const logged = new Set(days); // also drops repeated days
  let best = 0;
  for (const d of logged) {
    if (logged.has(d - 1)) continue; // not the first day of a streak
    let length = 1;
    while (logged.has(d + length)) length++;
    best = Math.max(best, length);
  }
  return best;
}

def longest_streak(days):
    logged = set(days)  # also drops repeated days
    best = 0
    for d in logged:
        if d - 1 in logged:  # not the first day of a streak
            continue
        length = 1
        while d + length in logged:
            length += 1
        best = max(best, length)
    return best

TimeO(n)Building the set is O(n), and each day is visited once by the outer loop and at most once by an inner count.

SpaceO(n)The set holds every distinct day.

Learn the idea: Hash Tables Arrays

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code