A raffle sold tickets with whole numbers on them, in no particular order, and some numbers may appear more than once. Write a function that returns the length of the longest run of consecutive ticket numbers that were sold, like 7, 8, 9, 10.
The numbers don't need to be next to each other in the list. Aim for O(n) time: sorting first works, but it's O(n log n).
text
1longest_streak([102, 4, 100, 1, 3, 2]) -> 4
2longest_streak([5, 5, 6]) -> 2
3longest_streak([]) -> 0
Example 1
102
0
4
1
100
2
1
3
3
4
2
5
1, 2, 3 and 4 were all sold: a streak of 4.
In the first example, the run is 1, 2, 3, 4. In the second, the repeated 5 still counts once.
Write longest_streak(tickets) in Python or longestStreak(tickets) in JavaScript.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 21 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
The sorting answer
Sort the numbers and walk through them, extending the current run when a number is one more than the last, skipping duplicates, and starting over otherwise. That's correct and O(n log n). The problem asks for better, so what does sorting give you that you could get another way?
Step 2
What you really need to know
For any number x, you only need to answer "is x + 1 there?" quickly. Put every number in a set and that question is O(1).
Step 3
Don't count the same run twice
If you start counting from every number, a run of length k gets counted from each of its k numbers, which is O(n²) in the worst case. Only start counting from a number that begins a run: one where x - 1 is not in the set.
Step by step1 / 3
x
102
0
4
1
100
2
1
3
3
4
2
5
4: is 3 in the set? Yes, so 4 isn't the start of a run. Skip it.
Step 4
Why that's O(n)
Each number is the start of at most one run, and while counting a run you only step through numbers in that run. So every number is visited a constant number of times in total.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Put all the numbers in a set. For each number in the set that has no x - 1 before it, count upwards (x + 1, x + 2, ...) while the next number is in the set, and keep the longest count.
python
1def longest_streak(tickets):
2 numbers = set(tickets)
↑a set: O(1) "is it there?"
3 best = 0
4 for x in numbers:
5 if x - 1 not in numbers: # x starts a run
↑only start at the beginning of a run
6 length = 1
7 while x + length in numbers:
↑count up while the next one exists
8 length += 1
9 best = max(best, length)
10 return best
javascript
1function longestStreak(tickets) {
2 const numbers = new Set(tickets)
↑a set: O(1) "is it there?"
3 let best = 0
4 for (const x of numbers) {
5 if (!numbers.has(x - 1)) { // x starts a run
↑only start at the beginning of a run
6 let length = 1
7 while (numbers.has(x + length)) length++
↑count up while the next one exists
8 best = Math.max(best, length)
9 }
10 }
11 return best
12}
Complexity
TimeO(n)SpaceO(n)
O(n) time: building the set is O(n), and the counting steps add up to O(n) across all runs. O(n) space for the set.
What we learned
A set turns "is this number present?" into O(1), which can beat sorting.
To avoid repeated work, find the natural starting points (here, numbers with no predecessor) and only do the expensive work from those.
When you claim O(n) for nested loops, explain why the inner loop's total work is bounded: here, each number is counted once.