Find the kth smallest element in an unsorted array

Example:

Input: [3,2,1,5,6,4] and k = 2
Output: 2

Approach: We can use the quick sort partition approach here using random pivot. As we don't have to sort the whole array, we will just focus on the target array.

Implementation in C#:

        public int FindKthSmallest(int[] arr, int k)

        {

            return this.FindKthSmallest(arr, k, 0, arr.Length - 1);

        }

        private int FindKthSmallest(int[] arr, int k, int start, int end)

        {

            if (k > 0 && k <= end - start + 1)

            {

                int pos = this.RandomPartition(arr, start, end);

                if (pos - start == k - 1)

                {

                    return arr[pos];

                }

                if (pos - start > k - 1)

                {

                    return this.FindKthSmallest(arr, k, start, pos - 1);

                }

                return this.FindKthSmallest(arr, k - pos + start - 1, pos + 1, end);

            }

            return int.MaxValue;

        }

        private int RandomPartition(int[] arr, int start, int end)

        {

            int pivot = new Random().Next(start, end);

            arr.SwapElements(pivot, end);

            return this.Partition(arr, start, end);

        }

        

        private int Partition(int[] arr, int start, int end)

        {

            int x = arr[end], i = start;

            for (int j = start; j <= end - 1; ++j)

            {

                if (arr[j] <= x)

                {

                    arr.SwapElements(i, j);

                    ++i;

                }

            }

            arr.SwapElements(i, end);

            return i;

        }

Hint: We can similarly find the kth largest element here by making changes while comparing or we can call FindKthSmallest(arr, arr.Length - k + 1, 0, arr.Length - 1).

Complexity: O(n)