Top K Frequent Elements
Real-world version: Most Reported Calibration OffsetsThe statement here is our own: the same inputs, outputs and technique.
A field probe emits one signed calibration offset each time it is polled. The array readings holds every offset captured during a single shift, and k is how many of them a technician wants to look at.
Report the k distinct offsets that were emitted the greatest number of times. Those k values may be handed back in whatever order is convenient.
The shift log is filtered before it reaches you so the choice is never ambiguous: any offset left out of the answer was emitted strictly fewer times than any offset placed in it.
Examples
Example 1
- Input
- readings = [4, -2, 4, 4, -2, 7], k = 2
- Output
- [4, -2]
Offset 4 lands three times and offset -2 twice, both ahead of 7 with its single appearance.
Example 2
- Input
- readings = [3, 3, 8, 8, 8, 1, 1, 1, 1, -9], k = 1
- Output
- [1]
Offset 1 was emitted four times, more than 8 at three, 3 at two and -9 at one.
Example 3
- Input
- readings = [10000, -10000, 5, -5], k = 4
- Output
- [10000, -10000, 5, -5]
Nothing repeats and k covers the whole distinct set, so all four offsets are reported.
Constraints
- 1 <= readings.length <= 10^5
- -10^4 <= readings[i] <= 10^4
- 1 <= k <= the count of distinct values in readings
- The set of k answers is guaranteed to be unambiguous
The values you return may be in any order.
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 frequent_offsets(readings: list[int], k: int) -> list[int]:public int[] frequentOffsets(int[] readings, int k)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 8 test cases: 8 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