Loading page…
Practice problem · medium
A delivery route visits its stops in a fixed order, and every stop belongs to a delivery zone. Zones are numbered, and one route can pass through the same zone more than once.
Each zone's parcels travel in their own cage inside the van, and a van has room for two cages. So one van can serve a run of consecutive stops only if those stops cover at most two zones.
Dispatch wants to give the first van the longest such run on the route. The planners need its length, in stops.
Write longest_two_zone(zones).
zones[i] is the zone number of stop i on the route, in order.Input: zones = [4, 2, 4, 7, 7, 4, 2, 2]
Output: 4| right | Joins | Leaves | Counts after the step | left after | Segment | Length | Best |
|---|---|---|---|---|---|---|---|
| 0 | 4 | none | 4→1 | 0 | 4 | 1 | 1 |
| 1 | 2 | none | 4→1, 2→1 | 0 | 4, 2 | 2 | 2 |
| 2 | 4 | none | 4→2, 2→1 | 0 | 4, 2, 4 | 3 | 3 |
| 3 | 7 | 4, 2 | 4→1, 7→1 | 2 | 4, 7 | 2 | 3 |
| 4 | 7 | none | 4→1, 7→2 | 2 | 4, 7, 7 | 3 | 3 |
| 5 | 4 | none | 4→2, 7→2 | 2 | 4, 7, 7, 4 | 4 | 4 |
| 6 | 2 | 4, 7, 7 | 4→1, 2→1 | 5 | 4, 2 | 2 | 4 |
| 7 | 2 | none | 4→1, 2→2 | 5 | 4, 2, 2 | 3 | 4 |
When zone 7 joins at stop 3, the segment covers three zones. Stops leave from the left until zone 2 has no stop left in it.
Input: zones = [5, 5, 5]
Output: 3Every stop is in one zone, so the whole route fits in one van.
Input: zones = [1, 2, 3, 4]
Output: 2Every stop is in a different zone, so any two neighbouring stops make a longest segment.
1 ≤ zones.length ≤ 10^5 (a long route on the busiest day)1 ≤ zones[i] ≤ 10^4Starting at every stop and extending until a third zone appears is O(n^2) in the worst case. When the whole route covers two zones, that is about 5 × 10^9 steps. Aim for O(n).
The window never needs more than three zone counts at once: two that fit, and the one that has joined last. So the extra space stays O(1).
longest_two_zone · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.