K'th Smallest Element in an Unsorted Array

In this article, we will solve the problem of finding the k'th smallest element in an unsorted array. This means that in an array, we need to find the k'th smallest element. Note that every array element ia unique.

Example:

Input: array = [0, 1, 22, 11, 10, 15], k = 4

Output: 11

The 4th smallest element in the array is 11.

Solution:

To solve this problem, we will use the QuickSelect algorithm, which is an efficient selection algorithm to find the k'th smallest element in an unordered list.

Steps to Solve:

1.    Choose a Pivot:

o   Choose a random element as the pivot.

2.    Partition the Array:

o   Rearrange the array so that all elements less than the pivot come before it and all elements greater than the pivot come after it. The pivot element will be in its final sorted position.

3.    Recursively Apply QuickSelect:

o   If the pivot position is equal to k-1, then the pivot element is the k'th smallest element.

o   If the pivot position is greater than k-1, recursively apply QuickSelect to the left subarray.

o   If the pivot position is less than k-1, recursively apply QuickSelect to the right subarray.

Time Complexity: O(N^2)

Space Complexity: O(1)