Kth Largest Element Using Max Heap in DSA Java

Mental Model

We use a max heap to keep track of the largest elements, removing the largest until we reach the kth largest.

Analogy: Imagine a pile of books stacked by height. You keep removing the tallest book until you find the kth tallest one.

Max Heap Array Representation:
[ 9, 7, 8, 5, 6, 3, 4 ]
Heap structure:
       9
     /   \
    7     8
   / \   / \
  5   6 3   4

Dry Run Walkthrough

Input: array: [3, 2, 1, 5, 6, 4], k = 2

Goal: Find the 2nd largest element in the array using a max heap

Step 1: Build max heap from array

[6, 5, 4, 2, 3, 1]

Why: We need a max heap to quickly access the largest element

Step 2: Remove max element (6) from heap

[5, 3, 4, 2, 1]

Why: Removing the largest element to get closer to the kth largest

Step 3: Peek max element (5) from heap

[5, 3, 4, 2, 1]

Why: After k-1 removals, peeking the root gives the 2nd largest element

Result:

Heap after k-1 removals: [5, 3, 4, 2, 1]
2nd largest element is 5

Annotated Code

DSA Java

import java.util.PriorityQueue;
import java.util.Collections;

public class KthLargestMaxHeap {

    public static int findKthLargest(int[] nums, int k) {
        // Create a max heap using PriorityQueue with reverse order
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        // Add all elements to the max heap
        for (int num : nums) {
            maxHeap.add(num);
        }

        // Remove the largest element k-1 times
        for (int i = 1; i < k; i++) {
            maxHeap.poll(); // remove max
        }

        // The root of the heap is now the kth largest
        return maxHeap.peek();
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        int kthLargest = findKthLargest(nums, k);
        System.out.println("2nd largest element is " + kthLargest);
    }
}

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

Create max heap to access largest elements quickly

for (int num : nums) { maxHeap.add(num); }

Add all numbers to max heap to build heap structure

for (int i = 1; i < k; i++) { maxHeap.poll(); }

Remove largest elements k-1 times to reach kth largest

return maxHeap.peek();

Return current largest which is kth largest element

Output

2nd largest element is 5

Complexity Analysis

Time: O(n log n + k log n) because adding n elements one-by-one takes O(n log n) and removing k elements takes O(k log n)

Space: O(n) because the heap stores all n elements

vs Alternative: Using sorting takes O(n log n), which is slower than heap for large n and small k

Edge Cases

k is 1 (find largest element)

Returns the maximum element without removals

DSA Java

for (int i = 1; i < k; i++) { maxHeap.poll(); }

k equals array length (find smallest element)

Removes all but smallest element, returns smallest

DSA Java

for (int i = 1; i < k; i++) { maxHeap.poll(); }

array with duplicates

Duplicates are handled normally, kth largest may be duplicate

DSA Java

for (int num : nums) { maxHeap.add(num); }

When to Use This Pattern

When asked to find the kth largest element efficiently, use a max heap to remove the largest elements step by step.

Common Mistakes

Mistake: Using a min heap instead of max heap without adjusting logic
Fix: Use a max heap or invert values to maintain correct order

Mistake: Removing k elements instead of k-1 before returning
Fix: Remove k-1 elements so the next is the kth largest

Summary

Finds the kth largest element by building a max heap and removing the largest elements k-1 times.

Use when you want to find the kth largest element without sorting the entire array.

The key insight is that the max heap root always holds the largest element, so removing the top k-1 times reveals the kth largest.

Practice

1. What is the main idea behind finding the kth largest element using a max heap?

easy

A. Build a min heap and extract the min element k times

B. Sort the array and pick the element at index k

C. Build a max heap from the array and extract the max element k times

D. Use a hash map to count frequencies and find the kth largest

Solution

1. Step 1: Build a max heap from the array

   A max heap always keeps the largest element at the root, so building it organizes the data for easy extraction.

2. Step 2: Extract the max element k times

   Each extraction removes the largest element. After k extractions, the last extracted element is the kth largest.

3. Final Answer:

   Build max heap and extract max k times -> Option C

4. Quick Check:

   Max heap extraction = kth largest element [OK]

Hint: Extract max from max heap k times to get kth largest [OK]

Common Mistakes:

• Using min heap instead of max heap
• Sorting and picking wrong index
• Confusing kth largest with kth smallest

2. Which of the following Java code snippets correctly creates a max heap using PriorityQueue?

easy

A. PriorityQueue<Integer> maxHeap = new PriorityQueue<>();

B. PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

C. PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.naturalOrder());

D. PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.nullsFirst());

Solution

1. Step 1: Understand Java PriorityQueue default behavior

   By default, PriorityQueue is a min heap, so PriorityQueue<Integer> maxHeap = new PriorityQueue<>(); creates a min heap.

2. Step 2: Use reverse order comparator for max heap

   PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); uses Collections.reverseOrder() which reverses natural order, creating a max heap.

