Find Kth Smallest or Largest element in an Array.

Objective: Find Kth Smallest or Largest element in an Array

Example:

int[] arrA = { 2, 3, 11, 16, 27, 4, 15, 9, 8 };
Output: The 4th smallest element is : 8

Approach:

Naive Approach: Use Sorting

Sort the array and return kth element. Time Complexity – O(nlogn).

Better Approach: Use Quick Sort Technique

Here we are finding the kth smallest element in array. Same approach you can apply to find the kth largest element.

  • In this technique we select a pivot element and after a one round of operation the pivot element takes its correct place in the array.
  • Once that is done we check if the pivot element is the kth element in array, if yes then return it.
  • But if pivot element is less than the kth element, that clearly means that the kth element is on the right side of the pivot. So make a recursive call from pivot+1 to end.
  • Similarly if pivot element is greater than the kth element, that clearly means that the kth element is on the left side of the pivot. So make a recursive call from start to pivot-1.

Average Time Complexity : O(n)

NOTE: Instead of printing the kth element, you can print all elements from index 0 to k and this will the solution of the problemPrint First K smallest or largest elements in an array”.

Complete Code:

Output:

The 4th smallest element is : 8

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

  • dheeraj singhal

    after line swap(arrA, pivot, right), element at index ‘right’ will be at correct position not element at pivot index.
    Code need little modification as mentioned below.

    if (right == k)
    return arrA[right];
    else if (right < k)
    return kSmall(arrA, right + 1, end, k);
    else
    return kSmall(arrA, start, right – 1, k);

%d bloggers like this: