Array Interview Questions

Kth smallest element in an array

Posted Vamsi Sangam

Problem Statement – Given an unsorted array of N elements, find the kth smallest element. kth smallest element is the element at index k if the array were sorted.

Clues –

  • Solution should be O(N) in time and O(1) in space.
  • Can you think of a divide-and-conquer based solution?
  • Can you apply Quicksort’s partitioning logic here?

Solution – This can be done in O(N) time and O(1) space by the Quickselect Algorithm. The Quickselect Algorithm is a very useful divide-and-conquer based algorithm which rearranges the array such that the kth element is the kth smallest element in the array. A step-by-step version of Quickselect is –

  •  Calculate the middle element for the given range.
  • Place all the elements greater than the mid element to its right.
  • Place all the elements lesser than the mid element to its left.
  • If ‘k’ is less than the index of the middle element, then recursively call Quickselect on the left half of the range.
  • If ‘k’ is greater than the index of the middle element, then recursively call Quickselect on the right half of the range.

Code –

C
// Quick Select procedure to search for
// the kth smallest element in O(N) time.
void quickSelect(int arr[], int low, int high, int k)
{
    if (high - low < k) {
        // A single element is 
        // considered to be sorted
        return;
    }
     
    int mid = low + ((high - low) / 2);
     
    // Put the pivot at the last
    int temp = arr[mid];
    arr[mid] = arr[high];
    arr[high] = temp;
     
    int pivot = arr[high];
    int i = low;
    int j = high - 1;
     
    // The partition
    while (j >= i) {
        if (arr[j] < pivot && arr[i] > pivot) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
             
            ++i;
            --j;
        } else if (arr[j] < pivot && arr[i] <= pivot) {
            ++i;
        } else if (arr[j] >= pivot && arr[i] > pivot) {
            --j;
        } else if (arr[j] >= pivot && arr[i] <= pivot) {
            ++i;
            --j;
        }
    }
     
    // Bring the pivot back to its
    // appropriate place
    temp = arr[i];
    arr[i] = arr[high];
    arr[high] = temp;
     
    if (k >= i) {
        quickSelect(arr, i + 1, high, k);
    } else {
        quickSelect(arr, low, i, k);
    }
}

Leave a Reply