Loading page…
Practice problem · medium
A parcel-delivery app numbers every parcel scanned at a hub. The scans arrive in any order, and some parcels are scanned more than once.
A quality report wants the longest streak of consecutive parcel numbers that were all scanned, such as 7, 8, 9 and 10. The streak can be built from the scans in any order.
Write longest_streak(ids).
ids[i] is a scanned parcel number. Numbers can repeat, and they come in any order.v, v + 1, v + 2, ... where every number appears somewhere in ids.0 for an empty list.Input: ids = [100, 4, 200, 1, 3, 2]
Output: 4The trace looks at each distinct number. It starts a streak only where the number before it is missing.
| Number | Number before present? | Action | Streak length |
|---|---|---|---|
| 1 | no (0 is missing) | start: 2, 3, 4 are present, 5 is not | 4 |
| 2 | yes | skip: part of the run from 1 | - |
| 3 | yes | skip | - |
| 4 | yes | skip | - |
| 100 | no (99 is missing) | start: 101 is missing | 1 |
| 200 | no (199 is missing) | start: 201 is missing | 1 |
The set order does not matter, and the table lists the numbers in increasing order. The longest streak is 1, 2, 3, 4, so the answer is 4.
Input: ids = []
Output: 0An empty list has no streak, so the answer is 0.
Input: ids = [7, 7, 7]
Output: 1Duplicates count once. The numbers 7, 7, 7 make a streak of length 1.
0 ≤ ids.length ≤ 100,000 (scans in a day)1 ≤ ids[i] ≤ 10^9 (parcel numbers)Sorting the numbers and walking through them costs about n log n, about 1.7 million steps, which would also pass here. The set solution does the job in n steps, and it is the version interviewers ask for. Without the rule "start only at the beginning of a run", the same walk could repeat the same run many times and cost n × n.
longest_streak · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.