Toll plaza minute

A busy minute at a toll plaza fills a whole block of log lines. Finding one line in that block is easy; finding where the block starts and ends is the real question.

The problem

The northbound plaza appends one line per vehicle: the minute-mark, counted from opening time, at which the transponder was read. Lines land in the order cars pass, so stamps is sorted non-decreasing and a busy minute owns a run of consecutive lines.

An auditor picks a minute and wants that run: the index of its first line and of its last. A quiet minute has one line. A minute when the barrier was down has none, and the auditor still expects an answer rather than a crash.

The log holds a hundred thousand lines and the auditor works through thousands of minutes in a sitting, so re-reading it per question is too slow.

Input. stamps — a non-decreasing list of integers, the minute-mark of each logged vehicle. minute — the integer minute-mark being audited.

Output. A list [first, last], the smallest and largest index whose stamp equals minute, or [-1, -1] if no line does.

Example.

stamps = [12, 19, 19, 19, 27, 34], minute = 19   ->  [1, 3]
stamps = [12, 19, 19, 19, 27, 34], minute = 20   ->  [-1, -1]

Minute 19 owns lines 1 through 3. Minute 20 sits between two recorded minutes and owns nothing, so the answer is the sentinel pair, not the gap around it.

A second example, where the block is the whole log:

stamps = [45, 45, 45, 45], minute = 45   ->  [0, 3]

Constraints.

• 0 <= len(stamps) <= 10^5
• 0 <= stamps[i] <= 10^6
• stamps is sorted non-decreasing
• 0 <= minute <= 10^6

Hints

Approach

Brute force

Binary search for any matching line, then walk out to both ends of the run. On a rush-hour log where one minute owns every stamp that walk covers all 10⁵ lines, so 10³ questions cost 10⁸ steps — a linear scan wearing a binary search as a hat.

The insight

Search for a boundary, not for a value: the index of the first stamp that is at least minute is well defined whether or not that minute occurs at all.

Because stamps is sorted, stamps[i] >= minute reads F F F T T T — false while the stamps are early, true forever after. That is the monotone predicate binary search needs, and the answer is the first T. Call it lower(m): the block runs from lower(minute) to lower(minute + 1) - 1, and exists exactly when lower(minute) is a real index holding minute.

Algorithm

1. Write lower(m): binary search over [0, len(stamps)] for the first index with stamps[i] >= m; return len(stamps) if there is none.
2. Let first = lower(minute).
3. If first == len(stamps) or stamps[first] != minute, return [-1, -1].
4. Otherwise return [first, lower(minute + 1) - 1].

Complexity

Time O(log n) — two boundary searches over the log, each halving the range, and no walking. Space O(1); only indices are kept.

Solution

"""Toll plaza minute — twin lower-bound binary searches for a block of equal stamps."""


def lower(stamps, m):
    """First index whose stamp is at least m, or len(stamps) if none is."""
    lo, hi = 0, len(stamps)
    while lo < hi:                        # invariant: the boundary lies in [lo, hi]
        mid = (lo + hi) // 2
        if stamps[mid] >= m:
            hi = mid                      # mid may be the boundary; keep it
        else:
            lo = mid + 1                  # mid is still below m
    return lo


def solve(stamps, minute):
    first = lower(stamps, minute)
    # The boundary exists even when the minute does not, so check before trusting it.
    if first == len(stamps) or stamps[first] != minute:
        return [-1, -1]
    # Everything strictly below minute + 1 and at or above minute is this block.
    return [first, lower(stamps, minute + 1) - 1]

TESTS = [
    (([12, 19, 19, 19, 27, 34], 19), [1, 3]),
    (([12, 19, 19, 19, 27, 34], 20), [-1, -1]),
    (([45, 45, 45, 45], 45), [0, 3]),
    (([], 7), [-1, -1]),
    (([8], 8), [0, 0]),
    (([3, 5, 9], 9), [2, 2]),
    (([3, 5, 9], 1), [-1, -1]),
    (([3, 5, 9], 40), [-1, -1]),
]

Pitfalls

• Expanding outward from a hit. It looks cheap and is O(n) on the exact log the plaza produces at rush hour, when one minute owns every line.
• Skipping the existence check. lower(minute) lands on len(stamps) when the minute is past the last line, and indexing there raises IndexError. When it lands on a larger stamp instead, you report the next minute's block, or — taking [lower(m), lower(m + 1) - 1] on trust — a crossed pair like [4, 3].
• Searching [0, len(stamps) - 1]. The boundary can legitimately be len(stamps), so the top of the range is len(stamps), not the last index. On an empty log the range is [0, 0] and the loop must not run at all.

Variants

• Wrapped flight recorder — the same log search with the order broken in one place.
• Staircase price board — the same reasoning carried into two dimensions.