Take Kth Largest Element in an Array (LC 215) with nums = [3, 2, 3, 1, 2, 4, 5, 5, 6] and k = 4. There are 9 values, so target = len(nums) - k = 5. Index 5 is where the answer would sit if nums were sorted.

The first random pick is nums[0], so pivot = 3. The three-way partition reads nums[lo..hi] once. Afterwards nums is [2, 1, 2, 3, 3, 5, 5, 6, 4]. Indexes 0 to 2 hold the values smaller than 3, indexes 3 and 4 hold the two copies of 3, and indexes 5 to 8 hold the larger values.

In the sorted array, the three values smaller than 3 come first, and the two copies of 3 follow. So the two copies of 3 sit at indexes 3 and 4 in the sorted array too. The partition placed them correctly without sorting anything else.

Now target = 5 is above gt = 4. The answer is among the larger values, so lo becomes 5. The values at indexes 0 to 4 are never read again. The second random pick is nums[8], so pivot = 4. After the partition, nums[5..5] holds the pivot, and lt = gt = 5 = target. The answer is 4. In the sorted array [1, 2, 2, 3, 3, 4, 5, 5, 6], index 5 holds 4.

A pass over nums[lo..hi] costs one read per value. The next pass works on one side only. If the pivot is close to the middle in rank, the kept side is about half of the values, and the reads add up to about n + n/2 + n/4 + ..., which is about 2n. A random pivot lands in the middle half of the ranks half of the time, so the kept side shrinks by a constant fraction every two passes on average. The total is O(n) on average.

The numbers from a test agree. On a shuffled array of 10000 values with k = 5000, the code read about 34000 values on average over 50 runs, which is about 3.4 times n. Sorting the same array would cost about n log2 n, which is about 133000 comparisons.

The worst case happens when every pivot is the smallest or the largest value of the range. With the fixed pivot nums[hi] on a sorted array and k = n, each pass removes one value. For n = 10000, the code made 10000 passes and read 50005000 values, which is exactly n * (n + 1) / 2. With a random pivot, 20 runs on the same input read about 19700 values on average, about 2n.

Randomness does not remove the worst case. It removes the input that causes it: no fixed array can make the random choices bad every time. A deterministic O(n) worst case exists (the median-of-medians pivot rule), but the constant is large, and interviews rarely ask for it.

The partition has three blocks, not two. A value equal to pivot stays in the middle block, and lt..gt is never empty after a pass, because the pivot itself is in it. The else branch returns as soon as target falls inside nums[lt..gt].

This makes many equal values cheap. For an array of 1000 copies of 7, the first pass puts all of them in the middle block, and the loop returns after 1 pass. A two-way split that sends the equal values to the smaller side leaves the middle block empty, and the loop can never return.

The code changes nums. When it returns, nums[target:] holds the k largest values in any order. In a test of 5000 random arrays, sorted(nums[target:]) equalled the last k values of sorted(original) every time. This is why the trigger says you can also take the k items up to that rank. If the caller needs the original order, copy nums first, which costs O(n) extra space.

The median is the same question. For an odd length, the median is the k-th largest with k = (len(nums) + 1) // 2.

Both answer "which values are the largest". The Top-K Heap costs O(n log k) time and O(k) space, and it works on a stream, because it needs only the next value. Quickselect costs O(n) on average and O(1) extra space, but it needs every value in memory at once and it reorders nums.

For Kth Largest Element in a Stream (LC 703), Quickselect would restart for every new number. For Top K Frequent Elements (LC 347), the values are counts, which are never bigger than len(nums). A pass of buckets does that in O(n) every time, with no random choice.

Choose Quickselect when the array is given once, fits in memory, and you want one rank or the group of values up to that rank.