1094MediumArraySliding Window

Stretches Holding the Top Reading k Times

Tracked in this browser only

Trains the technique from

LeetCode 2962Count Subarrays Where Max Element Appears at Least K Times

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A log holds the readings readings. Let the top reading be the largest reading anywhere in the log.

Return how many stretches of neighbouring readings hold the top reading at least k times.

Examples

Example 1

Input: readings = [2, 2, 2], k = 2
Output: 3

The top reading is two and every reading is one. The stretches holding it at least twice are the two neighbouring pairs and the whole log.

Example 2

Input: readings = [5], k = 1
Output: 1

One reading is itself the top reading, and the single stretch holds it once.

Example 3

Input: readings = [1, 2, 1], k = 2
Output: 0

The top reading is two and the log holds only one of it, so no stretch can hold it twice.

Constraints

1 <= readings.length <= 10^5
1 <= readings[i] <= 10^6
1 <= k <= 10^5

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def count_subarrays(readings: list[int], k: int) -> int:

Java

public long countSubarrays(int[] readings, int k)

The intended approach

Time O(n) over the log's length.Space O(1).

The top reading is settled by one pass over the whole log, since a stretch's own largest reading never enters the question. Then slide a window along. Widening a stretch never lowers how many copies of the top reading it holds, so for each right end the stretches that qualify are exactly those whose left end sits at or before some furthest place. Push the left end in as far as it will go while the window still holds `k` copies, and then every left end from the log's start up to just before the window's left end gives a qualifying stretch, which is exactly the window's left position as a count. Both ends only move rightwards, so each reading is looked at a fixed number of times.

Pythonentry point: count_subarrays

def count_subarrays(readings, k):
    top = readings[0]
    for value in readings:
        if value > top:
            top = value
    total = 0
    seen = 0
    lo = 0
    for hi in range(len(readings)):
        if readings[hi] == top:
            seen += 1
        while seen >= k:
            if readings[lo] == top:
                seen -= 1
            lo += 1
        total += lo
    return total

The obvious version

Take every stretch and count the copies of the top reading inside it as the stretch grows, counting the stretch whenever the tally reaches `k`. Costs the log's length squared rather than one window.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_count_subarrays(readings, k):
    n = len(readings)
    top = readings[0]
    for value in readings:
        if value > top:
            top = value
    total = 0
    for start in range(n):
        seen = 0
        for end in range(start, n):
            if readings[end] == top:
                seen += 1
            if seen >= k:
                total += 1
    return total

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in