Count the Number of Good Subarrays
Real-world version: Stretches With Enough Matching PairsThe statement here is our own: the same inputs, outputs and technique.
A log holds the readings readings. A matching pair inside a stretch of neighbouring readings is any two positions of that stretch holding the same reading.
A stretch is rich when it holds at least k matching pairs.
Return how many stretches are rich.
Examples
Example 1
- Input
- readings = [3, 1, 4, 3, 2, 2, 4], k = 2
- Output
- 4
Four stretches hold at least two matching pairs. Each of them reaches from somewhere at or before the second reading out to the last, picking up the repeated 3, the repeated 4 and the repeated 2 along the way.
Example 2
- Input
- readings = [1, 1, 1, 1, 1], k = 10
- Output
- 1
Five readings all alike give ten matching pairs, exactly the number wanted, and only the whole log manages it.
Example 3
- Input
- readings = [1, 2, 3], k = 1
- Output
- 0
No two readings are alike, so no stretch holds a matching pair at all.
Constraints
- 1 <= readings.length <= 10^5
- 1 <= readings[i] <= 10^9
- 1 <= k <= 10^9
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.
def count_good(readings: list[int], k: int) -> int:public long countGood(int[] readings, int k)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's