Longest Harmonious Subsequence
Real-world version: Widest One-Degree SampleThe statement here is our own: the same inputs, outputs and technique.
A cold-store probe logs whole-degree temperatures into the list readings. Values may be below zero.
A technician wants to pull out a sample: any collection of readings taken from the log, chosen freely and without regard to where they sat in the log. A sample is tight when the difference between its largest and its smallest reading is exactly one degree.
Return the number of readings in the largest tight sample. If no tight sample exists, return 0.
Examples
Example 1
- Input
- readings = [-1, 0, 0, -1, 3]
- Output
- 4
Taking both readings of -1 and both readings of 0 gives a sample of four whose smallest is -1 and whose largest is 0, one degree apart.
Example 2
- Input
- readings = [4, 4, 5, 5, 5, 6]
- Output
- 5
The two 4s together with the three 5s make a sample of five running from 4 to 5. Adding the 6 as well would stretch the spread to two degrees.
Example 3
- Input
- readings = [12, 14, 10]
- Output
- 0
No two of these readings differ by exactly one degree, so no tight sample can be formed and the answer is 0.
Constraints
- 1 <= readings.length <= 2 * 10^4
- -10^9 <= readings[i] <= 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 longest_paired_sample(readings: list[int]) -> int:public int longestPairedSample(int[] readings)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 10 test cases: 10 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