Stretches With an Exact Low and High

Hard

A sensor logged its readings into the array readings. You are also given numbers lo and hi. A stretch of readings (a contiguous piece of the array) qualifies if its smallest reading is **exactly** lo and its largest is **exactly** hi. Return the number of qualifying stretches. Stretches at different positions count separately, even if their contents match.

Example 1

readings=[4, 2, 6, 3, 7], lo=2, hi=6 → 4

The stretches [2, 6], [4, 2, 6], [2, 6, 3] and [4, 2, 6, 3] qualify. Any stretch containing 7 fails because its maximum exceeds 6.

Example 2

readings=[3, 3, 3], lo=3, hi=3 → 6

Each of the 6 stretches has minimum and maximum both equal to 3.

Example 3

readings=[5, 1, 5], lo=1, hi=4 → 0

Constraints

2 ≤ len(readings) ≤ 10⁵
1 ≤ readings[i], lo, hi ≤ 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Queue Array Sliding Window Monotonic Queue

Similar problems

Moving Window Maximum Hard A Dark Gap Between Street Lamps Hard Shortest Stretch Reaching a Total Hard Maximum Sum With Short Hops Hard Best Pair of Close Beacons Hard

Input

readings=[4, 2, 6, 3, 7], lo=2, hi=6

Expected

Run checks the first 3 tests in your browser. Submit checks all 118 tests on the server, hidden ones included.