1. Introduction

Finding the k’th largest element in an array is a common question which can be approached in multiple ways. A straightforward method is to sort the array in decreasing order and then simply pick the k’th element. However, there are efficient algorithms to find the k’th largest element without sorting the entire array. Here, we will discuss one such approach using a partition method, similar to the QuickSort algorithm.

2. Program Steps

1. Select a ‘pivot’ element from the array and partition the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

2. Compare the size of the sub-array with ‘k’. If the size is equal to k, return the pivot.

3. If the size is greater than k, repeat the process with the left sub-array.

4. If the size is less than k, repeat the process with the right sub-array.

3. Code Program

public class KthLargestElement {

    public static int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return Integer.MAX_VALUE;
        }
        return partition(nums, 0, nums.length - 1, nums.length - k);
    }

    private static int partition(int[] nums, int start, int end, int k) {
        if (start == end) {
            return nums[k];
        }

        int pivot = nums[start];
        int left = start + 1;
        int right = end;

        while (left <= right) {
            while (left <= right && nums[left] <= pivot) {
                left++;
            }
            while (left <= right && nums[right] > pivot) {
                right--;
            }
            if (left <= right) {
                swap(nums, left, right);
            }
        }
        swap(nums, start, right);

        if (k == right) {
            return nums[k];
        } else if (k < right) {
            return partition(nums, start, right - 1, k);
        } else {
            return partition(nums, right + 1, end, k);
        }
    }

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

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

Output:

The 2th largest element is: 5

4. Step By Step Explanation

1. We use a method similar to the partitioning technique of QuickSort.

2. The pivot helps us partition the array into two parts. Elements less than or equal to the pivot are placed to the left, and elements greater than the pivot are placed to the right.

3. Depending on the position of the pivot, we can determine if our required k'th largest element lies on the left or right side of the pivot.

4. The process is recursively applied to the appropriate sub-array until the k'th largest element is found.