Card 07/ 08
Practice: The Longest Run of Consecutive Raffle Tickets
Nine tickets drawn in no order: find the longest run of numbers that follow one another, then optimise the first answer you would write.
Finding the longest run of consecutive numbers in an unsorted list is a problem whose first answer is slow for two reasons at once, so optimising it takes the whole procedure. A raffle draws nine tickets in this order: 14, 3, 15, 9, 4, 13, 2, 16, 8, all different. The organiser wants the length of the longest run of ticket numbers that follow one another, such as 2, 3, 4, whatever order they were drawn in. Write the first solution that comes to mind, then take it through the six steps: what dominates, what is the best conceivable runtime, what waste is there, which move removes it, and what does the move cost?
Show the answer and a solution
The longest run has 4 tickets, 13 to 16; the others are 2 to 4 and 8 to 9.
- Cost each step: from each ticket, search the list for the next number, and again for the one after; each search is O(n), and a run of length k costs k searches from every ticket in it, so O(n²) or worse.
- Best conceivable runtime: every ticket must be read, O(n).
- Compare: the searches put the solution above O(n).
- Name the waste: a bottleneck in the search, and duplicated work, since the run 13 to 16 is walked again from 14 and 15.
- Standard moves: a hash set makes each search one lookup, and walking only from a ticket whose predecessor is not drawn walks each run once.
- Memory: the set holds n tickets, O(n). Every ticket is looked at a constant number of times, so O(n) on average, which matches step 2: stop.
| Approach | Time | Space | What it removes |
|---|---|---|---|
| Search the list from every ticket | O(n²) or worse | O(1) | Nothing |
| A hash set, walking from every ticket | O(n²) in the worst case | O(n) | The list searches |
| A hash set, walking only from a run's start | O(n) on average | O(n) | The repeated walks |
| Sort, then one scan | O(n log n) | The sort's | The searches, by putting neighbours together |
The listing runs the first three and counts their work.
tickets = [14, 3, 15, 9, 4, 13, 2, 16, 8]
searches = 0
longest = 0
for ticket in tickets:
length = 1
while True:
searches += 1
if ticket + length in tickets:
length += 1
else:
break
longest = max(longest, length)
print(f"search the list: longest {longest}, list searches {searches}")
drawn = set(tickets)
steps = 0
longest = 0
for ticket in tickets:
length = 1
while ticket + length in drawn:
steps += 1
length += 1
longest = max(longest, length)
print(f"hash set, walk from every ticket: longest {longest}, steps walked {steps}")
steps = 0
longest = 0
runs = []
for ticket in tickets:
if ticket - 1 in drawn:
continue
length = 1
while ticket + length in drawn:
steps += 1
length += 1
runs.append((ticket, ticket + length - 1))
longest = max(longest, length)
print(f"hash set, walk only from a start: longest {longest}, steps walked {steps}")
print("runs:", ", ".join(f"{a} to {b}" for a, b in sorted(runs)))search the list: longest 4, list searches 19
hash set, walk from every ticket: longest 4, steps walked 10
hash set, walk only from a start: longest 4, steps walked 6
runs: 2 to 4, 8 to 9, 13 to 16The list searches number 19 against 10 steps for the set walked from every ticket and 6 for the set walked from the starts 2, 8 and 13. The middle version still walks the run 13 to 16 from 13, 14 and 15, which on one run of n tickets is n(n − 1)/2 steps. Sorting is the choice when memory matters more than the log factor.
- Complexity Analysis
- Performance
← → move through sections and cards