Kth Largest Element in an Array
Real-world version: Kth Highest Daily SwingThe statement here is our own: the same inputs, outputs and technique.
A rooftop weather station writes down how far the temperature moved from one day to the next. swings[i] is the figure recorded on day i in whole degrees, and it runs negative on a day that cooled off.
Line the recorded figures up from highest to lowest and return the figure standing at position k of that line, where position 1 is the highest.
Two days that recorded the same figure each take a place of their own in the line, so a repeated figure occupies several consecutive positions. If four days all recorded 5, then positions 1 through 4 of the line every one of them hold 5. Read the request as a position in that full line, not as a rank among the different figures the station saw: it is the k-th figure counting downward with repeats intact, and asking for the k-th value that differs from the ones above it gives a different, wrong answer.
Arranging the entire log just to read one position off it is more work than the question needs.
Examples
Example 1
- Input
- swings = [6, -2, 6, 1, -5, 9], k = 3
- Output
- 6
Highest to lowest the line reads 9, 6, 6, 1, -2, -5. Position 3 holds the second of the two sixes.
Example 2
- Input
- swings = [5, 5, 5, 2], k = 2
- Output
- 5
Three fives fill positions 1, 2 and 3, so position 2 holds 5. Only two figures ever appeared, and treating the request as a rank among them would wrongly report 2.
Example 3
- Input
- swings = [-7], k = 1
- Output
- -7
A one-day log leaves a line of length one, and its only entry answers every legal request.
Constraints
- 1 <= k <= swings.length <= 10^5
- -10^4 <= swings[i] <= 10^4
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 kth_highest_swing(swings: list[int], k: int) -> int:public int kthHighestSwing(int[] swings, int k)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 12 test cases: 12 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