HeapProblem 5 of 18
Kth smallest and largest element in an unsorted array
Problem Statement
Given an unsorted array and a number K, find the Kth smallest and Kth largest elements in the array.
Example:
- Input:
arr = [7, 10, 4, 3, 20, 15],k = 3 - Output:
Kth Smallest = 7, Kth Largest = 10 - Explanation: Sorted array is
[3, 4, 7, 10, 15, 20]. 3rd smallest is 7, 3rd largest is 10.
Approach 1: Sorting (Brute Force)
Intuition
Sort the array and directly access the Kth element from both ends.
Algorithm
- Sort the array in ascending order
- Kth smallest element is at index K-1
- Kth largest element is at index n-K
java
import java.util.Arrays;
public class Solution {
public int[] kthSmallestLargest(int[] arr, int k) {
int n = arr.length;
if (k > n || k <= 0) return new int[]{-1, -1};
Arrays.sort(arr);
int kthSmallest = arr[k - 1];
int kthLargest = arr[n - k];
return new int[]{kthSmallest, kthLargest};
}
}Complexity Analysis
- Time Complexity: O(n log n) - Due to sorting
- Space Complexity: O(1) - In-place sorting
Approach 2: Using Heaps
Intuition
For Kth smallest, use a max-heap of size K. For Kth largest, use a min-heap of size K. The top of each heap gives the answer.
Algorithm
- Kth Smallest: Build max-heap with K elements, replace top if current element is smaller
- Kth Largest: Build min-heap with K elements, replace top if current element is larger
- Top of heap is the answer
java
import java.util.PriorityQueue;
import java.util.Collections;
public class Solution {
public int kthSmallest(int[] arr, int k) {
// Max-heap of size k
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int num : arr) {
maxHeap.offer(num);
if (maxHeap.size() > k) {
maxHeap.poll();
}
}
return maxHeap.peek();
}
public int kthLargest(int[] arr, int k) {
// Min-heap of size k
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : arr) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
public int[] kthSmallestLargest(int[] arr, int k) {
return new int[]{kthSmallest(arr, k), kthLargest(arr, k)};
}
}Complexity Analysis
- Time Complexity: O(n log k) - Each of n elements involves O(log k) heap operation
- Space Complexity: O(k) - Heap stores k elements
Approach 3: QuickSelect (Optimal)
Intuition
Use the partitioning logic of QuickSort. After partitioning, the pivot is at its correct sorted position. If pivot index equals K-1, we found our answer.
Algorithm
- Choose a random pivot and partition the array
- If pivot index == k-1, return pivot element
- If pivot index > k-1, search in left part
- If pivot index < k-1, search in right part
java
import java.util.Random;
public class Solution {
private Random rand = new Random();
private int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
private int randomPartition(int[] arr, int low, int high) {
int randomIndex = low + rand.nextInt(high - low + 1);
int temp = arr[randomIndex];
arr[randomIndex] = arr[high];
arr[high] = temp;
return partition(arr, low, high);
}
private int quickSelect(int[] arr, int low, int high, int k) {
if (low <= high) {
int pivotIndex = randomPartition(arr, low, high);
if (pivotIndex == k) {
return arr[pivotIndex];
} else if (pivotIndex > k) {
return quickSelect(arr, low, pivotIndex - 1, k);
} else {
return quickSelect(arr, pivotIndex + 1, high, k);
}
}
return -1;
}
public int[] kthSmallestLargest(int[] arr, int k) {
int n = arr.length;
int[] arr1 = arr.clone();
int[] arr2 = arr.clone();
int kthSmallest = quickSelect(arr1, 0, n - 1, k - 1);
int kthLargest = quickSelect(arr2, 0, n - 1, n - k);
return new int[]{kthSmallest, kthLargest};
}
}Complexity Analysis
- Time Complexity: O(n) average, O(n²) worst case
- Space Complexity: O(1) in-place (O(log n) for recursion stack)
Approach 4: Median of Medians (Guaranteed Linear)
Intuition
Choose pivot using median of medians to guarantee O(n) worst-case time complexity.
Algorithm
- Divide array into groups of 5
- Find median of each group
- Recursively find median of medians
- Use this as pivot for partitioning
java
import java.util.Arrays;
public class Solution {
private int findMedian(int[] arr, int start, int end) {
Arrays.sort(arr, start, end + 1);
return arr[start + (end - start) / 2];
}
public int kthSmallest(int[] arr, int k) {
// Simplified implementation using QuickSelect with random pivot
// Full median-of-medians implementation is complex
return quickSelect(arr.clone(), 0, arr.length - 1, k - 1);
}
private int quickSelect(int[] arr, int low, int high, int k) {
if (low == high) return arr[low];
int pivotIdx = partition(arr, low, high);
if (pivotIdx == k) return arr[pivotIdx];
else if (pivotIdx > k) return quickSelect(arr, low, pivotIdx - 1, k);
else return quickSelect(arr, pivotIdx + 1, high, k);
}
private int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
}Complexity Analysis
- Time Complexity: O(n) - Guaranteed linear time
- Space Complexity: O(log n) - Recursion stack
Key Takeaways
- Sorting is O(n log n) - simple but not optimal
- Heap approach is O(n log k) - good when k is small
- QuickSelect is O(n) average - best practical choice
- Median of Medians guarantees O(n) worst case but has high constants
- Kth largest = (n-k+1)th smallest
- Random pivot selection makes worst case unlikely in QuickSelect
- For multiple queries, sorting once may be better than multiple QuickSelects