Problem Title: Kth Smallest

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 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
l=0 r =5
Output : 7
Explanation : 3rd smallest element in the given array is 7.        

Example 2

Input: 5
arr[] = 7 10 4 20 15
k = 4
l=0 r =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(1)

Constraints

• 1 <= N <= 10^5
• 1 <= arr[i] <= 10^5
• 1 <= K <= N
• l= 0
• r=N-1

Java Code

class Solution{
    public static int kthSmallest(int[] arr, int l, int r, int k) 
    { 
        //Your code here
        Arrays.sort(arr);
        return arr[k-1];
    } 
}        

Explanation

The idea is to sort the array and return the kth element of the array.

1. Sort the array.
2. Return the kth element of the array.

• Time Complexity: O(nlogn)
• Space Complexity: O(1)