Coding

K-th Largest element in an array

Asked at

Apple

Blinkit

Goldman Sachs

SAP

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an array nums, return the k****th **largest **element in the array.

Input: nums = [1, 2, 3, 4, 5], k = 2 Output: 4

Input: nums = [-5, 4, 1, 2, -3], k = 5 Output: -5

Input: nums = [11, 9, 8, 7, 3, 1], k = 4

1 <= nums.length <= 105
-1000 <= nums[i] <= 1000
1 <= k <= nums.length

cpp

class Solution {
public:
    int kthLargestElement(vector<int>& nums, int k) {

    }
};

java

class Solution {
    public int kthLargestElement(int[] nums, int k) {

    }
}

python

class Solution:
    def kthLargestElement(self, nums, k):

javascript

class Solution {
    kthLargestElement(nums, k) {

    }
}

csharp

public class Solution {
    public int KthLargestElement(int[] nums, int k) {

    }
}

func KthLargestElement(nums []int, k int) int {
	
}

Stuck? Show a way to structure it+

01Clarify that kth largest counts positions including duplicate values.
02Maintain a min-heap containing the k largest elements seen so far.
03Push each value and remove the minimum whenever the heap exceeds size k.
04Return the heap root and discuss quickselect as the average-linear alternative.

Reference answer

Maintain a min-heap of at most k elements. For each number, push it into the heap. If the heap grows beyond k, remove its minimum. After processing the array, the heap contains the k largest elements, and its root is the smallest among them, which is exactly the kth largest value. Duplicates remain separate heap entries, so an input such as [5, 5, 4] with k = 2 correctly returns 5.

The heap solution takes O(n log k) time and O(k) space. It is straightforward, has predictable worst-case behavior, and adapts naturally when values arrive as a stream. Sorting the whole array takes O(n log n) time.

For an in-memory array, quickselect partitions around a pivot and continues only in the side containing the target index n - k. It uses average O(n) time and O(1) auxiliary space when implemented in place, but naive pivot selection has O(n^2) worst-case time and mutates the input. State which trade-off you are choosing rather than presenting complexity in isolation.

Then expect these follow-ups

Which approach would you choose for a stream of numbers?
Tests: trade-off reasoning
How does quickselect locate the kth largest index?
Tests: selection fundamentals

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question