CareerCup

create a MaxHeap (binomial heap) of size n. Iterate over array and insert every element into heap. Extract Max k times, kth element should be kth largest.
Time: O(N log N) space : O(N).

Quick Select I found this implementation

public int findKthLargest(int[] nums, int k) 
{
	if (k < 1 || nums == null)
		return 0;

	return getKth(nums.length - k +1, nums, 0, nums.length - 1);
}

public int getKth(int k, int[] nums, int start, int end)
{
	int pivot = nums[end];
	int left = start;
	int right = end;
	while (true)
	{
		while (nums[left] < pivot && left < right)
		left++;

		while (nums[right] >= pivot && right > left)
			right--;

		if (left == right)
			break;

		swap(nums, left, right);
	}

	swap(nums, left, end);
	if (k == left + 1)
		return pivot;
	else if (k < left + 1)
		return getKth(k, nums, start, left - 1);
	else
		return getKth(k, nums, left + 1, end);
}

public void swap(int[] nums, int n1, int n2)
{
	int tmp = nums[n1];
	nums[n1] = nums[n2];
	nums[n2] = tmp;
}

Create a min heap of first k elements vin the array. This heap represents the k largest elements in the array and kth largest will be at the root. Now process each element not in the heap from the array. If the element is smaller than root ignore it. Else add it to the heap. Finally return the root.

public static int kthBiggest(int[] a, int k) {
		return kthSmallest(a, a.length-1-k, 0, a.length-1);
	}

	private static int kthSmallest(int[] a, int k, int from, int to) {
		
		// modified quicksort
		
		// error case
		if (k>to || k<from) {
			System.out.println("Oops, maybe we should throw an exception");
		}
		
		// base case
		if (k==from && k==to) {
			return a[k];
		}
		
		int pivot = a[from];
		
		int left = from+1;
		int right = to;
		
		while(left<=right){
			while (left<= to && a[left] < pivot){
				left++;
			}
			while (right >= from && a[right] > pivot){
				right--;
			}
			if (left<right){	
				//swap
				int temp = a[right];
				a[right] = a[left];
				a[left] = temp;
			}
		}
		//swap pivot with right which should point to the last smaller element
		a[from] = a[right];
		a[right] = pivot;
		
		if (right == k) {
			return pivot;
		} else if (right > k) {
			// continue on left side
			return kthSmallest(a, k, from, right-1);
		} else {
			// continue on right side
			return kthSmallest(a, k, right+1, to);
		}
	}

Best runtime of O(NlogK)

import java.util.Arrays;
import java.util.PriorityQueue;

public class KthLargest {
	public static void main(String[] args) {
		int[] array = {5, 3, 9, 1};
		System.out.println(kthLargest(array, 2));
		System.out.println(kthLargestEfficient(array, 2));
	}
	// O(NlogN)
	public static int kthLargest(int[] array, int k) {
		Arrays.sort(array);
		return array[array.length - 1 - k];
	}
	// O(Nlogk)
	public static int kthLargestEfficient(int[] array, int k) {
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		for(int i=0; i<k+1; i++) {
			pq.add(array[i]);
		}
		for(int i=k+1; i<array.length; i++) {
			pq.add(array[i]);
			pq.poll();
		}
		int kthLargest = pq.peek();
		return kthLargest;
	}
}

Presumably array length 'n' is very large relative to history depth 'k'.

The naive answer then is sorting on 'n' and taking the k'th index. That would be O(n) space and O(nlogn) time, both which are 'very large' because 'n' is 'very large'.

Use of a heap (or even insertion sort) of 'k' elements iterating without modifying the array gives the main improvement. So the final answer should be O(k) space complexity. Time complexity must still run over the entire N array so O(nlogk) for heap implementation or O(nk) for insertion sort.

The heap is clearly better here but given that n >> k, even the simple sliding insertion sort on k elements is still better than any answer involving sorting on n.

#include <stdio.h>

int arr[]={5,9,8,7,6,10,2,1};
int larg[10];

int main()
{
	int dat;
	int i,j,k=0,l;
	scanf("%d",&dat);
	for(i=0;i<dat;i++)
		larg[i]=0;
	
	for(i=0;arr[i]!=0x00;i++)
	{
		for(j=0;arr[j]!=0x00;j++)
		{
			if(arr[i]>=arr[j])
			{
				for(k=0;k<dat;k++)
				{
					if(arr[i]==larg[k])
					{
						k=dat;
					}
					else
					{
						if(arr[i]>larg[k])
						{
							for(l=dat-1;l>=k;l--)
							{
								larg[l+1]=larg[l];
							}
							larg[k]=arr[i];
							k=dat;
						}
					}
				}
			}
		}
	}
	printf("%d \n",larg[dat-1]);
}

