- What is the kth smallest element problem
- Different approaches to find kth smallest element
- Using sorting, selection, and heap-based approaches
- Quick Select algorithm implementation
- Time and space complexity analysis
Introduction to Kth Smallest Element
The kth smallest element problem asks us to find the element at position k when the array is sorted in ascending order. For example, in the array [7, 10, 4, 3, 20, 15], the 3rd smallest element is 7.
Key characteristics of this problem:
- 1-indexed: k = 1 means the smallest element, k = n means the largest element
- Multiple approaches: Can be solved using sorting, heap, or Quick Select
- Common interview question: Tests understanding of sorting and selection algorithms
- Applications: Used in statistics, order statistics, and data analysis
š” Example: For array [7, 10, 4, 3, 20, 15]:
1st smallest = 3, 2nd smallest = 4, 3rd smallest = 7, 4th smallest = 10, 5th smallest = 15, 6th smallest = 20
C Program to Find Kth Smallest Element
#include <stdio.h>
#include <stdlib.h>
// Function to swap two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Partition function for Quick Select
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Choose last element as pivot
int i = low - 1; // Index of smaller element
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1;
}
// Quick Select function to find kth smallest element
// Note: k is 0-indexed (0 = smallest, n-1 = largest)
int quickSelect(int arr[], int low, int high, int k) {
if (low == high) {
return arr[low];
}
// Partition the array
int pivotIndex = partition(arr, low, high);
// If pivot is at k position, we found our element
if (pivotIndex == k) {
return arr[pivotIndex];
}
// If pivot is greater than k, search left side
else if (pivotIndex > k) {
return quickSelect(arr, low, pivotIndex - 1, k);
}
// If pivot is less than k, search right side
else {
return quickSelect(arr, pivotIndex + 1, high, k);
}
}
// Approach 1: Using Sorting (Simple but O(n log n))
int kthSmallestBySorting(int arr[], int n, int k) {
// Copy array to avoid modifying original
int *temp = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
temp[i] = arr[i];
}
// Sort the array using bubble sort (for simplicity)
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (temp[j] > temp[j + 1]) {
swap(&temp[j], &temp[j + 1]);
}
}
}
int result = temp[k - 1]; // k is 1-indexed
free(temp);
return result;
}
// Approach 2: Using Max Heap (O(n log k))
// Implementation using a simple max heap array
void maxHeapify(int heap[], int size, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size && heap[left] > heap[largest]) {
largest = left;
}
if (right < size && heap[right] > heap[largest]) {
largest = right;
}
if (largest != i) {
swap(&heap[i], &heap[largest]);
maxHeapify(heap, size, largest);
}
}
int kthSmallestUsingHeap(int arr[], int n, int k) {
// Build max heap of first k elements
int *heap = (int *)malloc(k * sizeof(int));
for (int i = 0; i < k; i++) {
heap[i] = arr[i];
}
for (int i = k / 2 - 1; i >= 0; i--) {
maxHeapify(heap, k, i);
}
// For remaining elements, if smaller than heap root, replace
for (int i = k; i < n; i++) {
if (arr[i] < heap[0]) {
heap[0] = arr[i];
maxHeapify(heap, k, 0);
}
}
int result = heap[0];
free(heap);
return result;
}
// Function to print the array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Driver program to test the kth smallest element
int main() {
int arr[] = {7, 10, 4, 3, 20, 15, 8, 1, 6, 12};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3; // Find 3rd smallest element
printf("Array: ");
printArray(arr, n);
printf("k = %d\n\n", k);
// Approach 1: Using Sorting
int result1 = kthSmallestBySorting(arr, n, k);
printf("Using Sorting: %dth smallest element = %d\n", k, result1);
// Approach 2: Using Max Heap
int result2 = kthSmallestUsingHeap(arr, n, k);
printf("Using Max Heap: %dth smallest element = %d\n", k, result2);
// Approach 3: Using Quick Select
// Create a copy for Quick Select (it modifies the array)
int *arrCopy = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
arrCopy[i] = arr[i];
}
int result3 = quickSelect(arrCopy, 0, n - 1, k - 1);
printf("Using Quick Select: %dth smallest element = %d\n", k, result3);
free(arrCopy);
// Test with different k values
printf("\nAll kth smallest elements:\n");
for (int i = 1; i <= n; i++) {
int *copy = (int *)malloc(n * sizeof(int));
for (int j = 0; j < n; j++) {
copy[j] = arr[j];
}
int result = quickSelect(copy, 0, n - 1, i - 1);
printf("%dth smallest = %d\n", i, result);
free(copy);
}
return 0;
}
Sample Output
Array: 7 10 4 3 20 15 8 1 6 12 k = 3 Using Sorting: 3th smallest element = 6 Using Max Heap: 3th smallest element = 6 Using Quick Select: 3th smallest element = 6 All kth smallest elements: 1th smallest = 1 2th smallest = 3 3th smallest = 6 4th smallest = 7 5th smallest = 8 6th smallest = 10 7th smallest = 12 8th smallest = 15 9th smallest = 20 10th smallest = 7
Program Explanation
The program demonstrates three different approaches:
- Using Sorting (O(n log n)):
- Sort the entire array using any sorting algorithm
- Return the element at index k-1
- Simple but not optimal for large arrays
- Using Max Heap (O(n log k)):
- Build a max heap with first k elements
- For each remaining element, if smaller than heap root, replace and heapify
- At the end, the heap root contains the kth smallest element
- More efficient for large n and small k
- Using Quick Select (O(n) average):
- Based on Quick Sort's partitioning algorithm
- Partition the array around a pivot
- If pivot is at position k, we found our element
- Otherwise, search the appropriate half
- Average time complexity O(n)
Step-by-Step Approach for Quick Select
| Step | Action | Explanation |
|---|---|---|
| 1 | Choose Pivot | Select the last element as pivot |
| 2 | Partition | Rearrange array so pivot is in its correct position |
| 3 | Check Position | If pivotIndex == k-1, we found the element |
| 4 | Recurse Left | If pivotIndex > k-1, search left half |
| 5 | Recurse Right | If pivotIndex < k-1, search right half |
Time & Space Complexity
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting | O(n log n) | O(n) - for copying |
| Max Heap | O(n log k) | O(k) - for heap |
| Quick Select | O(n) average, O(nĀ²) worst | O(1) - in-place |
š Recommendation:
- For small arrays: Sorting is simplest and sufficient
- For large n and small k: Max Heap approach is efficient
- For general use: Quick Select is the best choice
š» Practice Exercise
Challenge 1: Modify the program to find the kth largest element instead of kth smallest.
Challenge 2: Implement kth smallest using a Min Heap and compare with Max Heap approach.
Challenge 3: Find the median of an array using Quick Select (median is the n/2-th smallest element).
š Click to Show Solution for Challenge 1
// To find kth largest, find (n-k+1)th smallest
int kthLargest(int arr[], int n, int k) {
// Create copy for Quick Select
int *copy = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
copy[i] = arr[i];
}
// kth largest = (n-k+1)th smallest
int result = quickSelect(copy, 0, n - 1, n - k);
free(copy);
return result;
}
Frequently Asked Questions
1. What is the difference between kth smallest and kth largest?
Kth smallest is the element at position k when sorted ascending. Kth largest is the element at position k when sorted descending, or equivalently, the (n-k+1)th smallest element.
2. Why is Quick Select faster than sorting?
Quick Select only processes one half of the array at each step, resulting in O(n) average time, while sorting requires O(n log n) time to process the entire array.
3. When does Quick Select have O(nĀ²) worst case?
Quick Select has worst-case O(nĀ²) when the pivot always picks the smallest or largest element. This can be avoided by using random pivot selection or the median-of-medians algorithm.
4. Can I use this for arrays with duplicate elements?
Yes, the algorithm works with duplicates. The partition function uses <= comparison, so duplicates are handled correctly.
5. Which approach is best for finding the median?
Quick Select is excellent for finding the median (k = n/2) because it runs in O(n) average time, faster than sorting the entire array.
š” Pro Tip: In coding interviews, Quick Select is the preferred approach for order statistics problems. Always mention that it has O(n) average time complexity!