Posts Find Kth Smallest Element
Post
Cancel

Find Kth Smallest Element

Problem Description

Given N array elements, find Kth smallest element.

Problem Constraints

1 <= |A| <= 100000
1 <= B <= min(|A|, 500)
1 <= A[i] <= 109

Solution

Since B can be at max 500, we can use any algorithm to solve the problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    // DO NOT MODIFY THE ARGUMENTS WITH "final" PREFIX. IT IS READ ONLY
    public int kthsmallest(final int[] A, int B) {

        int arr[] = A.clone();

        for(int i=0; i<B; i++){
            int minIdx = i;
            for(int j=i+1; j<arr.length; j++){
                if(arr[j] < arr[minIdx]){
                    minIdx = j;
                }
            }
            swap(arr, i, minIdx);
        }

        return arr[B-1];

    }

    public void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
This post is licensed under CC BY 4.0 by the author.