Problem

Algorithm to find kth largest element from an unsorted array in linear time.

Examples

Example 1:

1
2

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

Solution

Method 1 - Blum Floyd Pratt Rivest Tarjan Algorithm

  1. If the number of elements in an array is large .Divide the array into arrays each with 5 elements ⇨ n/5 arrays.
  2. Compute Median of all arrays of 5 elements. This can be done by sorting each group and taking middle element. This results in time complexity of n/5 * 5log5. (Sorting each group takes 5log5, and we have n/5 arrays)
  3. All the computed medians from each sub-array are then collected into a new, smaller array.
  4. Now, compute median of this array
  5. Use this Median as Pivot in QuickSelect

Median > half of these n/5 group medians. So median > n/10 medians.

Also each median in respective group is greater then half element so in total median is greater then 3n/10 element. (why multiply with 3 ⇨ because median in subgroup will be greater than equal to 3 elements, including ltself.)

So in total median is greater then 3n/10 and lesser then 3n/10 element

Complexity

The overall time complexity of the algorithm can be analyzed as follows:

  • Median calculation within sub-arrays contributes O(n) time.
  • Recursive processing of the median array takes T(n/5) time, which can be further broken down using the Master Theorem for divide-and-conquer recurrences. For constant sub-array size (k), the solution converges to O(n).

Therefore, the total time complexity becomes O(n) + T(n/5) + O(n), which simplifies to O(n) due to the dominant linear term.