Kth Smallest

Given an array arr[] and an integer k where k is smaller than the size of the array, the task is to find the k^th smallest element in the given array. It is given that all array elements are distinct.

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[] = [7, 10, 4, 20, 15], k = 4 
Output:  15
Explanation: 4th smallest element in the given array is 15.

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

Approach 01:

#include <vector>
#include <algorithm>

class Solution {
public:
    // array : given array of integers
    // k : find the k-th smallest element in the array
    int kthSmallest(std::vector<int> &array, int k) {
        // Find the maximum value in the array
        int maxValue = 0;
        for (int i = 0; i < array.size(); i++) {
            if (array[i] > maxValue) {
                maxValue = array[i];
            }
        }

        // Create a boolean array to track the presence of each value
        std::vector<int> presence(maxValue, 0);

        // Mark the presence of each value in the boolean array
        for (int i = 0; i < array.size(); i++) {
            presence[array[i] - 1] = 1;
        }

        // Find the k-th smallest element by counting marked values
        int count = 0;
        int kthSmallestElement = 0;
        for (int i = 0; count < k; i++) {
            if (presence[i] == 1) {
                count++;
                kthSmallestElement = i + 1;
            }
        }

        return kthSmallestElement;
    }
};

class Solution:
    def kthSmallest(self, array, k):
        # Find the maximum value in the array
        maxValue = 0
        for num in array:
            if num > maxValue:
                maxValue = num

        # Create a boolean array to track the presence of each value
        presence = [0] * maxValue

        # Mark the presence of each value in the boolean array
        for num in array:
            presence[num - 1] = 1

        # Find the k-th smallest element by counting marked values
        count = 0
        kthSmallestElement = 0
        for i in range(maxValue):
            if presence[i] == 1:
                count += 1
                kthSmallestElement = i + 1
                if count == k:
                    break

        return kthSmallestElement

Time Complexity

• Finding Maximum Value:

  Iterating through the array to find the maximum value takes \( O(n) \) time, where \( n \) is the size of the array.

• Creating and Populating Presence Array:

  Creating the boolean array `presence` takes \( O(maxValue) \) time, where `maxValue` is the largest value in the array. Populating this array also takes \( O(n) \) time.

• Finding the k-th Smallest Element:

  Iterating through the `presence` array to find the k-th smallest element takes \( O(maxValue) \) time in the worst case.

• Overall Time Complexity:

  The overall time complexity is \( O(n + maxValue) \), where \( n \) is the size of the input array, and `maxValue` is the maximum value in the array.

Space Complexity

• Space for Presence Array:

  The boolean array `presence` requires \( O(maxValue) \) space to track the presence of each value from 1 to `maxValue`.

• Overall Space Complexity:

  The overall space complexity is \( O(maxValue) \), which is used by the `presence` array.