[LeetCode] 215. Kth Largest Element in an Array


Official solutions have several approaches including sorting, heap, and quick selecting. They are all great. I’d like to put forward another solution: Binary Search.

First, we can come to that the answer must be equal to or greater than the MIN element and equal to or smaller than the MAX element in the array. That is to say, the range of the answer is [min, max].

So, now let’s try to convert this problem into a decision one. By observing, we can find out that for a given x, if x is kth greatest element, there only k-1 elements are grater than x. For example, in array


If I guess, 5 is 2nd greatest element, then I can only find one element 6 is greater than 5.

That is to say, for a given x, if there are k elements >= x, we should guess another bigger x.


class Solution {
    int[] nums;
    int k;
    public int findKthLargest(int[] nums, int k) {
        this.nums = nums;
        this.k = k;
        int l = Integer.MAX_VALUE, r = Integer.MIN_VALUE;
        for (int x : nums) {
            l = Math.min(l, x);
            r = Math.max(r, x);
        while (l + 1 < r ) {
            int mid = (l + r) / 2;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid;
        if (check(r)) {
            return r;
        return l;
    private boolean check(int x) {
        int count = 0;
        for (int e : nums) {
            if (e >= x) {
        return count >= k;

Time Complexity


Similar Questions


You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *