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

Hiring now

Get the Apple interview, not just the prep

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Or practice this question first

Next question