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 LinkedIn.

What role is this question designed for?

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

Find the k-th largest element in an array

Q: Find the k-th largest element in an array

This question evaluates proficiency with selection algorithms, array manipulation, and analysis of time and space complexity, reflecting competency in order-statistics and basic data structures.

Company: LinkedIn

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given an integer array `nums` and an integer `k`, return the **k-th largest** element in the array. Notes: - The k-th largest element is the element that would appear in position `k` (1-indexed) if the array were sorted in **descending** order. - Do **not** fully sort the array unless you want to (but consider performance). ## Input - `nums`: array of integers - `k`: integer (`1 <= k <= len(nums)`) ## Output - The k-th largest integer. ## Constraints - `1 <= len(nums) <= 2 * 10^5` - `-10^9 <= nums[i] <= 10^9`

Quick Answer: This question evaluates proficiency with selection algorithms, array manipulation, and analysis of time and space complexity, reflecting competency in order-statistics and basic data structures.

Given an integer array `nums` and an integer `k`, return the **k-th largest** element in the array. The k-th largest element is the element that would appear in position `k` (1-indexed) if the array were sorted in **descending** order. Note this is the k-th largest element in sorted order, not the k-th distinct element (duplicates count). You are not required to fully sort the array — a heap of size `k` (O(n log k)) or Quickselect (O(n) average) both work and are preferred for large inputs. ### Input - `nums`: array of integers - `k`: integer (`1 <= k <= len(nums)`) ### Output - The k-th largest integer. ### Example 1 ``` Input: nums = [3, 2, 1, 5, 6, 4], k = 2 Output: 5 ``` Descending order is `[6, 5, 4, 3, 2, 1]`; the 2nd element is `5`. ### Example 2 ``` Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4 Output: 4 ``` Descending order is `[6, 5, 5, 4, 3, 3, 2, 2, 1]`; the 4th element is `4` (duplicates count).

Constraints

1 <= len(nums) <= 2 * 10^5
-10^9 <= nums[i] <= 10^9
1 <= k <= len(nums)

Examples

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

Expected Output: 5

Explanation: 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: Descending: [6,5,5,4,3,3,2,2,1]; the 4th element is 4 (duplicates count toward rank).

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 duplicates; every rank is 7.

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

Expected Output: -1

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

Input: ([-10, 0, 10, 5, -5], 3)

Expected Output: 0

Explanation: Descending: [10,5,0,-5,-10]; the 3rd largest is 0.

Input: ([2, 1], 2)

Expected Output: 1

Explanation: k equals array length; the k-th largest is the smallest element, 1.

Hints

You don't 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 size k works well: push elements and pop the smallest whenever the heap exceeds size k. After processing all elements, the heap root is the k-th largest. This is O(n log k).
For optimal average performance, use Quickselect (partition-based selection) to find the element at index (n - k) in ascending order, giving O(n) average time.
Watch the indexing: the k-th LARGEST in descending order equals the element at 0-based index (n - k) when sorted ascending. Duplicates count toward the rank.

Quick Overview

This question evaluates proficiency with selection algorithms, array manipulation, and analysis of time and space complexity, reflecting competency in order-statistics and basic data structures.