How should I practice Space-Bounded Kth Largest Element?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Meta phone screen problems in FastPrep.

Is Space-Bounded Kth Largest Element associated with Meta?

FastPrep tags this as a Meta phone screen coding practice problem when the problem catalog has that company and stage context.

Space-Bounded Kth Largest Element

Meta● MediumINTERNPHONE SCREEN

Learn

Problem statement

Given an unordered integer array nums and a one-based rank k, return its kth largest value. Duplicate occurrences occupy separate ranks.

Do not sort the array. Solve the follow-up using a rank-selection heap containing at most ceil(nums.length / 2) values. The supplied array is already in memory; this limit concerns additional selection storage.

Function

findKthLargest(nums: int[], k: int) → int

Examples

Example 1

nums = [3,2,1,5,6,4]k = 2return = 5

Only 6 is larger than 5.

Example 2

nums = [3,2,3,1,2,4,5,5,6]k = 4return = 4

The descending ranks begin 6, 5, 5, 4; equal values occupy separate ranks.

Example 3

nums = [8,-1,3,5,2]k = 5return = -1

For a rank near the end, retaining the smallest values uses less storage.

Constraints

1 <= nums.length <= 100000.
1 <= k <= nums.length.
-1000000000 <= nums[i] <= 1000000000.