public static int selectKthLargest(int[] arr, int k) {
		TreeSet<Integer> treeSet = new TreeSet<>();
		for (int i = 0; i < arr.length; i++) {
			treeSet.add(arr[i]);
		}

		Iterator itr = treeSet.iterator();
		for (int i = 0; i < k - 1; i++) {
			itr.next();
		}
		return (int) itr.next();
	}

public static int selectKthLargest(int[] arr, int k) {
		TreeSet<Integer> treeSet = new TreeSet<>();
		for (int i = 0; i < arr.length; i++) {
			treeSet.add(arr[i]);
		}

		Iterator itr = treeSet.iterator();
		for (int i = 0; i < k - 1; i++) {
			itr.next();
		}
		return (int) itr.next();
	}

for(int i=0;i<array.length;i++)
{
for(int j=i;j<array.length;j++){
if(array[i]<array[j])
{
int temp=array[i];
array[i]=arr[j];
array[j]=temp;
}
}
}
for(int i=0;i<arr.length;i++)
System.out.println(arr[i]);
System.out.println("Enter the k value to print kth largest value");
k=sc.nextInt();
System.out.println("Kth largest element is:"+arr[k-1]);
}

import bisect

def kth_largest(arr, k):
    l = [arr[0]]
    for e in arr[1:]:
        if e > l[0] or len(l) <= k:
            bisect.insort(l, e)
            if len(l) > (k+1):
                l = l[len(l) - (k+1):]
    return l[0];

a = [5, 3, 9, 1]
for k in range(len(a)):
    print(k, kth_largest([5, 3, 9, 1], k))

public static int kthBiggest(int[] a, int k) {
		return kthSmallest(a, a.length-1-k, 0, a.length-1);
	}

	private static int kthSmallest(int[] a, int k, int from, int to) {
		
		// modified quicksort
		
		// error case
		if (k>to || k<from) {
			System.out.println("Oops, maybe we should throw an exception");
		}
		
		// base case
		if (k==from && k==to) {
			return a[k];
		}
		
		int pivot = a[from];
		
		int left = from+1;
		int right = to;
		
		while(left<=right){
			while (left<= to && a[left] < pivot){
				left++;
			}
			while (right >= from && a[right] > pivot){
				right--;
			}
			if (left<right){	
				//swap
				int temp = a[right];
				a[right] = a[left];
				a[left] = temp;
			}
		}
		//swap pivot with right which should point to the last smaller element
		a[from] = a[right];
		a[right] = pivot;
		
		if (right == k) {
			return pivot;
		} else if (right > k) {
			// continue on left side
			return kthSmallest(a, k, from, right-1);
		} else {
			// continue on right side
			return kthSmallest(a, k, right+1, to);
		}

}

- Insert all elements in the array to Min Heap of size K.
- Then pick the root, it will be the Kth largest

This approach is better than Max heap where the heap size would be n. Also you need to perform K remove operation.

public int findKthLargest(int[] nums, int k) {
	Arrays.sort(nums);
	return nums[nums.length - k];
}

O(n log n) for merge sort

private static int getKthMax(int[] arr, int k) {
    if (arr == null || arr.length == 0 || k <= 0) {
        return -1;  
    }
    
    int n = arr.length;
    if (k > n) {
      return -1;
    }
    
    PriorityQueue<Integer> q = new PriorityQueue<Integer>(Collections.reverseOrder());
    for (int i = 0; i < n; i++) {
      q.add(arr[i]);
    }
    
    for (int i = 0; i < k-1; i++) {
      q.remove();
    }
    
    return q.peek();
  }

I think this problem depends a lot on the range of the expected values and how large do we expect K to be.

We do know K <= N, where N is the length of the input array, otherwise it wouldn't make sense.

I've designed the class interface thinking that this could also be solved with a running stream of values.

My assumptions are that K is much smaller than N (very small!).
I've got a running time of O(N * K) and extra space of O(K). I could also improve the solution using a Heap of max size K but again, assuming K is very small, that would be extra complexity for little added value.

Here's my Python solution:
You can either call the static method to solve it in batch or keep pushing and querying the values (provided K is a constant).

