Array Basics to Advance

Today, we will be finding the Kth Smallest element in the array with two approach, one we all know, and the second one is quite interesting.

Problem Statement

We are given an array, and we need to find the Kth Smallest element in the array.

Examples :

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

Input: arr[] = [2, 3, 1, 20, 15], k = 4 
Output: 15
Explanation: 4th smallest element in the given array is 15

✅ Approach 1: Using In-Built Function

we will sort the array, and will return the element present at k-1 index

int kthSmallest(vector<int> &arr, int k) {
        
        sort(arr.begin(),arr.end());
        return arr[k-1];

Time Complexity: O(n log n)

Space Complexity: O(1)

✅ Approach 2: Use partition method

Get Mayur777’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

In this method we will be selecting one element as pivot element, and place that element in such a way that:

1. Elements present at the left side of the pivot will be less or equal to pivot element
2. Elements present at the right side of the pivot will be greater than pivot element

After that, need to get pivot index of the pivot element, check

1. if pivot index is equal to k-1 (why k-1 ? because, we are using o- based indexing) than that is answer
2. if pivot index is greater than k-1, than our searching area lies to the left sub-array, which is from starting point to pivot index-1
3. if pivot index is less than k-1, than our searching area lies to the right sub-array, so it starts from pivot index+1 to ending point

(starting point = 0 and ending point = size of array — 1

int partition(vector<int> &arr, int low, int high){
          int pivot = arr[high];
          int i = low;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            swap(arr[i], arr[j]);
            i++;
        }
    }
    swap(arr[i], arr[high]);
    return i;
    }
    
    int solve(vector<int> &arr, int low, int high, int k){
      if (low <= high) {
            int pi = partition(arr, low, high);

            if (pi == k - 1) {
                return arr[pi];
            } else if (pi > k - 1) {
                return solve(arr, low, pi - 1, k);
            } else {
                return solve(arr, pi + 1, high, k);
            }
        }
        return -1;
        
    }
    int kthSmallest(vector<int> &arr, int k) {
        // code here
        int low=0,high=arr.size()-1;
        return solve(arr,low,high,k);
    }

The core part of the above code is :
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
swap(arr[i], arr[j]);
i++;
}
}
swap(arr[i], arr[high]);
return i;

We traverse the array using the j pointer, and the i pointer keeps track of the position where the next smaller or equal element should go.

Initially, i points to the start of the array (or sub-array). As we move j from left to right:

• If arr[j] is less than or equal to the pivot, we swap arr[i] and arr[j], and then increment i.
• This ensures that all elements less than or equal to the pivot are moved to the left side of the pivot.

After the loop finishes, we place the pivot element at its correct position by swapping it with arr[i].

This is how:

• The pivot ends up in the right place, and
• All smaller or equal elements are on its left,
• While all greater elements are on its right.

So instead of sorting the entire array, we just partition it and work only on the side where our answer might exist. This makes the algorithm more efficient.