K’th Largest Element in Unsorted Array

Given an array and a number k where k is smaller than size of array, find the k’th largest element in the given array. All array elements are distinct.

Examples:

Input: arr[] = {1, 7, 10, 4, 3, 30, 15}
       k = 3
Output: 10

Input: arr[] = {1, 7, 10, 4, 3, 30}
       k = 4
Output: 4

Java (sorting)
Time complexity: O(N log N)
Space complexity: O(1)

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
            return -1;
        }

        Arrays.sort(nums);
        
        return nums[nums.length-k];
        
    }
}

Java (heap sort)
Time complexity: O(N log N)
Space complexity: O(N)

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
            return -1;
        }

        Queue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
        for (int n : nums){
            q.offer(n);
        }
        
        for (int i = 1; i < k; ++i){
            q.poll();
        }
        
        return q.poll();
        
    }
}

Java (quick select)
Time complexity: O(N)
Space complexity: O(N)

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
            return -1;
        }

        //shuffle to eliminate worst case running time O(N^2)
        shuffle(nums);

        return findKthLargest(nums, k, 0, nums.length - 1);

    }

    private int findKthLargest(int[] nums, int k, int lo, int hi){
       if (lo <= hi){
            int pivot = partition(nums, lo, hi);

            if (hi - pivot == k - 1){
                return nums[pivot];
            } else if (hi - pivot < k - 1){
                return findKthLargest(nums,k-(hi-pivot+1),lo, pivot - 1);
            } else {
                return findKthLargest(nums,k,pivot + 1, hi);
            }
        }

        return -1;
    }

    private int partition(int[] nums, int lo, int hi){
        if (lo <= hi){
            int i = lo + 1;
            int j = lo + 1;

            while (j <= hi){
                if (nums[j] < nums[lo]){
                    swap(i, j, nums);
                    ++i;
                }
                 ++j;
            }

            swap(lo, i-1, nums);
            return i-1;
        }
        return -1;
    }

    private void shuffle(int[] nums){
        Random r = new Random();
        for (int i = 1; i < nums.length; ++i){
            int j = r.nextInt(i+1);
            swap(i, j, nums);
        }

    }


    private void swap(int i, int j, int[] nums){
        int x = nums[i];
        x ^= nums[j];
        nums[j] = x ^ nums[j];
        nums[i] = x ^ nums[j];
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s