Geeksforgeeks: Kth Smallest

 Kth Smallest

Difficulty: Medium

Given an array arr[] and an integer k where k is smaller than the size of the array, the task is to find the kth smallest element in the given array.

Follow up: Don't solve it using the inbuilt sort function.

Examples :

Input: arr[] = [7, 10, 4, 3, 20, 15], k = 3
Output:  7
Explanation: 3rd smallest element in the given array is 7.

Input: arr[] = [2, 3, 1, 20, 15], k = 4 
Output: 15
Explanation: 4th smallest element in the given array is 15.

Expected Time Complexity: O(n+(max_element) )

Expected Auxiliary Space: O(max_element)

Constraints:
1 <= arr.size <= 106
1<= arr[i] <= 106
1 <= k <= n

To solve the problem of finding the kth smallest element in an array without using built-in sorting functions, we can use a heap-based approach, particularly min-heap or max-heap.

Approach:

1. Min-Heap Approach:

   • We can build a min-heap of size k.
   • Then, for each element in the array:
     • If the heap size is less than k, we push the element into the heap.
     • If the heap size exceeds k, we pop the minimum element from the heap.
   • After processing all elements, the root of the heap will contain the kth smallest element.
   • Time complexity: The heap operations (insert and delete-min) take $O(\log k)$, and we do this for $n$ elements, so the overall time complexity is $O(n \log k)$.

2. Counting Sort Approach (For a restricted range of values):

   • Given the problem constraints, we can also solve this using a counting sort-like approach. We count the frequency of each element and iterate through the frequencies to find the kth smallest.
   • Time complexity: This approach runs in $O(n + M)$, where $M$ is the maximum value in the array. However, this approach may not be feasible if the maximum value in the array is too large.

Solution using Min-Heap Approach in C#:

using System;
using System.Collections.Generic;

public class Solution {
    public int KthSmallest(int[] arr, int k) {
        // Step 1: Create a max-heap with size k
        PriorityQueue<int, int> maxHeap = new PriorityQueue<int, int>();

        // Step 2: Insert first k elements into the heap
        for (int i = 0; i < k; i++) {
            maxHeap.Enqueue(arr[i], -arr[i]);  // We use -arr[i] to simulate max-heap (since PriorityQueue is min-heap by default)
        }

        // Step 3: Process the remaining elements
        for (int i = k; i < arr.Length; i++) {
            if (arr[i] < -maxHeap.Peek()) {  // Compare with the root of the heap
                maxHeap.Dequeue();           // Remove the largest element in the heap
                maxHeap.Enqueue(arr[i], -arr[i]);  // Add the new smaller element
            }
        }

        // Step 4: The root of the heap is the kth smallest element
        return -maxHeap.Peek();
    }
}

// Driver code to test
public class Program {
    public static void Main(string[] args) {
        Solution sol = new Solution();

        int[] arr1 = { 7, 10, 4, 3, 20, 15 };
        int k1 = 3;
        Console.WriteLine("The 3rd smallest element is: " + sol.KthSmallest(arr1, k1));  // Output: 7

        int[] arr2 = { 2, 3, 1, 20, 15 };
        int k2 = 4;
        Console.WriteLine("The 4th smallest element is: " + sol.KthSmallest(arr2, k2));  // Output: 15
    }
}

Explanation:

1. PriorityQueue:

   • A max-heap is implemented using a PriorityQueue in C# (which is a min-heap by default, so we use negative values to simulate the max-heap behavior).

2. First k elements:

   • We add the first k elements to the heap.

3. Remaining elements:

   • For each element from k onwards, we check if it is smaller than the root of the heap (i.e., the largest of the k smallest elements).
   • If so, we remove the largest element from the heap and add the current element to the heap.

4. Result:

   • After processing all elements, the root of the heap will be the kth smallest element.

Time and Space Complexity:

• Time Complexity:
  • Building the heap initially takes $O(k \log k)$.
  • For each of the remaining $n - k$ elements, we perform a heap operation, which takes $O(\log k)$. Therefore, the total time complexity is $O(n \log k)$.
• Space Complexity:
  • The space complexity is $O(k)$, due to the heap storing up to k elements.

Example Walkthrough:

Example 1:

