progress

~/problems / Range queries / Sparse table (static RMQ)

Tide gauge: rise and fall between two hours

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

easy ~15 min

A harbour's tide gauge logged the water level once an hour for a year: levels[h] is hour h's reading. Boat owners ask: "between hours a and b, how big was the swing from lowest to highest water?"

Write tide_swings(levels, queries) -> list[int]. For each (a, b) with a <= b, answer max(levels[a..b]) - min(levels[a..b]) (inclusive), in query order.

levels = [120, 180, 240, 210, 130, 60, 90]
tide_swings(levels, [(0, 2), (2, 5), (3, 3), (0, 6)])
# [120, 180, 0, 180]
#  (0,2): 240 - 120    (2,5): 240 - 60    (3,3): one reading    (0,6): 240 - 60

Up to 10**5 readings (integers, possibly negative) and 10**5 queries.

⭐ Bonus: scanning each range still passes; a speed test with 10**5 queries over 10**5 readings earns a star for an O(n log n) build and O(1) per query.

Show hint

two sparse tables, for min and max. For length L, take k = L.bit_length() - 1; the windows [a, a + 2**k) and (b - 2**k, b] overlap but cover a .. b, and overlap doesn't matter for min or max.

Topic: Sparse table (static RMQ). O(n log n) build, O(1) idempotent range queries (min/max/gcd).

0:00
Ctrl ' run · Ctrl ↵ submit
esc