class KthLargest(object):
    def __init__(self, k):
        self._largest = [None] * (k + 1)

    def get_kth(self):
        return self._largest[0]

    def push(self, value):
        if self._largest[0] and self._largest[0] > value:
            return

        i = 0
        while i < len(self._largest) - 1 and self._largest[i + 1] < value:
            self._largest[i] = self._largest[i + 1]
            i += 1

        self._largest[i] = value

    @staticmethod
    def kth_largest(iterable, k):
        largest = KthLargest(k)
        for value in iterable:
            largest.push(value)
        return largest.get_kth()

Runtime O(nlogn)

import java.util.Arrays;

public class KthLargest {
	public static void main(String[] args) {
		int[] array = {5, 3, 9, 1};
		System.out.println(kthLargest(array, 3));
	}
	public static int kthLargest(int[] array, int k) {
		Arrays.sort(array);
		return array[array.length - 1 - k];
	}
}

function insertSortedList(list, value, startIndex, endIndex) {
  var i;
  //if empty, insert it in the list
  if(!list.length) {
    list.push(value);
    return;
  }
  //initialize start and end indecies
  startIndex = startIndex || 0;
  if(endIndex === undefined) endIndex = list.length -1;
  
  //if start and end are the same, then insert it before or after
  // don't insert if duplicate
  if(startIndex === endIndex) {
    if(value < list[startIndex]) {
      //insert before
      list.splice(startIndex, 0, value);
    } else if( value > list[startIndex]) {
      //insert after
      list.splice(startIndex + 1, 0, value);
    }
    return;
  }
  
  var middle = Math.floor((startIndex + endIndex) / 2);
  if(value === list[middle]) {
    return;
  }
  
  if(value < list[middle]) {
    //insert to bottom half
    insertSortedList(list, value, startIndex, middle);
    console.log("insert in the bottom half");
  } else {
    insertSortedList(list, value, middle + 1, endIndex);
    console.log("insert in the top half");
  }
}
function selectKLargest(array, k) {
  var largestSet = [];
  var i;
  for( i = 0; i < array.length; i++) {
    console.log(largestSet);
    //fill the list
    if(largestSet.length < k) {
      insertSortedList(largestSet, array[i]);
    } else {
      if(array[i] > largestSet[0]) {
        //remove the smallest entry, insert array[i]
        largestSet.splice(0, 1);
        insertSortedList(largestSet, array[i]);
      }
    }
  }
  console.log(largestSet[0]);
}
selectKLargest([5,3,9,1], 4);

This solution takes O(nlog(k)) time and O(k) space. I think it is the simplest coding solution, at least for Java:

public int largestValue(int[] array, int k){
	PriorityQueue<Integer> heap = new PriorityQueue<>();


	for(int i = 0; i < array.length; i++){
		heap.add(array[i]);
		if(heap.size() > k)
			heap.poll();
	}
        
       return heap.peek();

}

This is classic example of QuickSelect algorithm.

bool findmax(vector<int> vec, int k , int &ans)
{
    if(k >= vec.size())
        return false;
    
    std::nth_element(vec.begin(), vec.begin()+k, vec.end(), std::greater<int>());
    ans = vec[k];
    return ans;
}

We can use selection ranking, can be done in-place

Linear Time, doing a probabilistic algorithm

Time Complexity = O(klogk)
Space Complexity = O(k)

Logic:
1. Create a minHeap of size k. (This heap stores the k largest elements in the array)
2. Initialize the heap with first k elements.
3. For the next elements,
verify if the next element is greater than heap.peek().
if it is greater remove the top and add this element to the heap.
otherwise continue.
4. After iterating through all the elements in the array return heap.peek()

public class Main {

	public static void main(String[] args) {
		int[] array = {5, 3, 9, 1};
		int k = 4;
		System.out.println(k+"th largest number is "+kthLargest(array,k));
	}
	
	public static int kthLargest(int[] array, int k){
		PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k+1);
		if(array.length < k+1){
			System.out.println("Array size is smaller than k.");
			return 0;
		}
		for(int i=0;i<k+1;i++){
			queue.add(array[i]);
		}
		for(int i=k; i<array.length; i++){
			if(array[i] > queue.peek()){
				queue.remove();
				queue.add(array[i]);
			}
		}
		
		return queue.peek();
	}

}

public static void main(String[] args) {

int[] arr = {1,2,3,4,7,8,5,6};

Arrays.sort(arr);

System.out.println(arr[arr.length-3]);

}

Just sort the array and take "len-k"th element of array.