• Input: arr[] = [7, 10, 4, 3, 20, 15], k = 3
• First, we build the heap with the first 3 elements: [7, 10, 4] (max-heap).
• Then we process the remaining elements:
  • For 3: it's smaller than the root (10), so replace 10 with 3. Heap becomes [7, 3, 4].
  • For 20: it's larger than the root (7), so no change.
  • For 15: it's larger than the root (7), so no change.
• The root of the heap is 7, which is the 3rd smallest element.

Example 2:

• Input: arr[] = [2, 3, 1, 20, 15], k = 4
• After building the heap with the first 4 elements: [2, 3, 1, 20].
• Then we process the remaining element 15, and since 15 is smaller than 20, we replace 20 with 15.
• The root of the heap is 15, which is the 4th smallest element.

Conclusion:

This solution efficiently solves the problem of finding the kth smallest element using a max-heap of size k. The time complexity is optimal for the problem, making it suitable for large arrays with constraints up to $10^6$.

For the kth smallest element problem, I've covered the heap-based approach, which is an efficient solution. However, here are a few other approaches that can be considered, along with their time complexities:

1. Sorting Approach (Using Sorting)

• Method: Sort the array in non-decreasing order and pick the element at index k-1.
• Time Complexity: $O(n \log n)$ (due to sorting).
• Space Complexity: $O(1)$ (if sorting in place).

This is the simplest approach but not the most efficient when compared to the heap-based solution.

using System;

public class Solution {
    public int KthSmallest(int[] arr, int k) {
        Array.Sort(arr);
        return arr[k - 1];
    }
}

2. QuickSelect (Partition-based approach)

• Method: Use the QuickSelect algorithm, a variation of QuickSort, to find the kth smallest element. This is more efficient on average than sorting because it doesn't need to fully sort the array.
• Time Complexity: Average case $O(n)$, Worst case $O(n^2)$ (similar to QuickSort).
• Space Complexity: $O(1)$.

QuickSelect works by partitioning the array, much like in QuickSort. Instead of sorting both sides, it continues searching in the side that contains the kth smallest element.

using System;

public class Solution {
    public int KthSmallest(int[] arr, int k) {
        return QuickSelect(arr, 0, arr.Length - 1, k - 1);
    }

    private int QuickSelect(int[] arr, int left, int right, int k) {
        if (left == right) return arr[left];

        int pivotIndex = Partition(arr, left, right);
        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);
    }

    private int Partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int i = left;
        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                Swap(arr, i, j);
                i++;
            }
        }
        Swap(arr, i, right);
        return i;
    }

    private void Swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

3. Heap-based Approach (as explained previously)

• Method: Use a min-heap or max-heap to efficiently find the kth smallest element.
• Time Complexity: $O(n \log k)$ (for inserting elements into the heap).
• Space Complexity: $O(k)$ (for the heap).

As described earlier, we can use a max-heap to track the k smallest elements, and the root of the heap will give us the kth smallest element.

4. Counting Sort (For a Restricted Range)

• Method: Count the frequency of each element in the array and use that to determine the kth smallest element.
• Time Complexity: $O(n + M)$, where $M$ is the maximum value in the array (or range of values).
• Space Complexity: $O(M)$ for storing the count.

This approach works well when the range of elements is small (for example, if the values are integers between 1 and 100). For larger ranges, this approach might not be feasible.

using System;

public class Solution {
    public int KthSmallest(int[] arr, int k) {
        int maxVal = 0;
        foreach (var num in arr) {
            maxVal = Math.Max(maxVal, num);
        }

        int[] count = new int[maxVal + 1];
        foreach (var num in arr) {
            count[num]++;
        }

        int countSoFar = 0;
        for (int i = 0; i <= maxVal; i++) {
            countSoFar += count[i];
            if (countSoFar >= k) {
                return i;
            }
        }

        return -1; // If no such element exists
    }
}

Conclusion:

For each problem, it's good practice to consider multiple approaches and choose the one that best suits the problem's constraints, especially for large datasets:

1. Sorting is simple but slower for large arrays.
2. QuickSelect is more efficient for average cases but has a worst-case time complexity.
3. Heap-based approaches work well when k is small relative to n.
4. Counting Sort is useful when the range of numbers is constrained.