Java Program to Find kth Largest Element

To find the kth largest element in Java, sort the array using Arrays.sort() and then access the element at index array.length - k.

Examples

Input[3, 1, 5, 12, 2, 11], k=3

Output5

Input[10, 20, 30, 40, 50], k=1

Output50

Input[7, 7, 7, 7], k=2

Output7

How to Think About It

To find the kth largest element, first understand that sorting the array puts elements in order. The largest element is at the end. So, the kth largest is at position length minus k. This way, you can directly pick the element without searching.

Algorithm

1

Get the input array and the value k.

2

Sort the array in ascending order.

3

Calculate the index as array length minus k.

4

Return the element at this index.

Code

java

import java.util.Arrays;

public class KthLargest {
    public static int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 5, 12, 2, 11};
        int k = 3;
        System.out.println("The " + k + "rd largest element is " + findKthLargest(arr, k));
    }
}

Output

The 3rd largest element is 5

Dry Run

Let's trace the example array [3, 1, 5, 12, 2, 11] with k=3 through the code.

1

Input array and k

Array: [3, 1, 5, 12, 2, 11], k = 3

2

Sort the array

Sorted array: [1, 2, 3, 5, 11, 12]

3

Calculate index

Index = length - k = 6 - 3 = 3

4

Return element at index

Element at index 3 is 5

Step	Array State	Index Calculated	Element Returned
1	[3, 1, 5, 12, 2, 11]	-	-
2	[1, 2, 3, 5, 11, 12]	-	-
3	[1, 2, 3, 5, 11, 12]	3	-
4	[1, 2, 3, 5, 11, 12]	3	5

Why This Works

Step 1: Sorting the array

Sorting arranges elements from smallest to largest, making it easy to find positions relative to size.

Step 2: Finding the kth largest index

The kth largest element is at index length - k because array indices start at 0.

Step 3: Returning the element

Accessing the element at the calculated index gives the kth largest value directly.

Alternative Approaches

Using a Max-Heap (PriorityQueue)

java

import java.util.PriorityQueue;

public class KthLargestHeap {
    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        for (int num : nums) {
            maxHeap.add(num);
        }
        for (int i = 1; i < k; i++) {
            maxHeap.poll();
        }
        return maxHeap.peek();
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 5, 12, 2, 11};
        int k = 3;
        System.out.println("The " + k + "th largest element is " + findKthLargest(arr, k));
    }
}

This approach uses extra memory for the heap but can be more efficient for large data when k is small.

Using Quickselect Algorithm

java

import java.util.Random;

public class KthLargestQuickselect {
    private static final Random rand = new Random();

    public static int findKthLargest(int[] nums, int k) {
        return quickselect(nums, 0, nums.length - 1, nums.length - k);
    }

    private static int quickselect(int[] nums, int left, int right, int k_smallest) {
        if (left == right) return nums[left];
        int pivotIndex = left + rand.nextInt(right - left + 1);
        pivotIndex = partition(nums, left, right, pivotIndex);
        if (k_smallest == pivotIndex) {
            return nums[k_smallest];
        } else if (k_smallest < pivotIndex) {
            return quickselect(nums, left, pivotIndex - 1, k_smallest);
        } else {
            return quickselect(nums, pivotIndex + 1, right, k_smallest);
        }
    }

    private static int partition(int[] nums, int left, int right, int pivotIndex) {
        int pivot = nums[pivotIndex];
        swap(nums, pivotIndex, right);
        int storeIndex = left;
        for (int i = left; i < right; i++) {
            if (nums[i] < pivot) {
                swap(nums, storeIndex, i);
                storeIndex++;
            }
        }
        swap(nums, right, storeIndex);
        return storeIndex;
    }

    private static void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 5, 12, 2, 11};
        int k = 3;
        System.out.println("The " + k + "th largest element is " + findKthLargest(arr, k));
    }
}

Quickselect is efficient with average O(n) time but is more complex to implement.

Complexity: O(n log n) time, O(1) space

Time Complexity

Sorting the array takes O(n log n) time, which dominates the runtime.

Space Complexity

Sorting in-place uses O(1) extra space, so no significant additional memory is needed.

Which Approach is Fastest?

Sorting is simple but slower for large data; Quickselect offers average O(n) time but is complex; heap approach uses extra space but can be efficient for small k.

Approach	Time	Space	Best For
Sorting	O(n log n)	O(1)	Small to medium arrays, simple code
Max-Heap	O(n + k log n)	O(n)	When k is small and data is large
Quickselect	O(n) average	O(1)	Large arrays needing fast selection