Kth Smallest

GeeksforGeeks

Step-by-Step Solution Approach:

Understand the Problem:

• We are given an unsorted array and a value k.
• Our goal is to find the kth smallest element in the array without using the built-in sort function.

Constraints:

• The array contains distinct elements.
• The size of the array can be up to 10^6, and each element in the array can be as large as 10^6.

Initial Thought Process:

• A straightforward approach would be to sort the array and then pick the kth smallest element, but the problem explicitly asks to avoid this.
• We can instead use counting to efficiently determine the kth smallest element.

Counting Frequency Approach:

• We can leverage a frequency array to count occurrences of each element up to the maximum element (10^6).
• Once we have the frequency count, we can iterate through the frequency array to accumulate counts and determine when we reach the kth smallest element.

Implementation:

• We initialize a frequency array count[] with a size of maxElement + 1 to accommodate all possible values.
• Traverse the input array and increment the corresponding index in the count[] array for each element.
• Accumulate the counts in the count[] array until we reach or exceed k, at which point the current index is our desired kth smallest element.

Edge Cases:

The input is always valid as per constraints, so we assume that k is always a valid index.

JAVA CODE

This solution efficiently determines the kth smallest element with a time complexity of O(n + max_element), making it suitable for large arrays.

GITHUB:

github_SMILE_KHAN-JAVA