Coding Interview Patterns Module 3 – Arrays and hashing
Sets for consecutive runs
Find the longest run of consecutive numbers in an unsorted list in linear time with a hash set, compare it with sorting, and apply it to dates.
What you will learn
- Find the longest run of consecutive integers in O(n) average time with a hash set
- Explain why the set search stays linear on long runs and on repeated values
- Compare the set search with sorting, including how each treats repeated values
- Apply the method to calendar dates by turning them into day numbers
- Avoid integer overflow at the largest value in Java and C++
Before you start
What you’ll learn · Before you start
What you will learn
- Find the longest run of consecutive integers in O(n) average time with a hash set
- Explain why the set search stays linear on long runs and on repeated values
- Compare the set search with sorting, including how each treats repeated values
- Apply the method to calendar dates by turning them into day numbers
- Avoid integer overflow at the largest value in Java and C++
Before you start
On this page
The longest consecutive run: Whole numbers that follow one another without a gap, such as 101, 102, 103 and 104. They may appear in a list in any order and still form one run. in an unsorted list, such as the four
workout days 101 to 104 hidden in [104, 7, 101, 5, 102, 6, 103, 9], can be found in linear time with a hash set. A
set answers “is this number in the list?” in O(1) on average, so following a run from one number to the next costs
one lookup per step, and with care each number is stepped over only once. Sorting finds the same run in O(n log n), by putting every run side by side. What follows is
an original workout-streak version of longest consecutive sequence, with its limits, and the obvious walk that turns
quadratic on one long run.
The problem: the longest workout streak
The problem
A fitness app stores the days on which a user worked out as day numbers, counted from the day the app launched; days imported from an older app, before the launch, are negative. The list is in no order, and a day appears twice when the user worked out twice that day. Return the length of the longest streak: the most consecutive day numbers that all appear in the list. Limits: 0 to 100,000 day numbers, each between −10⁹ and 10⁹.
[104, 7, 101, 5, 102, 6, 103, 9]gives4: the days 101 to 104.[0, −1, 1, 1, 3, −2]gives4: the days −2 to 1; the second 1 adds nothing.[]gives0.
Three streaks hidden in an unsorted list
Text description of the diagram
The input lists the days 104, 7, 101, 5, 102, 6, 103 and 9 in that order. Grouped by consecutive numbers they form three streaks, one per row; dashed boxes mark the missing days that end a streak:
- 101, 102, 103 and 104: a streak of 4, the longest;
- 5, 6 and 7, then 8 is missing: a streak of 3;
- 9 alone, with 8 and 10 missing: a streak of 1.
The brute force: walk forward from every day
For each day d of the list, walk forward through d + 1, d + 2 and so on while the next day is present, and keep
the longest walk. Checking “present” by scanning the list costs O(n) per step. A set brings each check down to O(1),
but the walks themselves repeat: on one long streak, the walk from every day retraces the rest of the streak.
"""The longest streak of consecutive workout days, by walking forward from every day in the list."""
import random
def longest_streak_walk(days):
"""Returns (length of the longest streak, lookups made). Even with a set for each lookup, it repeats walks."""
present = set(days)
best = lookups = 0
for day in days:
length = 1
while True:
lookups += 1
if day + length not in present:
break
length += 1
best = max(best, length)
return best, lookups
print(longest_streak_walk([104, 7, 101, 5, 102, 6, 103, 9])[0])
print(longest_streak_walk([0, -1, 1, 1, 3, -2])[0])
print(longest_streak_walk([])[0])
# The slowest case: one long streak, shuffled. A walk from the k-th day of the streak repeats every walk after it.
rng = random.Random(4)
for n in (1_000, 2_000, 4_000):
days = list(range(n))
rng.shuffle(days)
best, lookups = longest_streak_walk(days)
print(f"n = {n:,}: streak {best:,}, {lookups:,} lookups")
n = 100_000
print(f"n = {n:,}: {n * (n + 1) // 2:,} lookups")Output
4 4 0 n = 1,000: streak 1,000, 500,500 lookups n = 2,000: streak 2,000, 2,001,000 lookups n = 4,000: streak 4,000, 8,002,000 lookups n = 100,000: 5,000,050,000 lookups
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 walk_every_day.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
On a single shuffled streak of n days, the walks make n(n + 1)/2 lookups: doubling n quadruples them, and at 100,000 days there are about 5 × 10⁹, where a second allows about 10⁷ in Python. Step through the walks on the first example:
The drawing shows the whole scene; its 10 steps are listed below.
Every step as text
- The list. The days are 104, 7, 101, 5, 102, 6, 103 and 9, in that order, and they hide three streaks. Every lookup asks the set whether the next day is present.
- 104. 105 is missing, so the walk from 104 stops at once. 1 lookup.
- 7. 8 is missing. 1 lookup, 2 so far.
- 101. 102, 103 and 104 are present and 105 is not, so this walk measures the whole streak of 4. 4 lookups, 6 so far.
- 5. 6 and 7 are present and 8 is not. 3 lookups, 9 so far.
- 102. This walk retraces 103 and 104, which the walk from 101 already covered. 3 lookups, 12 so far.
- 6. Another walk inside a streak, over 7 again. 2 lookups, 14 so far.
- 103. The walk from 103 checks 104 a third time. 2 lookups, 16 so far.
- 9. 10 is missing. 1 lookup, 17 in all, and the longest walk was 4.
- Why it grows. Only the walks from 101, 5 and 9 measured a whole streak; the other five retraced part of one. On a single streak of n days the walks add up to n(n + 1)/2 lookups.
What to notice
A walk that starts in the middle of a streak measures only part of it, and the walk from the streak’s first day covers that part anyway. Three ways to find the longest streak are in common use:
- Sorting the days puts every streak side by side, so one scan finds the longest, in O(n log n) time.
- A hash set, with a walk started only from days whose previous day is missing, finds it in O(n) average time.
- Union-find joins each day to its neighbours and reports the largest group, which also suits days that arrive one at a time.
Checkpoint
Check: The longest streak of consecutive days · Walking forward from every day · What to notice about walks inside a streak
To practise the streak problem, the walk from every day and the three ways to do better, answer the questions below; they start with your weakest idea.
Practice that adapts to you
Practise this lesson
8 questions about 10 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
Walking only from the first day of a streak Pro: opens with a Pro, Premium or Ultimate pass
In this part:
- A dry run on the first example
- The set search in 14 languages
- Looping over the list, reproduced
- Sorting instead, and the repeated day that breaks it
- Set against sort, measured
- Streaks of calendar dates
- Variants, edge cases and the common bugs
- Variants
- Edge cases and common bugs
- Practice: the longest streak and where it starts
- The longest streak and the day it starts
- Interview questions
- Your hash-set solution for the longest run of consecutive numbers passes small tests but times out on a hidden test of 10⁵ numbers, half of them copies of one value. What is the likely cause, how do you confirm it, and how do you fix it?
- Numbers arrive one at a time, up to 10⁶ of them. After each arrival, report the length of the longest run of consecutive numbers seen so far. What do you keep between arrivals, and what does each arrival cost?
- A fitness app shows each user's longest streak of workout days. It stores workouts as UTC timestamps, and its users travel. How do you turn timestamps into days so that streaks are fair, and what can go wrong?
- Key takeaways
1 diagram · 6 runnable examples (Java, Python) · 1 exercise with sample tests · 3 interview answers · about 31 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Terms in this lesson
- consecutive run
- Whole numbers that follow one another without a gap, such as 101, 102, 103 and 104. They may appear in a list in any order and still form one run.
References
- Built-in types: set types (set, frozenset) (Python Software Foundation)
- datetime: date.toordinal(), date.fromisoformat() and timezone (Python Software Foundation)
- ECMAScript language specification: Set objects (Ecma International (TC39))
- Java SE 25 API: LocalDate.toEpochDay() (Oracle)
- Java SE 25 API: HashSet (Oracle)
- The Java Language Specification, Java SE 25: 15.18.2 Additive operators (+ and -) for numeric types (Oracle)
- std::unordered_set::contains (cppreference.com)
- Working Draft, Programming Languages: C++ (N4950), 7.1 Preamble [expr.pre], paragraph 4 (ISO/IEC JTC1/SC22/WG21)
- The Go Programming Language Specification: map types (The Go Authors)
- tz database: the asia file (Asia/Kolkata) (IANA)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress