Top Techniques to Identify the K-th Largest Element

Given an integer array nums and an integer k, return the k-th largest element in the array.

Note that it is the k-th largest element in the sorted order, not the k-th distinct element.

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

Approach 1: Sorting

function findKthLargest(arr: number[], k: number): number {
    // Sort numerically and then reverse
    arr.sort((a, b) => a - b);
    arr.reverse();

    let i = 0;
    let res = arr[0];

    while (i !== k) {
        if (arr[i] < res) {
            res = arr[i];
        }
        i++;
    }

    return res;
}

How It Works

1. Sorting:

   • First, the array is sorted in ascending order.

   • Sorting rearranges all the elements so that the smallest numbers come first and the largest come last.

2. Reversing:

   • After sorting, the array is reversed to make the largest elements come first.

3. Finding the k-th Largest:

   • We then loop through the reversed array to find the k-th largest element. We keep track of the smallest value found during this iteration, which ends up being our desired k-th largest element.

Time Complexity

• Sorting: O(n log n), where n is the number of elements in the array.

• Overall Time Complexity: O(n log n) due to the sorting step being the most time-consuming.

Approach 2: Quickselect Algorithm

function findKthLargest(arr: number[], k: number): number {
    let indexToFind = arr.length - k; //think it like array is sorted or we'll sort 
//but choosing largest k-th element from the right side
//e.g. array of length 6 and k =2 
//first largest => 6-1 = 5 i.e arr.length-1 as we are using 0-based indexing here
    return quickSelect(arr, 0, arr.length - 1, indexToFind);
}

function quickSelect(nums: number[], left: number, right: number, indexToFind: number): number {
   // base condition  // when only 1 element left , return it
     if (left === right) {
        return nums[left];
    }

    let i = left - 1, j = right + 1;
//choose any method to randomize this pivot index
    const pivot = nums[Math.floor((left + right) / 2)];

    while (i < j) {
        do { i++; } while (nums[i] < pivot);
        do { j--; } while (nums[j] > pivot);
       // Swap elements if pointers haven't crossed
        if (i < j) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
        }
    }

    if (j < k) {
         //the indexToFind-th element is in the right partition
        return quickSelect(nums, j + 1, right, indexToFind);
    } else {
 // Otherwise, the indexToFind-th element is in the left partition (or it's at `j`)
        return quickSelect(nums, left, j, indexToFind);
    }
}

How It Works

1. Pivot Selection:

   • Choose a pivot (in this case, the middle element of the current subarray).

2. Partitioning:

   • Reorder the array so that elements less than the pivot are on one side and elements greater are on the other.

3. Recursion:

   • Determine if the k-th largest element is in the left or right partition of the pivot.

   • Recursively apply the Quickselect algorithm to the appropriate partition.

Time Complexity

• Average Case: O(n), where n is the number of elements. This is due to the partitioning step being linear on average.

• Worst Case: O(n^2) in the worst-case scenario, typically when the pivot choices are poor.

Future Approach: Min-Heap

In a future update, I will discuss the min-heap approach, which provides another efficient way to find the k-th largest element by maintaining a heap of size k. This method can offer different performance characteristics and is particularly useful in scenarios where we need to handle large datasets efficiently.

Comment if I have committed any mistake. Let's connect on my socials. I am always open for new opportunities , if I am free :P

Linkedin| Twitter | ShowwCase