0018MediumArrayDivide and ConquerSortingHeap (Priority Queue)Quickselect

Kth Highest Daily Swing

Tracked in this browser only

Trains the technique from

LeetCode 215Kth Largest Element in an Array

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 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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def kth_highest_swing(swings: list[int], k: int) -> int:

Java

public int kthHighestSwing(int[] swings, int k)

The intended approach

Time O(n) expected, O(n^2) worst caseSpace O(n)

Position `k` from the top is the index `len(swings) - k` once the figures run low to high, so only that one index has to be settled. Pick a random figure as a splitter and rearrange the working range into three blocks, below it, equal to it and above it; the block boundaries reveal exactly which positions the splitter occupies. If the wanted index lands in the equal block the splitter is the answer, otherwise the search continues in the single block that can still contain it. Handling ties as their own block keeps heavily repeated logs from degrading the split.

Pythonentry point: kth_highest_swing

def kth_highest_swing(swings, k):
    import random
    vals = list(swings)
    wanted = len(vals) - k
    low, high = 0, len(vals) - 1
    picker = random.Random(20240517)
    while low < high:
        splitter = vals[picker.randint(low, high)]
        below, cursor, above = low, low, high
        while cursor <= above:
            if vals[cursor] < splitter:
                vals[below], vals[cursor] = vals[cursor], vals[below]
                below += 1
                cursor += 1
            elif vals[cursor] > splitter:
                vals[cursor], vals[above] = vals[above], vals[cursor]
                above -= 1
            else:
                cursor += 1
        if wanted < below:
            high = below - 1
        elif wanted > above:
            low = above + 1
        else:
            return splitter
    return vals[low]

The obvious version

Order the whole log from highest to lowest and index straight into position k, O(n log n).

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_kth_highest_swing(swings, k):
    ordered = sorted(swings, reverse=True)
    return ordered[k - 1]

How this problem was checked

Reference solution executed against 12 test cases — 12 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