Show problems as
Classic problem #128MediumArrayHash TableUnion-Find

Longest Consecutive Sequence

Real-world version: Widest Serviced Floor Band
Tracked in this browser only
Read Longest Consecutive Sequence on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A building automation system writes one entry every time a lift stops to be serviced. floors[i] is the floor number attached to entry i. Floors above ground carry positive numbers, ground is 0, and basement levels carry negative numbers. Entries land in whatever order the technicians filed them, and the same floor may show up several times.

Call a set of floor numbers a band when it has no holes: some floor f, then f + 1, then f + 2, and so on up to some final floor. A band counts as serviced when every floor it contains shows up at least once somewhere in floors. Where those entries sit in the log is irrelevant.

Return how many floors the widest serviced band contains. An empty log services no band at all, so the answer is 0 in that case.

Repeats never widen a band: three entries for floor 4 still only account for one floor.

The log may hold up to a hundred thousand entries, and your routine has to finish in expected linear time with respect to that count. Putting the log in order first is therefore ruled out.

Examples

Example 1

Input
floors = [3, 12, 4, 2, 11, 5]
Output
4

Floors 2, 3, 4 and 5 are all present, which is a band of four floors. Adding 6 would break it because no entry mentions floor 6, and the pair 11 with 12 only reaches two floors.

Example 2

Input
floors = [6, 7, 7, 8, 8, 12]
Output
3

The band 6 through 8 is serviced, so the answer is three. The duplicate entries for 7 and 8 add nothing, and floor 12 stands alone because floors 9 through 11 never appear.

Example 3

Input
floors = [-2, 9, -1, 0, -3]
Output
4

Three basement levels join ground level to form the band -3 through 0, four floors wide. Floor 9 is isolated since neither 8 nor 10 was logged.

Constraints

  • 0 <= floors.length <= 10^5
  • -10^9 <= floors[i] <= 10^9
  • Expected running time is linear in floors.length

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def widest_floor_band(floors: list[int]) -> int:
Java
public int widestFloorBand(int[] floors)

More on the same topics