Java Coding Test Course, Finding the Kth Number in an Array

In this lecture, we will address one of the commonly tested algorithm problems in Java, which is the “Finding the Kth Smallest Number in an Array” problem. This problem involves finding the Kth smallest number in a given array and can be approached in various ways. The ability to solve such types of problems is crucial for employment coding tests, so let’s aim to upgrade our coding skills through this.

Problem Definition

Write a function that finds and returns the Kth smallest number from the given array.

Input:
- Integer array arr: an array of size n (1 ≤ n ≤ 1000)
- Integer K: K is a value between 1 and n inclusive

Output:
- Return the Kth smallest number from the array

Example

For example, if 
arr = [7, 10, 4, 3, 20, 15] and K = 3, 
the answer is 7.

Approach

To solve this problem, several methods can be considered. The most basic approach is as follows.

• Method Using Sorting: Sort the array and return the value at the K-1 index.
• Selection Algorithm (Quickselect): Use the Quickselect algorithm to directly find the Kth number.
• Method Using Heap: Use a min-heap to find the Kth smallest value.

Method 1: Method Using Sorting

The most intuitive method is to sort the array and return the value at the K-1 index. Using one of the sorting algorithms, the time complexity is O(n log n).

public class KthSmallestNumber {
    public static int findKthSmallest(int[] arr, int K) {
        Arrays.sort(arr);
        return arr[K - 1];
    }
    
    public static void main(String[] args) {
        int[] arr = {7, 10, 4, 3, 20, 15};
        int K = 3;
        System.out.println("Kth smallest number: " + findKthSmallest(arr, K));  // 7
    }
}

Method 2: Quickselect Algorithm

The Quickselect algorithm is a method to quickly find the Kth smallest element through a process similar to quicksort. This algorithm has an average performance of O(n).

Quickselect chooses a pivot and partitions the array into smaller and larger values based on the pivot. It then recursively searches in the section where the Kth number should be located.

public class KthSmallestNumber {
    public static int partition(int[] arr, int left, int right, int pivotIndex) {
        int pivotValue = arr[pivotIndex];
        swap(arr, pivotIndex, right);   // Move the pivot to the end of the array
        int storeIndex = left;

        for (int i = left; i < right; i++) {
            if (arr[i] < pivotValue) {
                swap(arr, storeIndex, i);
                storeIndex++;
            }
        }
        swap(arr, storeIndex, right);  // Move the pivot to its final place
        return storeIndex;              // Return the final index of the pivot
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static int quickSelect(int[] arr, int left, int right, int K) {
        if (left == right) {
            return arr[left];  // Only one element left
        }
        
        int pivotIndex = left + (right - left) / 2; 
        pivotIndex = partition(arr, left, right, pivotIndex);
        
        if (K == pivotIndex) {
            return arr[K];
        } else if (K < pivotIndex) {
            return quickSelect(arr, left, pivotIndex - 1, K);
        } else {
            return quickSelect(arr, pivotIndex + 1, right, K);
        }
    }

    public static int findKthSmallest(int[] arr, int K) {
        return quickSelect(arr, 0, arr.length - 1, K - 1);
    }

    public static void main(String[] args) {
        int[] arr = {7, 10, 4, 3, 20, 15};
        int K = 3;
        System.out.println("Kth smallest number: " + findKthSmallest(arr, K));  // 7
    }
}

Method 3: Method Using Min-Heap

A min-heap has the characteristic that the smallest value is always at the root. When the size of the given array is n, we can extract the smallest K elements using a min-heap to find the Kth element. This method has a performance of O(n + k log n).

import java.util.PriorityQueue;

public class KthSmallestNumber {
    public static int findKthSmallest(int[] arr, int K) {
        PriorityQueue minHeap = new PriorityQueue<>();
        
        for (int num : arr) {
            minHeap.offer(num);
        }
        
        int kthSmallest = -1;
        for (int i = 0; i < K; i++) {
            kthSmallest = minHeap.poll();
        }
        
        return kthSmallest;
    }

    public static void main(String[] args) {
        int[] arr = {7, 10, 4, 3, 20, 15};
        int K = 3;
        System.out.println("Kth smallest number: " + findKthSmallest(arr, K));  // 7
    }
}

Conclusion

In this lecture, we explored various algorithmic approaches to the problem of “Finding the Kth Smallest Number in an Array.” We introduced three methods: a simple method using sorting, an efficient method using the Quickselect algorithm, and a method using a min-heap. To cultivate algorithmic problem-solving skills, it is important to experience a variety of problems and understand in which situations each method performs optimally.

By regularly practicing such problems and building your problem-solving patterns and strategies, you can achieve good results in coding tests.

I hope that through more lectures covering algorithm problems and their solutions, your coding skills will advance even further.