Find The Kth Smallest Largest Element In An Array In Java

In data analysis, competitive programming, and statistics, identifying specific elements within a dataset, such as the k-th smallest or largest value, is a frequent requirement. This article will guide you through various Java approaches to efficiently find the k-th smallest or largest element in an array.

Problem Statement

Given an unsorted array of integers and an integer k, the task is to find the k-th smallest and k-th largest element in that array. The value of k will always be valid, meaning 1 <= k <= array.length. This problem is fundamental in scenarios like finding median values, top performers, or specific percentiles in a dataset, where a full sort might be overkill.

Example

Consider the array [7, 10, 4, 3, 20, 15] and k = 3.

• Sorted array: [3, 4, 7, 10, 15, 20]
• The 3rd smallest element is 7.
• The 3rd largest element is 15.

Background & Knowledge Prerequisites

To understand the solutions presented, a basic understanding of the following Java concepts is helpful:

• Arrays: Fundamental data structures for storing collections of elements.
• Sorting Algorithms: Knowledge of how sorting works (e.g., Arrays.sort()).
• Priority Queues (Heaps): Understanding min-heaps and max-heaps and their use cases.
• Basic Recursion: For the QuickSelect algorithm.
• Time and Space Complexity: To compare the efficiency of different approaches.

Use Cases or Case Studies

Finding the k-th smallest/largest element has several practical applications:

• Ranking and Leaderboards: Identifying the top k scores or bottom k performers in a game or competition without sorting all participants.
• Data Percentiles: Calculating specific percentiles (e.g., the 90th percentile for income or exam scores) which is essentially finding the element at k% position.
• Median Finding: The median of a dataset is a special case of finding the k-th smallest element where k is approximately n/2.
• Resource Allocation: In systems monitoring, identifying the k processes consuming the most memory or CPU.
• Outlier Detection: Finding elements that are significantly larger or smaller than others (e.g., the 5 largest or smallest values).

Solution Approaches

Here are three common approaches to solve this problem, ranging from simple to more optimized.

Approach 1: Sorting the Array

One-line summary: Sort the entire array and then access the element at the k-1 index for the k-th smallest and n-k index for the k-th largest.

// FindKthElementSorting
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {7, 10, 4, 3, 20, 15};
        int k = 3;

        System.out.println("Original Array: " + Arrays.toString(arr));

        // Find Kth Smallest Element
        int[] arrSmallest = Arrays.copyOf(arr, arr.length); // Use a copy to preserve original
        Arrays.sort(arrSmallest);
        // Step 1: Sort the array
        // Step 2: Access the element at index k-1
        int kthSmallest = arrSmallest[k - 1];
        System.out.println(k + "th Smallest Element (via Sorting): " + kthSmallest);

        // Find Kth Largest Element
        int[] arrLargest = Arrays.copyOf(arr, arr.length); // Use a copy
        Arrays.sort(arrLargest);
        // Step 1: Sort the array
        // Step 2: Access the element at index n-k (where n is array length)
        int kthLargest = arrLargest[arrLargest.length - k];
        System.out.println(k + "th Largest Element (via Sorting): " + kthLargest);
    }
}

Run

Sample Output:

Original Array: [7, 10, 4, 3, 20, 15]
3th Smallest Element (via Sorting): 7
3th Largest Element (via Sorting): 15

Stepwise Explanation:

1. Copy Array: Create a copy of the original array to avoid modifying it.
2. Sort: Use Arrays.sort() to sort the array in ascending order. This typically uses a Dual-Pivot Quicksort algorithm, which has an average time complexity of O(N log N).
3. K-th Smallest: The k-th smallest element will be at index k - 1 (since arrays are 0-indexed).
4. K-th Largest: The k-th largest element will be at index array.length - k. For example, if k=1, it's n-1 (the last element).

Approach 2: Using a Min-Heap or Max-Heap (PriorityQueue)

One-line summary: Use a min-heap to find the k-th largest and a max-heap to find the k-th smallest, maintaining only k elements at a time.

// FindKthElementHeap
import java.util.PriorityQueue;
import java.util.Collections; // For reverse order comparator

public class Main {
    public static void main(String[] args) {
        int[] arr = {7, 10, 4, 3, 20, 15};
        int k = 3;

        System.out.println("Original Array: " + Arrays.toString(arr));

        // Find Kth Smallest Element using a Max-Heap
        // A max-heap stores the 'k' largest elements seen so far.
        // The root will be the largest among these 'k', if current element < root, replace.
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int num : arr) {
            maxHeap.offer(num); // Add element
            if (maxHeap.size() > k) {
                maxHeap.poll(); // Remove the largest element if size exceeds k
            }
        }
        // Step 1: Iterate through the array.
        // Step 2: Add each element to a max-heap.
        // Step 3: If heap size exceeds k, remove the largest element (heap's root).
        // Step 4: The root of the max-heap after iteration will be the k-th smallest.
        System.out.println(k + "th Smallest Element (via Max-Heap): " + maxHeap.peek());


        // Find Kth Largest Element using a Min-Heap
        // A min-heap stores the 'k' smallest elements seen so far.
        // The root will be the smallest among these 'k', if current element > root, replace.
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // Default is min-heap
        for (int num : arr) {
            minHeap.offer(num); // Add element
            if (minHeap.size() > k) {
                minHeap.poll(); // Remove the smallest element if size exceeds k
            }
        }
        // Step 1: Iterate through the array.
        // Step 2: Add each element to a min-heap.
        // Step 3: If heap size exceeds k, remove the smallest element (heap's root).
        // Step 4: The root of the min-heap after iteration will be the k-th largest.
        System.out.println(k + "th Largest Element (via Min-Heap): " + minHeap.peek());
    }
}

Run

