Kth Smallest or Largest Efficient Code

In this class, We discuss Kth Smallest or Largest Efficient Code.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of basic coding.

Take our placement training for service-based companies course to improve basic coding Skills. Click Here.

Question:

Given N distinct elements.

Example:

N = 9

[8,9,1,5,11,13,2,28,6]

Given K value. 1 <= K <= N

Identify the Kth smallest element.

Conditions:

Time complexity O(N)

Space complexity O(1)

First Way:

Arrange the elements in ascending order and pick the Kth element.

We need O(nLog(n)) time to sort the elements.

They were asked to solve in O(N) time in the question.

Second Way:

We go with Quick Select with a randomised pivot selection algorithm.

The ‘quick select’ will execute on an average O(N) time with randomised pivot selection.

The ‘quick select’ works exactly similar to the quick sort algorithm.

Randomly pick the pivot element and place the pivot in its exact position.

Suppose the K value is less than the pivot position. We take the left half and repeat the process.

Our design and analysis of algorithms course discussed the quick select efficiency.

The below program for Kth smallest element using quick select.

Program:

import random

def kthSmallest(arr, l, r, k):

   while True:

       x=random.randint(l,r)

       temp=arr[x]

       arr[x]=arr[r]

       arr[r]=temp

       pivot=arr[r];

       c=l

       for i in range(l,r):

           if(arr[i]<pivot):

               temp=arr[c]

               arr[c]=arr[i]

               arr[i]=temp

               c=c+1

       arr[r]=arr[c]

       arr[c]=pivot

       if(c==k-1):

           return pivot

       if(c>k-1):

           r=c-1

       else:

           l=c

n = int(input(“enter number of elements”))

arr=[]

for i in range(n):

   x = int(input())

   arr.append(x)

k = int(input(“enter k value between 1 and n”))

val=kthSmallest(arr,0,n-1,k)

print(val)