Kth smallest element (DSA)

Problem Statement:(👈click here for GFG)

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

Note :-  l and r denotes the starting and ending index of the array.

Example 1:

Input:
N = 6
arr[] = 7 10 4 3 20 15
K = 3
Output : 7
Explanation :
3rd smallest element in the given 
array is 7.

Example 2:Input:

N = 5
arr[] = 7 10 4 20 15
K = 4
Output : 15
Explanation :
4th smallest element in the given 
array is 15.

Your Task:
You don't have to read input or print anything. Your task is to complete the function kthSmallest() which takes the array arr[], integers l and r denoting the starting and ending index of the array and an integer K as input and returns the Kth smallest element.
 
 
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(log(n))
Constraints:
1 <= N <= 105
1 <= arr[i] <= 105
1 <= K <= N

Solution:1

class Solution {
  kthSmallest(arr,l,r,k){
    // Sort the array
  arr.sort(function(a, b) {
    return a - b;
  });
  
  // Return the kth smallest element
  return arr[k - 1];
  }
}

Solution:2

class Solution {
  kthSmallest(arr,l,r,k){
    // Sort the array
    arr.sort((a,b) => a - b);
    return arr[k-1];
  }
}

Solution 3:

Here's the solution in JavaScript using the Quickselect algorithm to find the kth smallest 

function kthSmallest(arr, l, r, k) {
    // If k is smaller than number of elements in array
    if (k > 0 && k <= r - l + 1) {
        // Partition the array around last element and get
        // position of pivot element in sorted array
        const pos = partition(arr, l, r);
 
        // If position is same as k
        if (pos - l == k - 1) {
            return arr[pos];
        }
        // If position is more, recur for left subarray
        else if (pos - l > k - 1) {
            return kthSmallest(arr, l, pos - 1, k);
        }
        // Else recur for right subarray
        else {
            return kthSmallest(arr, pos + 1, r, k - pos + l - 1);
        }
    }
    // If k is greater than number of elements in array
    else {
        return -1;
    }
}
 
function partition(arr, l, r) {
    const pivot = arr[r];
    let i = l - 1;
    for (let j = l; j < r; j++) {
        if (arr[j] < pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    [arr[i + 1], arr[r]] = [arr[r], arr[i + 1]];
    return i + 1;
}

// Example usage
const arr = [7, 10, 4, 3, 20, 15];
const k = 3;
const result = kthSmallest(arr, 0, arr.length - 1, k);
console.log(`The ${k}th smallest element in the array is: ${result}`);