Kth Largest Element in an Array

Interview Problem Intermediate Medium Top K Array Heap

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.findKthLargest(nums, k). Return the kth largest value, counting duplicates as separate positions.

Starter code

class Solution:
    def findKthLargest(self, nums, k):
        pass

Test cases

second

{
  "args": [
    [
      3,
      2,
      1,
      5,
      6,
      4
    ],
    2
  ]
}

Expected: 5

Wizard outline

Step 1: Initialize Solution.findKthLargest
Replace the empty starter with the first real state owned by Solution.findKthLargest. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Pass the Second case
Complete the readable core algorithm for one representative Interview case. Maintain a min-heap containing only the largest k values seen so far.
Step 3: Harden the Duplicates boundary
Repair the reviewed boundary and pass the complete submission contract. After each value the heap contains the largest min(k,seen) multiset values. Once all values are processed, its smallest member has exactly k-1 values at least as large ahead of it, so it is kth largest.

Footguns and prerequisites

Using a set incorrectly discards duplicate ranks.
python specific rapid fire

Reviewed references

LeetCode 215 — Kth Largest Element in an Array

Practice prerequisites

Update a Bounded Heap(opens in a new tab)
Update a Bounded Heap isolates after each value, the heap contains the largest min(k, processed_count) values seen so far. That focused state discipline is required when implementing kth largest array as a complete Interview Problem.

Recommended approach and implementation

Push values into a min-heap and pop whenever size exceeds k; the root is then kth largest.

Why it works: After each value the heap contains the largest min(k,seen) multiset values. Once all values are processed, its smallest member has exactly k-1 values at least as large ahead of it, so it is kth largest.

class Solution:
    def findKthLargest(self, nums, k):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        import heapq
        heap = []
        for value in nums:
            heapq.heappush(heap, value)
            if len(heap) > k: heapq.heappop(heap)
        return heap[0]

Similar exercises

Top K Frequent Elements(opens in a new tab)