How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Find the kth largest element | Meta Coding Question

Find the kth largest element

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given an unsorted array of n integers and an integer k (1 ≤ k ≤ n), return the k-th largest element without fully sorting the array. Design two methods: ( 1) an expected linear-time selection algorithm and ( 2) a heap-based approach. For each, describe the algorithm, analyze time and space complexity, and discuss how you would adapt it to find the k-th largest element in a data stream.

Quick Answer: This question evaluates a candidate's mastery of finding the k-th largest element using selection algorithms and heap data structures, along with algorithmic time and space complexity analysis and techniques for adapting solutions to streaming inputs.

Given an unsorted array of n integers `nums` and an integer `k` (1 ≤ k ≤ n), return the k-th largest element in the array. Note this is the k-th largest element in sorted order, not the k-th distinct element. You should NOT fully sort the array. Two classic approaches solve this in better-than-O(n log n) terms: 1. **Heap-based (implemented here):** maintain a min-heap of size k while scanning the array. After processing every element, the heap holds the k largest values seen so far, and its smallest element (the root) is the k-th largest. Runs in O(n log k) time and O(k) space, and adapts naturally to a streaming setting — just push each new arriving value and pop when the heap exceeds size k; the root is always the running k-th largest. 2. **Quickselect (expected linear time):** partition around a (randomized) pivot and recurse only into the side that contains the target rank. Expected O(n) time, O(1) extra space, but does not extend cleanly to an unbounded stream. Return the value of the k-th largest element.

Constraints

1 ≤ k ≤ n ≤ 10^5
-10^4 ≤ nums[i] ≤ 10^4
The answer is the k-th largest in sorted order, counting duplicates (not the k-th distinct value).

Examples

Input: ([3, 2, 1, 5, 6, 4], 2)

Expected Output: 5

Explanation: Sorted descending: [6, 5, 4, 3, 2, 1]. The 2nd largest is 5.

Input: ([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)

Expected Output: 4

Explanation: Sorted descending: [6, 5, 5, 4, 3, 3, 2, 2, 1]. The 4th largest is 4 (duplicates count).

Input: ([1], 1)

Expected Output: 1

Explanation: Single element; the 1st largest is itself.

Input: ([7, 7, 7, 7], 2)

Expected Output: 7

Explanation: All elements equal; any rank is 7 (duplicates are counted separately).

Input: ([-1, -2, -3, -4, -5], 1)

Expected Output: -1

Explanation: Largest value of all-negative array is -1.

Input: ([-1, -2, -3, -4, -5], 5)

Expected Output: -5

Explanation: k = n boundary: the 5th largest (i.e. the smallest) is -5.

Input: ([2, 1], 2)

Expected Output: 1

Explanation: Sorted descending: [2, 1]. The 2nd largest is 1.

Hints

You do not need to fully sort the array. To find the k-th largest, you only need to track the k largest elements seen so far.
A min-heap of fixed size k is ideal: its smallest element (the root) is exactly the k-th largest once all elements are processed. Pop whenever the heap grows beyond k.
For an expected linear-time approach instead, use Quickselect: randomly pick a pivot, partition, and recurse only into the partition that contains rank n-k.
Streaming adaptation: the min-heap approach works online — push each arriving value, pop when size exceeds k, and the root is always the running k-th largest.

Quick Overview

This question evaluates a candidate's mastery of finding the k-th largest element using selection algorithms and heap data structures, along with algorithmic time and space complexity analysis and techniques for adapting solutions to streaming inputs.