K’th Smallest/Largest Element in Unsorted Array

// Java code for Kth smallest element
// in an array
import java.util.Arrays;
import java.util.Collections;

class GFG {
    // Function to return K'th smallest
    // element in a given array
    public static int kthSmallest(Integer[] arr, int K)
    {
        // Sort the given array
        Arrays.sort(arr);

        // Return K'th element in
        // the sorted array
        return arr[K - 1];
    }

    // driver's code
    public static void main(String[] args)
    {
        Integer arr[] = new Integer[] { 12, 3, 5, 7, 19 };
        int K = 2;

        // Function call
        System.out.print("K'th smallest element is "
                         + kthSmallest(arr, K));
    }
}

// This code is contributed by Chhavi

// Java code for kth smallest element in an array

import java.util.Arrays;
import java.util.Collections;

class GFG {
    static int count(int[] nums, int mid)
    {
        // function to calculate number of elements less
        // than equal to mid
        int cnt = 0;

        for (int i = 0; i < nums.length; i++)
            if (nums[i] <= mid)
                cnt++;

        return cnt;
    }

    static int kthSmallest(int[] nums, int k)
    {
        int low = Integer.MAX_VALUE;
        int high = Integer.MIN_VALUE;
        // calculate minimum and maximum the array.
        for (int i = 0; i < nums.length; i++) {
            low = Math.min(low, nums[i]);
            high = Math.max(high, nums[i]);
        }
        // Our answer range lies between minimum and maximum
        // element of the array on which Binary Search is
        // Applied
        while (low < high) {
            int mid = low + (high - low) / 2;
            /*if the count of number of elements in the
              array less than equal to mid is less than k
              then increase the number. Otherwise decrement
              the number and try to find a better answer.
            */
            if (count(nums, mid) < k)
                low = mid + 1;

            else
                high = mid;
        }

        return low;
    }

    // Driver's code
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 5, 3, 19, 3 };
        int k = 3;

        // Function call
        System.out.print("Kth smallest element is "
                         + kthSmallest(arr, k));
    }
}

// This code is contributed by CodeWithMini

import java.util.PriorityQueue;

public class KthSmallestElement {

    // Function to find the kth smallest array element
    public static int kthSmallest(int[] arr, int N, int K) {
        // Create a max heap (priority queue)
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);

        // Iterate through the array elements
        for (int i = 0; i < N; i++) {
            // Push the current element onto the max heap
            pq.offer(arr[i]);

            // If the size of the max heap exceeds K, remove the largest element
            if (pq.size() > K)
                pq.poll();
        }

        // Return the Kth smallest element (top of the max heap)
        return pq.peek();
    }

    // Driver's code:
    public static void main(String[] args) {
        int N = 10;
        int[] arr = { 10, 5, 4, 3, 48, 6, 2, 33, 53, 10 };
        int K = 4;

        // Function call
        System.out.println("Kth Smallest Element is: " + kthSmallest(arr, N, K));
    }
}

// Java code for kth smallest element in an array

import java.util.Arrays;
import java.util.Collections;

class GFG {
    // Standard partition process of QuickSort.
    // It considers the last element as pivot
    // and moves all smaller element to left of
    // it and greater elements to right
    public static int partition(Integer[] arr, int l, int r)
    {
        int x = arr[r], i = l;
        for (int j = l; j <= r - 1; j++) {
            if (arr[j] <= x) {

                // Swapping arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;

                i++;
            }
        }

        // Swapping arr[i] and arr[r]
        int temp = arr[i];
        arr[i] = arr[r];
        arr[r] = temp;

        return i;
    }

    // This function returns k'th smallest element
    // in arr[l..r] using QuickSort based method.
    // ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT
    public static int kthSmallest(Integer[] arr, int l,
                                  int r, int K)
    {
        // If k is smaller than number of elements
        // in array
        if (K > 0 && K <= r - l + 1) {

            // Partition the array around last
            // element and get position of pivot
            // element in sorted array
            int pos = partition(arr, l, r);

            // If position is same as k
            if (pos - l == K - 1)
                return arr[pos];

            // If position is more, recur for
            // left subarray
            if (pos - l > K - 1)
                return kthSmallest(arr, l, pos - 1, K);

            // Else recur for right subarray
            return kthSmallest(arr, pos + 1, r,
                               K - pos + l - 1);
        }

        // If k is more than number of elements
        // in array
        return Integer.MAX_VALUE;
    }

    // Driver's code
    public static void main(String[] args)
    {
        Integer arr[]
            = new Integer[] { 12, 3, 5, 7, 4, 19, 26 };
        int K = 3;

        // Function call
        System.out.print(
            "K'th smallest element is "
            + kthSmallest(arr, 0, arr.length - 1, K));
    }
}

// This code is contributed by Chhavi

import java.util.Arrays;

public class GFG {

    // This function returns the kth smallest element in an
    // array
    static int kthSmallest(int[] arr, int n, int k)
    {
        // First, find the maximum element in the array
        int max_element = arr[0];
        for (int i = 1; i < n; i++) {
            if (arr[i] > max_element) {
                max_element = arr[i];
            }
        }

        // Create an array to store the frequency of each
        // element in the input array
        int[] freq = new int[max_element + 1];
        Arrays.fill(freq, 0);
        for (int i = 0; i < n; i++) {
            freq[arr[i]]++;
        }

        // Keep track of the cumulative frequency of
        // elements in the input array
        int count = 0;
        for (int i = 0; i <= max_element; i++) {
            if (freq[i] != 0) {
                count += freq[i];
                if (count >= k) {
                    // If we have seen k or more elements,
                    // return the current element
                    return i;
                }
            }
        }
        return -1;
    }

    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 12, 3, 5, 7, 19 };
        int n = arr.length;
        int k = 2;
        System.out.println("The " + k
                           + "th smallest element is "
                           + kthSmallest(arr, n, k));
    }
}

// This code is contributed by akshitaguprzj3