Kth Largest Element Heap DSA Solution - Study Chapter | QuizMaker

Kth Largest Element explained with sorting brute force, optimized size-k min-heap, dry run, edge cases, complexity, and Python, C++, Java code.

Read: 12m
Type: Chapter
Access: Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 12: Heap & Priority Queue

Learning Outcome

After this lesson, you should be able to use a min-heap as a fixed-size filter for the k largest values.

Problem Statement

Given an unsorted array and integer k, return the kth largest element.

Input	Output	Why
`nums = [3,2,1,5,6,4], k = 2`	`5`	The sorted descending order is 6,5,4,3,2,1, so the second largest is 5.

Brute Force Approach

Sort the full array and read index n - k. This is simple but sorts more than needed.

Optimized Approach

Maintain a min-heap of size k. After every push, remove the smallest if the heap is too large, so the heap keeps the k largest values.

Exact Pseudocode

heap = empty min heap
for x in nums:
  push x into heap
  if heap size is greater than k:
    pop smallest
return heap top

Reference Code

import heapq

class Solution:
    def findKthLargest(self, nums, k):
        heap = []
        for x in nums:
            heapq.heappush(heap, x)
            if len(heap) > k:
                heapq.heappop(heap)
        return heap[0]

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> heap;

        for (int x : nums) {
            heap.push(x);
            if (heap.size() > k) heap.pop();
        }

        return heap.top();
    }
};

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();

        for (int x : nums) {
            heap.offer(x);
            if (heap.size() > k) heap.poll();
        }

        return heap.peek();
    }
}

Sample Dry Run

Step	State	Result
Push 3,2	heap keeps [2,3]	size is k
Push 1	pop 1	heap still has 2 largest seen
Push 5,6,4	small values are popped	heap keeps [5,6]
Return top	top is 5	2nd largest

Complexity

Measure	Value	Reason
Time	O(n log k)	Each number performs heap work bounded by heap size k.
Space	O(k)	The heap stores at most k numbers.

Edge Cases

k = 1 returns the maximum value.
Duplicates count as separate elements.
k is assumed valid in the standard problem.

Interview Checklist

Use a min-heap, not a max-heap, for size-k filtering.
Pop only when heap size exceeds k.
Return heap top after all numbers are processed.

FAQs

Why does the heap top become kth largest?

The heap stores the k largest values seen so far, so the smallest among them is the kth largest.

Why not sort?

Sorting is fine but costs O(n log n), while the heap only pays log k per item.

What is the core pattern?

Size-k min-heap.