Kth Largest Element

Question (LC.215)

Given an unsorted array, find the kth largest element.

Example

([3,2,1,5,6,4], 2) => 5

Brute Force

Sort the input array. Then return the n-k smallest element.

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

Priority Queue

We need to somehow structure this unstructured data. Maintain a min heap of size k. Poll as we go.

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    return minHeap.peek();
}

Time O(nlogk) Space O(k)

Quick Select

A true linear time algorithm doesn't exist for an unsorted array. But we can randomly pick a pivot and hope that it will structure some parts of the data. We can use the partition step from quick sort to help us to do that.

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

// Quickly select the kth _smallest_ element
private int quickSelect(int[] arr, int k, int start, int end) {
    // base case
    if (start == end) {
        return arr[start];
    }
    // divide
    int pivotPos = partition(arr, start, end);
    // conquer
    if (k - 1 == pivotPos) {
        return arr[pivotPos];
    } else if (k - 1 < pivotPos) {
        return quickSelect(arr, k, start, pivotPos - 1);
    } else {
        return quickSelect(arr, k, pivotPos + 1, end);
    }
}

private int partition(int[] arr, int start, int end) {
    int pivot = arr[start];
    int i = start + 1, j = end;
    while (i <= j) {
        // swap after both pointers invalidate the condition
        while (i <= j && arr[i] < pivot) i++;
        while (i <= j && arr[j] >= pivot) j--;
        if (i <= j) {
            swap(arr, i, j);
            i++;
            j--;
        }
    }
    // swap the pivot with the last element smaller than it
    swap(arr, j, start);
    return j;
}

Be mindful on the post condition after partition. j becomes the end the smaller section and i becomes the start of the larger section.

Time O(n) on average because the geometric sum proves T(n) = O(n) + T(n/2) = O(n).

Median Variant (LI.80)

k=length/2 if even k=length/2 + 1 if odd

public int median(int[] nums) {
    int length = nums.length;
    if (length % 2 == 1)
        return findKthSmallest(nums, length / 2 + 1);
    else
        return findKthSmallest(nums, length / 2);
}

private int findKthSmallest(int[] arr, int k) {
    return quickSelect(arr, k, 0, arr.length - 1);
}

Mailbox Variant (EPI)

Given an unordered list of building objects, find the best place a mailbox to minimize the total distance.