Nth Smallest Element in an Unsorted Array

Introduction

Finding the Nth smallest element in an unsorted array is a fundamental problem in computer science, particularly in sorting and searching algorithms. This problem frequently appears in coding interviews and competitive programming. This blog post will explore the best ways to solve it efficiently using Java.

The Context for Nth Smallest Element in an Unsorted Array Algorithm

Finding the Nth smallest element is useful in various applications, including:

• Order statistics in databases and search engines
• Median finding algorithms for statistical analysis
• Optimizing resource allocation in real-time applications

Now, let’s dive into different methods to solve this problem in Java.

Method 1: Nth Smallest Element by Sorting

A simple way to find the N’th smallest element is to sort the array and then access the element at index N-1.

Steps:

1. Sort the array in ascending order.
2. Return the element at the index N-1 (since array indices start from 0).

Java Code:

    @Test
    public void findNthSmallestElementTest() throws Exception {
        int[] array = { 8, 9, 4, 3, 23, 15 };
        int n = 3;
        Arrays.sort(array);
        assertEquals(8, array[n - 1]);
        System.out.println("Nth smallest element: " + array[n - 1]);
    }

Time Complexity:

• O(N log N) due to sorting.
• O(1) space complexity.

Method 2: Nth Smallest Element Using Min-Heap

A more efficient approach involves using a Min-Heap (PriorityQueue in Java), which allows us to extract the K’th smallest element without sorting the entire array.

Steps:

1. Insert all elements into a Min-Heap.
2. Extract the minimum element N times.
3. The K’th extracted element is our answer.

Java Code:

    @Test
    public void findNthSmallestElementMinHeapTest() throws Exception {
        int[] array = { 8, 9, 4, 3, 23, 15 };
        int n = 3;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : array) {
            minHeap.add(num);
        }
        for (int i = 1; i < n; i++) {
            minHeap.poll();
        }   
        int result = minHeap.poll();
        assertEquals(8, result);
        System.out.println("Nth smallest element: " + result);
    }

Time Complexity:

• O(N + K log N), which is better than sorting for large datasets.
• O(N) space complexity due to heap storage.

Method 3: Nth Smallest Element by QuickSelect

QuickSelect is a variation of QuickSort that efficiently finds the Nth smallest element with an average time complexity of O(N).

Steps:

1. Choose a pivot element.
2. Partition the array into elements smaller and larger than the pivot.
3. Recursively call QuickSelect on the appropriate partition.

Java Code:

    private int part(int[] array, int l, int r) {
        int pivot = array[r];
        int i = l;
        for (int j = l; j < r; j++) {
            if (array[j] <= pivot) {
                swapElements(array, i, j);
                i++;
            }
        }
        swapElements(array, i, r);
        return i;
    }

    public int quickSel(int[] array, int l, int r, int n) {
        if (l == r) {
            return array[l];
        }

        int pivotIndex = part(array, l, r);

        if (n - 1 == pivotIndex) {
            return array[pivotIndex];
        } else if (n - 1 < pivotIndex) {
            return quickSel(array, l, pivotIndex - 1, n);
        } else {
            return quickSel(array, pivotIndex + 1, r, n);
        }
    }

    private void swapElements(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    @Test
    public void findNthSmallestElementQuickSelectTest() throws Exception {
        int[] array = { 8, 9, 4, 3, 23, 15 };
        int n = 3;
        int result = quickSel(array, 0, array.length - 1, n);
        assertEquals(8, result);
        System.out.println("Nth smallest element: " + result);
    }

Complexity:

• O(N) average.
• O(N^2) worst case (non-optimal pivot selection).
• O(1) space complexity.

Conclusion

Finding the Nth smallest element in an unsorted array is a crucial problem in data structures and algorithms. We explored three solutions:

• Sorting – Simple but slow for large arrays.
• Min-Heap – Efficient for medium-sized arrays.
• QuickSelect – Best for large datasets with random access.

For small inputs, sorting is acceptable. For large datasets, QuickSelect is optimal due to its expected O(N) complexity.

You can find the example code on Github.