3. Final Answer:

   PriorityQueue with reverseOrder comparator -> Option B

4. Quick Check:

   Reverse order comparator = max heap [OK]

Hint: Use Collections.reverseOrder() for max heap in Java [OK]

Common Mistakes:

• Assuming default PriorityQueue is max heap
• Using naturalOrder() which is min heap
• Using nullsFirst() which is unrelated

3. What is the output of the following Java code snippet?

int[] arr = {4, 10, 3, 5, 1};
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int num : arr) maxHeap.add(num);

int k = 3;
int kthLargest = 0;
for (int i = 0; i < k; i++) {
    kthLargest = maxHeap.poll();
}
System.out.println(kthLargest);

medium

A. 4

B. 5

C. 10

D. 3

Solution

1. Step 1: Build max heap from array

   The max heap will organize elements as [10, 5, 4, 3, 1] with 10 at root.

2. Step 2: Extract max element 3 times

   First poll: 10, second poll: 5, third poll: 4. The third extracted element is 4.

3. Step 3: Check the printed value

   The code prints the last extracted element, which is 4.

4. Final Answer:

   4 -> Option A

5. Quick Check:

   3rd largest element = 4 [OK]

Hint: Extract max k times; last extracted is kth largest [OK]

Common Mistakes:

• Confusing kth largest with kth smallest
• Off-by-one error in loop
• Printing before extraction

4. Identify the error in the following code that tries to find the 2nd largest element using a max heap:

int[] arr = {7, 2, 9, 4};
PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
for (int num : arr) maxHeap.add(num);

int k = 2;
int kthLargest = 0;
for (int i = 0; i < k; i++) {
    kthLargest = maxHeap.poll();
}
System.out.println(kthLargest);

medium

A. kthLargest should be initialized to Integer.MIN_VALUE

B. The loop should run k+1 times

C. The array should be sorted before adding to heap

D. PriorityQueue should use Collections.reverseOrder() to create max heap

Solution

1. Step 1: Check PriorityQueue initialization

   The code uses default PriorityQueue which is a min heap, not max heap.

2. Step 2: Correct max heap creation

   To find kth largest using max heap, PriorityQueue must be created with Collections.reverseOrder().

3. Final Answer:

   PriorityQueue should use Collections.reverseOrder() to create max heap -> Option D

4. Quick Check:

   Default PriorityQueue = min heap, need reverseOrder for max heap [OK]

Hint: Default PriorityQueue is min heap; add reverseOrder for max heap [OK]

Common Mistakes:

• Not using reverseOrder comparator
• Changing loop count incorrectly
• Sorting array unnecessarily

5. Given an array arr = {12, 3, 5, 7, 19} and k = 4, which of the following code snippets correctly finds the 4th largest element using a max heap in Java?

hard

A. PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int num : arr) maxHeap.add(num);
int kthLargest = 0;
for (int i = 0; i < k; i++) kthLargest = maxHeap.poll();
System.out.println(kthLargest);

B. PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
for (int num : arr) maxHeap.add(num);
int kthLargest = 0;
for (int i = 0; i < k; i++) kthLargest = maxHeap.poll();
System.out.println(kthLargest);

C. PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : arr) {
minHeap.add(num);
if (minHeap.size() > k) minHeap.poll();
}
System.out.println(minHeap.peek());

D. Arrays.sort(arr);
System.out.println(arr[k]);

Solution

1. Step 1: Check each option's approach

   PriorityQueue<Integer> maxHeap = new PriorityQueue<>(); for (int num : arr) maxHeap.add(num); int kthLargest = 0; for (int i = 0; i < k; i++) kthLargest = maxHeap.poll(); System.out.println(kthLargest); uses default min heap, wrong for max heap extraction. PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); for (int num : arr) maxHeap.add(num); int kthLargest = 0; for (int i = 0; i < k; i++) kthLargest = maxHeap.poll(); System.out.println(kthLargest); correctly uses max heap with reverseOrder. PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for (int num : arr) { minHeap.add(num); if (minHeap.size() > k) minHeap.poll(); } System.out.println(minHeap.peek()); uses min heap to keep k largest elements, which finds kth largest but differently. Arrays.sort(arr); System.out.println(arr[k]); prints wrong index after sorting.

2. Step 2: Verify correct kth largest extraction

   PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); for (int num : arr) maxHeap.add(num); int kthLargest = 0; for (int i = 0; i < k; i++) kthLargest = maxHeap.poll(); System.out.println(kthLargest); extracts max element k times from max heap, giving correct 4th largest element.

3. Final Answer:

   Use max heap with reverseOrder and extract k times -> Option A

4. Quick Check:

   Max heap extraction k times = kth largest [OK]

Hint: Use max heap with reverseOrder and extract k times [OK]

Common Mistakes:

• Using min heap without size control
• Incorrect array index after sorting
• Confusing min heap approach with max heap