Posts Kth Element (Without Sorting)
Post
Cancel

Kth Element (Without Sorting)

Problem Description

Given unsorted array of N distinct elements, find kth index position of its sorted form. (k will start from 0) Note: We cannot modify the array and we cannot use extra space.

Example:
arr[5] = {2 8 3 11 14}
k=2
Answer: 8

Solution

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package com.gauk;

public class KthElement {

    public static void main(String[] args) {
        System.out.println(new KthElement().findKthElement(new int[]{11, 24, 20, 3, 5, 27, 34, 9, 40}, 4));
    }

    public int findKthElement(int[] arr, int k){

        //The search space can be between the min and max of the array
        int l=getMin(arr);
        int h=getMax(arr);

        //initialize the answer with any value
        int ans = l;

        while(l<=h){

            int m = (l+h)/2;

            //how many elements less than M are present in the array?
            int c = elementsLessThan(arr, m);

            //we are looking for kth element. there must be exactly k elements lesser than it in sorted form [not k-1 because we are starting from 0]
            if(c < k){

                //the number of elements less than m in the array is less than k. So, for any number lesser than m, the value will be equal to or even lower.
                //so we can discard left side
                l=m+1;

            }else if(c > k){

                //the number of elements more than m in the array is more than k. This will be true for any number more than m. So, we can discard right side.
                h=m-1;

            }else{

                //This part is important. It may seem that we can simply return the answer here. However, it is possible that the number is not even present in the array.
                //So, we need to save the answer, and look for another number.
                //The important thing to realize here is that we would need to go to the right to look for the correct answer.
                //This is because, the  right most number which has k elements smaller than itself is the one present in the answer. The next number must be having > k elemeents smaller than itself.
                ans = m;
                l=m+1;

            }

        }

        return ans;

    }

    public int elementsLessThan(int[] arr, int m){
        int c = 0;
        for(int i=0; i<arr.length; i++){
            if(arr[i] < m) c++;
        }
        return c;
    }

    public int getMin(int[] arr){
        int min = arr[0];
        for(int i=0; i<arr.length; i++){
            if(arr[i] < min) min = arr[i];
        }
        return min;
    }

    public int getMax(int[] arr){
        int max = arr[0];
        for(int i=0; i<arr.length; i++){
            if(arr[i] > max) max = arr[i];
        }
        return max;
    }

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