ArrayProblem 3 of 36
Find the Kth max and min element of an array
Problem Statement
Given an array of integers and a number K, find the Kth smallest and Kth largest element 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 (ignoring recursion stack)
Approach 2: Using Min-Heap and Max-Heap
Intuition
Use a max-heap of size K for Kth smallest, and a min-heap of size K for Kth largest.
Algorithm
- For Kth smallest: Build a max-heap of first K elements, then for remaining elements, if smaller than heap top, replace and heapify
- For Kth largest: Build a min-heap of first K elements, then for remaining elements, if larger than heap top, replace and heapify
java
import java.util.PriorityQueue;
import java.util.Collections;
public class Solution {
public int kthSmallest(int[] arr, int 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) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : arr) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
}Complexity Analysis
- Time Complexity: O(n log k) - Each insertion/deletion in heap is O(log k)
- 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 pivot and partition the array
- If pivot index == k-1, return pivot
- 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[] arrCopy = arr.clone();
int kthSmallest = quickSelect(arr, 0, n - 1, k - 1);
int kthLargest = quickSelect(arrCopy, 0, n - 1, n - k);
return new int[]{kthSmallest, kthLargest};
}
}Complexity Analysis
- Time Complexity: O(n) average, O(n²) worst case - With randomization, worst case is rare
- Space Complexity: O(1) - In-place partitioning (O(log n) for recursion stack)
Key Takeaways
- Sorting is the simplest approach but not optimal for single queries
- Heap-based approach is useful when K is small relative to N
- QuickSelect provides O(n) average time complexity - best for single queries
- Randomized pivot selection helps avoid worst-case scenarios
- For multiple queries, sorting once O(n log n) may be better than multiple QuickSelects