Kth smallest element from an array

Problem Statement

Given an array arr[] and an integer K where K is smaller than the size of the array, the task is to find the K^th smallest element in the given array. It is given that all array elements are distinct.

Input:

N = 6

arr[] = 7 10 4 3 20 15

K = 3

Output: 7

All Solution series of Love Babbar DSA Sheet

Approaches

Approach 1

1. First sort the array in ascending order by using some algorithm like Merge Sort, Quick Sort etc.

2. After iterating over the array up to the kth index ( if using starting index 1).

3. return or print the Kth element.

Time Complexity : 0(n log(n))

Space complexity : O(1) // best possible

But now as we have a lot of space but lack of time we can increase space usage and decrease time usage. Let's see in Approach 2.

Approach 2

1. Create an array b of length maximum possible integer in your array (constraints are always given in these types of problems).

2. Set all the elements of array B to 0(Zero).

3. Now iterate over the array A and for each element of array A set the A[i]th index of B to 1.

4. for example: if (B[i] == 10) B[10] = 1

5. Iterate over array B and iterate till we get the Kth 1(one).

6. Then return or print the index of that one.

Time complexity : O(n)

Space complexity : O(n)

// as we can see here time complexity is decrease form O( n log(n) ) to O(n) but space complexity is increased from O(1) to O(n)

int kthSmallest(int arr[], int l, int r, int k) {
        vector<int> a(100050); // you can use array here
        int n = r+1;
        for( int i = 0 ; i < n ; i++){
            a[arr[i]] = 1;
        }

        int count = 0;
        for( int i = 0; i < 100050; i++){
            if(a[i]){
                count++;
            }if(count == k){
                return i;
            }
        }
    }

I hope that this article will be of assistance to you. Should you have any questions or concerns regarding the content of this article, please do not hesitate to leave a comment below.

I have a question form you please comment. Do you do Competitive programming.

#kth_Smallest_element , #Kth_largets_element #love_babbar_dsa #array #DataStructures