Sample Output:

Original Array: [7, 10, 4, 3, 20, 15]
3th Smallest Element (via Max-Heap): 7
3th Largest Element (via Min-Heap): 15

Stepwise Explanation:

• For K-th Smallest:

1. Initialize a maxHeap (using Collections.reverseOrder()).
2. Iterate through each number in the array.
3. Add the number to the maxHeap.
4. If the maxHeap size exceeds k, remove the largest element from the heap using poll(). This ensures the heap always contains the k largest elements encountered *so far*.
5. After iterating through all numbers, the top element of the maxHeap (peek()) will be the k-th smallest element overall.

• For K-th Largest:

1. Initialize a minHeap (default PriorityQueue).
2. Iterate through each number in the array.
3. Add the number to the minHeap.
4. If the minHeap size exceeds k, remove the smallest element from the heap using poll(). This ensures the heap always contains the k smallest elements encountered *so far*.
5. After iterating through all numbers, the top element of the minHeap (peek()) will be the k-th largest element overall.

• Complexity: Building the heap takes O(N log K) time (N insertions, each taking log K time). Space complexity is O(K) for storing elements in the heap.

Approach 3: QuickSelect Algorithm

One-line summary: A selection algorithm related to QuickSort that finds the k-th element in average linear time by repeatedly partitioning the array.

// FindKthElementQuickSelect
import java.util.Arrays;
import java.util.Random;

public class Main {

    // Helper method to swap two elements in an array
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // Partition method (similar to QuickSort's partition)
    private static int partition(int[] arr, int low, int high, Random rand) {
        // Choose a random pivot to improve average-case performance
        int pivotIndex = low + rand.nextInt(high - low + 1);
        int pivotValue = arr[pivotIndex];
        swap(arr, pivotIndex, high); // Move pivot to end

        int i = low;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivotValue) {
                swap(arr, i, j);
                i++;
            }
        }
        swap(arr, i, high); // Move pivot to its final sorted position
        return i;
    }

    // QuickSelect algorithm to find the k-th smallest element
    public static int quickSelect(int[] arr, int low, int high, int k, Random rand) {
        if (low == high) {
            return arr[low];
        }

        int pivotIndex = partition(arr, low, high, rand);

        // If pivot is at the k-th position
        if (k == pivotIndex) {
            return arr[k];
        } else if (k < pivotIndex) {
            // Search in the left partition
            return quickSelect(arr, low, pivotIndex - 1, k, rand);
        } else {
            // Search in the right partition
            return quickSelect(arr, pivotIndex + 1, high, k, rand);
        }
    }

    public static void main(String[] args) {
        int[] arr = {7, 10, 4, 3, 20, 15};
        int k = 3; // For 3rd smallest

        System.out.println("Original Array: " + Arrays.toString(arr));

        // Find Kth Smallest Element
        int[] arrSmallest = Arrays.copyOf(arr, arr.length); // Use a copy
        Random rand = new Random();
        // k-th smallest element means element at index k-1 in a 0-indexed sorted array
        int kthSmallest = quickSelect(arrSmallest, 0, arrSmallest.length - 1, k - 1, rand);
        System.out.println(k + "th Smallest Element (via QuickSelect): " + kthSmallest);

        // Find Kth Largest Element
        int[] arrLargest = Arrays.copyOf(arr, arr.length); // Use a copy
        // k-th largest element means element at index arr.length - k in a 0-indexed sorted array
        int kthLargest = quickSelect(arrLargest, 0, arrLargest.length - 1, arrLargest.length - k, rand);
        System.out.println(k + "th Largest Element (via QuickSelect): " + kthLargest);
    }
}

Run

Sample Output:

Original Array: [7, 10, 4, 3, 20, 15]
3th Smallest Element (via QuickSelect): 7
3th Largest Element (via QuickSelect): 15

Stepwise Explanation:

1. Partition Function: This is the core of QuickSelect, identical to QuickSort's partition. It rearranges elements such that all elements smaller than a chosen pivot are to its left, and all larger elements are to its right. It returns the final index of the pivot. Using a random pivot helps prevent worst-case O(N^2) time complexity.
2. QuickSelect Function:

• It takes the array, low and high indices, and the target k (index, not ordinal position) as input.
• It calls partition to place a pivot element in its correct sorted position.
• It then checks the pivot's index:
• If pivotIndex is equal to k, the element at pivotIndex is the desired k-th element, so it's returned.
• If k is less than pivotIndex, the k-th element must be in the left partition, so the algorithm recursively calls itself on the left subarray.
• If k is greater than pivotIndex, the k-th element must be in the right partition, so the algorithm recursively calls itself on the right subarray.
• Complexity: Average time complexity is O(N) because, on average, the search space is halved in each step. Worst-case time complexity is O(N^2) if poor pivots are consistently chosen (mitigated by random pivot selection). Space complexity is O(log N) due to recursion stack (average case) or O(N) (worst case).

Conclusion

Finding the k-th smallest or largest element is a common problem with varying optimal solutions depending on constraints. Sorting the entire array is the simplest but least efficient for large datasets. Using a min/max-heap offers a good balance of performance and readability with O(N log K) time complexity. For scenarios demanding the highest average performance, the QuickSelect algorithm provides an efficient O(N) average-time solution, although its implementation is more complex.

Summary

• Sorting (Arrays.sort()): O(N log N) time, O(1) space (or O(N) if copying). Simple to implement.
• Heap (PriorityQueue): O(N log K) time, O(K) space. Efficient when k is much smaller than N.
• QuickSelect: O(N) average time, O(N^2) worst-case time, O(log N) average space. Most efficient for large N if implemented carefully.

When choosing an approach, consider the size of your array, the relative size of k, and the importance of average-case versus worst-case performance.