Kth Largest Element

Problem Statement

Write a Java program that uses a priority queue to find the kth largest element in an array of integers. The program should enqueue elements into a min-heap of size k, maintaining the k largest elements, and return the root (smallest of the k largest) as the kth largest element. Test the implementation with at least three different arrays and k values, including edge cases like k=1, k equal to the array length, and arrays with duplicate elements. You can visualize this as sorting through a list of exam scores to find the kth highest score, keeping only the top k scores in a priority queue to efficiently track the kth largest.

Input:

• An array of integers (e.g., [3, 1, 4, 1, 5]).
• An integer k (1 ≤ k ≤ array length). Output: The kth largest element in the array (e.g., for k=2 in [3, 1, 4, 1, 5], output 4). Constraints:
• Array length is between 1 and 10^5.
• Elements are integers in the range [-10^9, 10^9].
• 1 ≤ k ≤ array length.
• Assume k is valid for the input array. Example:
• Input: arr=[3, 1, 4, 1, 5], k=2
• Output: 4
• Explanation: The 2nd largest element is 4 (largest is 5, 2nd is 4).
• Input: arr=[1], k=1
• Output: 1
• Explanation: Only one element, so 1st largest is 1.
• Input: arr=[4, 4, 4], k=2
• Output: 4
• Explanation: All elements are 4, so 2nd largest is 4.

Pseudocode

CLASS MinPriorityQueue
    SET array to new integer array of size capacity
    SET size to 0
    SET capacity to input capacity
    
    FUNCTION enqueue(number)
        IF size equals capacity THEN
            IF number <= array[0] THEN
                RETURN false
            ENDIF
            SET array[0] to number
            CALL siftDown(0)
            RETURN true
        ENDIF
        SET array[size] to number
        CALL siftUp(size)
        INCREMENT size
        RETURN true
    ENDFUNCTION
    
    FUNCTION siftUp(index)
        WHILE index > 0
            SET parent to (index - 1) / 2
            IF array[index] >= array[parent] THEN
                BREAK
            ENDIF
            SWAP array[index] and array[parent]
            SET index to parent
        ENDWHILE
    ENDFUNCTION
    
    FUNCTION siftDown(index)
        SET minIndex to index
        WHILE true
            SET left to 2 * index + 1
            SET right to 2 * index + 2
            IF left < size AND array[left] < array[minIndex] THEN
                SET minIndex to left
            ENDIF
            IF right < size AND array[right] < array[minIndex] THEN
                SET minIndex to right
            ENDIF
            IF minIndex equals index THEN
                BREAK
            ENDIF
            SWAP array[index] and array[minIndex]
            SET index to minIndex
        ENDWHILE
    ENDFUNCTION
    
    FUNCTION peek()
        IF size equals 0 THEN
            RETURN null
        ENDIF
        RETURN array[0]
    ENDFUNCTION
ENDCLASS

FUNCTION findKthLargest(arr, k)
    CREATE queue as new MinPriorityQueue with capacity k
    FOR each number in arr
        CALL queue.enqueue(number)
    ENDFOR
    RETURN queue.peek()
ENDFUNCTION

FUNCTION main()
    SET testCases to array of (array, k) pairs
    FOR each testCase in testCases
        PRINT test case details
        CALL findKthLargest(testCase.arr, testCase.k)
        PRINT kth largest element
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define a MinPriorityQueue class using a min-heap with: a. An array of fixed capacity k, with size to track elements. b. enqueue: If size < k, add to end and sift up; if size = k and number > root, replace root and sift down. c. siftUp: Move smaller number up to maintain min-heap property. d. siftDown: Move larger number down to maintain min-heap property. e. peek: Return root (smallest of k largest elements).
2. In findKthLargest: a. Create a min-heap with capacity k. b. For each number in the array:
   • Enqueue to heap, maintaining k largest elements. c. Return the root (kth largest).
3. In main, test with at least three arrays and k values, including edge cases like k=1, k=length, and duplicates.

Java Implementation

import java.util.*;

public class KthLargestElement {
    // Custom min-heap priority queue implementation
    static class MinPriorityQueue {
        private int[] array;
        private int size;
        private int capacity;

        public MinPriorityQueue(int capacity) {
            this.array = new int[capacity];
            this.size = 0;
            this.capacity = capacity;
        }

        public boolean enqueue(int number) {
            if (size == capacity) {
                if (number <= array[0]) {
                    return false; // Smaller than kth largest
                }
                array[0] = number; // Replace smallest
                siftDown(0);
                return true;
            }
            array[size] = number;
            siftUp(size);
            size++;
            return true;
        }

