Find the k-th Maximum Element in an Array with Java using PriorityQueue DSA

Introduction

Finding the k-th maximum element in an array is a common challenge in data structures and algorithms (DSA) interviews. Whether you're preparing for a coding interview or enhancing your programming skills, mastering this concept can set you apart. In this blog post, we'll explore an efficient way to solve this problem using Java, while ensuring your solution is both optimized and easy to understand.

Understanding the Problem

Before diving into the solution, let’s clarify the problem. Given an array of integers and a number $k$, your goal is to find the k-th maximum element. For example, in the array [5, 8, 4, 9, 1, 10] with $k = 3$, the output should be 8, as it is the third largest unique number.

Why Use a Min-Heap?

Using a min-heap (or a priority queue) is an effective approach to solve this problem. A min-heap allows us to efficiently maintain the top $k$ maximum elements. Here’s why:

• Efficiency: Inserting an element into a min-heap takes $O(\log k)$ time. Thus, for $n$ elements, the overall complexity will be $O(n \log k)$.
• Memory Usage: We only need to store $k$ elements at any time, making it space-efficient.

Step-by-Step Solution

Let’s break down the implementation:

1. Check Edge Cases: First, ensure the array is not empty and that $k$ is valid.
2. Use a PriorityQueue: Initialize a min-heap to store the largest $k$ unique elements.
3. Iterate through the Array: Add elements to the heap and maintain the size.
4. Return the k-th Maximum: The root of the min-heap will be the k-th maximum element.

Java Code Implementation

Here’s the Java code that encapsulates the above logic:

import java.util.PriorityQueue;

import java.util.HashSet;

public class FindKthMaxElementInArray {

public static void main(String[] args) {

int[] arr = {5, 8, 4, 9, 9, 1, 10};

int key = 3;

int kthMax = getKthMaxElement(arr, key);

System.out.println(key + "th Max Element in Array is: " + kthMax);

}

private static int getKthMaxElement(int[] arr, int key) {

if (arr.length == 0 || arr.length < key) {

return -1;

}

PriorityQueue<Integer> q = new PriorityQueue<>();

HashSet<Integer> set = new HashSet<>();

for (int num : arr) {

set.add(num);

}

for (int num : set) {

q.add(num);

if (q.size() > key) {

q.poll();

}

}

return q.peek();

}

}

Conclusion

Finding the k-th maximum element in an array can be achieved efficiently using a min-heap. This approach not only enhances your understanding of data structures but also prepares you for technical interviews. By implementing the code shared above, you can confidently tackle similar problems in your coding journey.

Tags: #k-th maximum element, #Java, data structures, #DSA interview prep, #min-heap, #priority queue, #coding interview, #programming skills.