Show problems as
Classic problem #2444HardArrayQueueSliding WindowMonotonic Queue

Count Subarrays With Fixed Bounds

Real-world version: Stretches Pinned to Both Limits
Tracked in this browser only
Read Count Subarrays With Fixed Bounds on LeetCode(opens in a new tab)

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

A rig writes one pressure reading per second into readings.

A stretch is one or more readings that sit next to each other in the log. Two stretches count as different when they begin or end at different positions, even if the readings inside them happen to match.

A stretch is pinned when the smallest reading inside it is exactly low and the largest reading inside it is exactly high.

Return how many pinned stretches the log contains. Nothing guarantees that low is below high.

Examples

Example 1

Input
readings = [2,5,1,6,3,5], low = 1, high = 5
Output
2

The reading 6 at position 3 is above high, so no pinned stretch may contain it. The two that qualify are positions 1 to 2, giving [5,1], and positions 0 to 2, giving [2,5,1]; each has 1 as its smallest reading and 5 as its largest.

Example 2

Input
readings = [4,4,4], low = 4, high = 4
Output
6

Every stretch has 4 as both its smallest and its largest reading, and a log of three readings has six stretches.

Example 3

Input
readings = [3,3], low = 1, high = 3
Output
0

No reading equals 1, so no stretch can have 1 as its smallest reading.

Example 4

Input
readings = [2,3], low = 3, high = 2
Output
0

A stretch would need its smallest reading to be 3 and its largest to be 2, which nothing can satisfy.

Constraints

  • 2 <= readings.length <= 10^5
  • 1 <= readings[i], low, high <= 10^6

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 count_subarrays(readings: list[int], low: int, high: int) -> int:
Java
public long countSubarrays(int[] readings, int low, int high)

More on the same topics