The problem
Given a list of whole numbers in any order, return the length of the longest run of consecutive numbers among them. A run is a set of numbers like 4, 5, 6, 7, where each is one more than the one before.
longest_run([100, 4, 200, 1, 3, 2]) # 4 (1, 2, 3, 4)
longest_run([1, 2, 2, 3]) # 3 (repeats once)
longest_run([]) # 0
Sorting would make this easy, but it costs O(n log n). Do it in O(n) on average. sorted() and .sort() are switched off.
Limits
- Up to 200,000 numbers.
Builds on HASH-5 Inside dict and set and HASH-6 Counting and grouping.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
9 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Classic | Not run | |
| 2 | Empty | Not run | |
| 3 | One number | Not run | |
| 4 | Repeats | Not run | |
| 5 | Negative numbers | Not run | |
| 6 | Two runs | Not run | |
| 7 | No two in a row | Not run | |
| 8 | 200,000 in one run | Not run | |
| 9 | 200,000 scattered | Not run |