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 Onsite 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 kth largest element in array | Meta Coding Question

Quick Overview

A classic Meta software engineer onsite coding question: return the k-th largest element from an unsorted integer array, handling duplicates correctly. It tests order statistics and selection algorithms — sort, size-k min-heap (O(n log k)), and quickselect (O(n) average) — and the candidate's ability to beat a full sort.

Find kth largest element in array

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

##### Question Given an unsorted array of integers `nums` and an integer `k`, return the **k-th largest** element in the array. The 1st largest element is the maximum element, the 2nd largest is the second highest, and so on. Equivalently, the k-th largest element is the value that would appear at index `k - 1` if the array were sorted in **descending** order. **Requirements:** 1. Handle duplicates correctly. Duplicates count as separate positions, e.g. `nums = [5, 5, 4]`, `k = 2` returns `5` (not `4`). 2. Describe your approach and analyze its time and space complexity. Try to design an algorithm that is more efficient than fully sorting the array. (You do not need to provide working code unless asked.) **Input:** - `nums`: an array of integers - `k`: an integer where `1 <= k <= len(nums)` **Output:** - The k-th largest element (an integer). **Constraints (typical interview scale):** - `1 <= n <= 2 * 10^5` - `-10^9 <= nums[i] <= 10^9` **Example:** - `nums = [3, 2, 1, 5, 6, 4]`, `k = 2` -> `5` - `nums = [5, 5, 4]`, `k = 2` -> `5`

Quick Answer: A classic Meta software engineer onsite coding question: return the k-th largest element from an unsorted integer array, handling duplicates correctly. It tests order statistics and selection algorithms — sort, size-k min-heap (O(n log k)), and quickselect (O(n) average) — and the candidate's ability to beat a full sort.

Given an unsorted array of integers `nums` and an integer `k`, return the **k-th largest** element in the array. The 1st largest element is the maximum, the 2nd largest is the second highest, and so on. Equivalently, the k-th largest element is the value at index `k - 1` if the array were sorted in **descending** order. Duplicates count as separate positions. For example, `nums = [5, 5, 4]`, `k = 2` returns `5` (not `4`). Try to design an algorithm more efficient than fully sorting the array. **Input:** - `nums`: an array of integers - `k`: an integer where `1 <= k <= len(nums)` **Output:** - The k-th largest element (an integer). **Example:** - `nums = [3, 2, 1, 5, 6, 4]`, `k = 2` -> `5` - `nums = [5, 5, 4]`, `k = 2` -> `5`

Constraints

1 <= n <= 2 * 10^5
-10^9 <= nums[i] <= 10^9
1 <= k <= len(nums)
Duplicates are counted as separate positions.

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: ([5, 5, 4], 2)

Expected Output: 5

Explanation: Duplicates count separately. Sorted descending: [5,5,4]. The 2nd largest is 5, not 4.

Input: ([1], 1)

Expected Output: 1

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

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

Expected Output: 7

Explanation: All values equal, so the k-th largest is 7 for any valid k.

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

Expected Output: -1

Explanation: All negatives; the largest (1st) is -1.

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

Expected Output: -5

Explanation: k equals n, so this is the minimum, -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.

Input: ([2, 1], 2)

Expected Output: 1

Explanation: k equals n on a 2-element array; the 2nd largest is the minimum, 1.

Input: ([1000000000, -1000000000, 0], 2)

Expected Output: 0

Explanation: Sorted descending: [1e9, 0, -1e9]. The 2nd largest is 0; spans the full value range.

Hints

You do not need the whole array sorted — you only need one order statistic.
A min-heap of size k keeps exactly the k largest elements seen so far; its root is the k-th largest. This runs in O(n log k) and works even for streaming input.
Quickselect (the partition step of quicksort, recursing into only one side) gives O(n) average time in place. Randomize the pivot to avoid the O(n^2) worst case.
Duplicates need no special handling: compare by value and treat equal values as distinct positions. Sorting [5,5,4] descending gives [5,5,4], so the 2nd largest is 5.

Quick Overview