        private void siftUp(int index) {
            while (index > 0) {
                int parent = (index - 1) / 2;
                if (array[index] >= array[parent]) {
                    break;
                }
                // Swap
                int temp = array[index];
                array[index] = array[parent];
                array[parent] = temp;
                index = parent;
            }
        }

        private void siftDown(int index) {
            int minIndex = index;
            while (true) {
                int left = 2 * index + 1;
                int right = 2 * index + 2;
                if (left < size && array[left] < array[minIndex]) {
                    minIndex = left;
                }
                if (right < size && array[right] < array[minIndex]) {
                    minIndex = right;
                }
                if (minIndex == index) {
                    break;
                }
                // Swap
                int temp = array[index];
                array[index] = array[minIndex];
                array[minIndex] = temp;
                index = minIndex;
            }
        }

        public Integer peek() {
            if (size == 0) {
                return null;
            }
            return array[0];
        }
    }

    // Finds the kth largest element in the array
    public int findKthLargest(int[] arr, int k) {
        MinPriorityQueue queue = new MinPriorityQueue(k);
        for (int num : arr) {
            queue.enqueue(num);
        }
        return queue.peek();
    }

    // Helper class for test cases
    static class TestCase {
        int[] arr;
        int k;

        TestCase(int[] arr, int k) {
            this.arr = arr;
            this.k = k;
        }
    }

    // Main method to test kth largest element
    public static void main(String[] args) {
        KthLargestElement finder = new KthLargestElement();

        // Test cases
        List<TestCase> testCases = new ArrayList<>();
        
        // Test case 1: Normal array
        testCases.add(new TestCase(new int[]{3, 1, 4, 1, 5}, 2));
        
        // Test case 2: Single element
        testCases.add(new TestCase(new int[]{1}, 1));
        
        // Test case 3: Duplicates
        testCases.add(new TestCase(new int[]{4, 4, 4}, 2));
        
        // Test case 4: k equals array length
        testCases.add(new TestCase(new int[]{7, 2, 9, 4, 6}, 5));

        // Run test cases
        for (int i = 0; i < testCases.size(); i++) {
            TestCase test = testCases.get(i);
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Array: " + Arrays.toString(test.arr));
            System.out.println("k: " + test.k);
            int result = finder.findKthLargest(test.arr, test.k);
            System.out.println("Kth largest element: " + result + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Array: [3, 1, 4, 1, 5]
k: 2
Kth largest element: 4

Test case 2:
Array: [1]
k: 1
Kth largest element: 1

Test case 3:
Array: [4, 4, 4]
k: 2
Kth largest element: 4

Test case 4:
Array: [7, 2, 9, 4, 6]
k: 5
Kth largest element: 2

Explanation:

• Test case 1: In [3, 1, 4, 1, 5], k=2, the 2nd largest is 4 (largest is 5).
• Test case 2: In [1], k=1, the 1st largest is 1.
• Test case 3: In [4, 4, 4], k=2, the 2nd largest is 4 (all elements equal).
• Test case 4: In [7, 2, 9, 4, 6], k=5, the 5th largest is 2 (smallest element).

How It Works

• MinPriorityQueue:
  • Uses a min-heap array to maintain the k largest elements, with smallest at root.
  • enqueue: If size < k, adds number and sifts up; if size = k and number > root, replaces root and sifts down.
  • siftUp: Moves smaller number up to maintain min-heap.
  • siftDown: Moves larger number down to maintain min-heap.
  • peek: Returns root (kth largest).
• findKthLargest:
  • Creates a min-heap of size k.
  • Enqueues each array element, keeping only the k largest.
  • Returns the root (kth largest).
• Example Trace (Test case 1):
  • arr=[3, 1, 4, 1, 5], k=2.
  • Enqueue 3: heap=[3], size=1.
  • Enqueue 1: heap=[1,3], size=2.
  • Enqueue 4: heap=[1,3], replace 1 with 4, heap=[3,4], size=2.
  • Enqueue 1: heap=[3,4] (1 < 3, ignored).
  • Enqueue 5: heap=[3,4], replace 3 with 5, heap=[4,5], size=2.
  • Peek: Returns 4 (2nd largest).
• Main Method: Tests normal array, single element, duplicates, and k=length.

Complexity Analysis Table

Note:

• n is the array length, k is the input k.
• Time complexity: O(log k) for each enqueue (heap operations); O(n log k) for n elements.
• Space complexity: O(k) for the min-heap of size k.
• Worst case: O(n log k) time for large n, O(k) space.

✅ Tip: Use a min-heap of size k to efficiently find the kth largest element, as it discards smaller elements early. Test with edge cases like k=1 or k=length to ensure correctness.

⚠ Warning: Ensure k is valid (1 ≤ k ≤ array length) to avoid errors. Handle duplicates carefully, as they may affect the heap’s behavior.