Show problems as
Classic problem #2653MediumArrayHash TableSliding Window

Sliding Subarray Beauty

Real-world version: Drift Marks Over Sensor Blocks
Tracked in this browser only
Read Sliding Subarray Beauty on LeetCode(opens in a new tab)

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

A calibration log holds readings, the drift each sensor sweep measured. A negative reading means the sweep came out below the reference.

Every block of span consecutive readings gets a drift mark, worked out like this. Take the negative readings in the block and put them in increasing order, keeping repeats. If that ordering holds at least rank readings, the block's drift mark is the rank-th reading in it. Otherwise the block's drift mark is 0.

Return the drift marks of every block, in the order the blocks appear from the start of the log to its end.

Examples

Example 1

Input
readings = [-2, 4, -3, -1, 0, -50, 5], span = 3, rank = 2
Output
[-2, -1, -1, -1, 0]

The first block is [-2, 4, -3]; its negative readings in increasing order are -3 and -2, and the second of those is -2. The last block is [0, -50, 5], which holds only one negative reading, so its mark is 0.

Example 2

Input
readings = [-2, -2, -1, -4], span = 3, rank = 2
Output
[-2, -2]

The block [-2, -2, -1] orders its negative readings as -2, -2, -1, and the second of those is -2. The block [-2, -1, -4] orders them as -4, -2, -1, so its mark is -2 as well.

Example 3

Input
readings = [3, 7, 2, 9], span = 2, rank = 1
Output
[0, 0, 0]

No block holds a negative reading, so every mark is 0.

Constraints

  • n == readings.length
  • 1 <= n <= 10^5
  • 1 <= span <= n
  • 1 <= rank <= span
  • -50 <= readings[i] <= 50

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 drift_marks(readings: list[int], span: int, rank: int) -> list[int]:
Java
public int[] driftMarks(int[] readings, int span, int rank)

More on the same topics