Kth Largest Element Using Max Heap in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this Java code using a max heap to find the 3rd largest element?

Consider the following Java code snippet that uses a max heap to find the 3rd largest element in an array. What will be printed?

DSA Java

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

public class KthLargest {
    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int num : nums) {
            maxHeap.add(num);
        }
        int result = 0;
        for (int i = 0; i < k; i++) {
            result = maxHeap.poll();
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {4, 1, 7, 3, 8, 5};
        int k = 3;
        System.out.println(findKthLargest(nums, k));
    }
}

A 5

B 4

C 7

D 3

💡 Hint

Remember the max heap orders elements from largest to smallest. Polling k times gives the kth largest.

The max heap orders elements so the largest is first. Polling once gives 8, twice gives 7, and thrice gives 5, which is the 3rd largest element.

🧠 Conceptual

intermediate

Why use a max heap to find the kth largest element?

Which of the following best explains why a max heap is suitable for finding the kth largest element in an unsorted array?

A Because a max heap sorts the entire array in ascending order automatically.

B Because a max heap always keeps the largest element at the root, allowing easy removal of the largest elements.

C Because a max heap stores elements in sorted order internally.

D Because a max heap removes the smallest elements first.

💡 Hint

Think about how the largest elements are accessed in a max heap.

A max heap keeps the largest element at the root, so removing the root repeatedly gives the largest elements in order.

🔧 Debug

advanced

What error does this Java code produce when finding the kth largest element using a max heap?

Identify the error in the following code snippet and what error it will cause when run.

DSA Java

import java.util.PriorityQueue;

public class KthLargest {
    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
        for (int num : nums) {
            maxHeap.add(num);
        }
        int result = 0;
        for (int i = 0; i < k; i++) {
            result = maxHeap.poll();
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {4, 1, 7, 3, 8, 5};
        int k = 3;
        System.out.println(findKthLargest(nums, k));
    }
}

A The code prints the 3rd smallest element instead of the 3rd largest.

B The code throws a NullPointerException because maxHeap is empty.

C The code runs correctly and prints 5.

D The code prints 3 instead of the 3rd largest element.

💡 Hint

Check how the PriorityQueue is initialized and what order it uses by default.

By default, Java's PriorityQueue is a min heap, so polling removes the smallest elements first. This code returns the kth smallest, not kth largest.

📝 Syntax

advanced

Which option correctly creates a max heap in Java to find the kth largest element?

Choose the correct Java code snippet that creates a max heap using PriorityQueue.

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

B PriorityQueue<Integer> maxHeap = new PriorityQueue<>();

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

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

💡 Hint

Look for the correct method to reverse the natural order comparator.

Collections.reverseOrder() returns a comparator that reverses natural order, creating a max heap. Comparator.reverse() does not exist.

🚀 Application

expert

After running this code, what is the state of the max heap?

Given the code below, what is the state of the max heap after inserting all elements but before polling any?

DSA Java

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

public class MaxHeapState {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        int[] nums = {10, 20, 15, 30, 40};
        for (int num : nums) {
            maxHeap.add(num);
        }
        System.out.println(maxHeap);
    }
}

A [20, 10, 15, 30, 40]

B [40, 30, 15, 10, 20]

C [10, 15, 20, 30, 40]

D [40, 30, 20, 15, 10]

💡 Hint

Remember PriorityQueue's toString shows internal heap array order, not sorted order.

The internal array of a max heap after these insertions is [40, 30, 20, 15, 10]. The root is 40, children 30 and 20, then 15 and 10.

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