Kth Largest Element Using Max Heap in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a max heap using PriorityQueue in Java.

DSA Java

PriorityQueue<Integer> maxHeap = new PriorityQueue<>([1]);

Drag options to blanks, or click blank then click option'

Anull

BComparator.naturalOrder()

C() -> 0

DCollections.reverseOrder()

Attempts:

3 left

💡 Hint

Common Mistakes

Using natural order comparator creates a min heap instead of max heap.

Passing null does not create a max heap.

Using Collections.reverseOrder() creates a max heap by reversing the natural order.

2fill in blank

medium

Complete the code to add elements from the array to the max heap.

DSA Java

for (int num : nums) {
    maxHeap.[1](num);
}

Drag options to blanks, or click blank then click option'

Aremove

Bpeek

Coffer

Dpoll

Attempts:

3 left

💡 Hint

Common Mistakes

Using poll() removes elements instead of adding.

Using peek() only views the top element.

The offer() method adds elements to the PriorityQueue (max heap).

3fill in blank

hard

Fix the error in the code to extract the kth largest element from the max heap.

DSA Java

int kthLargest = 0;
for (int i = 0; i < k; i++) {
    kthLargest = maxHeap.[1]();
}

Drag options to blanks, or click blank then click option'

Apoll

Boffer

Cpeek

Dremove

Attempts:

3 left

💡 Hint

Common Mistakes

Using peek() causes an infinite loop or wrong result.

Using offer() or remove() incorrectly.

poll() removes and returns the top element, which is needed to get the kth largest.

4fill in blank

hard

Fill both blanks to complete the method that returns the kth largest element using a max heap.

DSA Java

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> maxHeap = new PriorityQueue[1];
    for (int num : nums) {
        maxHeap[2](num);
    }
    for (int i = 0; i < k - 1; i++) {
        maxHeap.poll();
    }
    return maxHeap.peek();
}

Drag options to blanks, or click blank then click option'

A<>(Collections.reverseOrder())

B.offer

C.add

D<>()

Attempts:

3 left

💡 Hint

Common Mistakes

Not using reverseOrder() causes min heap behavior.

Using add() or offer() both work, but offer() is preferred.

Use PriorityQueue<>(Collections.reverseOrder()) to create max heap and offer() to add elements.

5fill in blank

hard

Fill all three blanks to complete the method that returns the kth largest element by polling k times from the max heap.

DSA Java

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> maxHeap = new PriorityQueue[1];
    for (int num : nums) {
        maxHeap[2](num);
    }
    int result = 0;
    for (int i = 0; i < k; i++) {
        result = maxHeap.[3]();
    }
    return result;
}

Drag options to blanks, or click blank then click option'

A<>(Collections.reverseOrder())

B.offer

C.poll

D<>()

Attempts:

3 left

💡 Hint

Common Mistakes

Using peek() instead of poll() in the loop.

Not using reverseOrder() causes wrong heap behavior.

Create max heap with reverseOrder(), add elements with offer(), and poll() k times to get 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