Extract K largest elements from array of N integers in O(N + K) time

user_5356096 0
Viewed 774

So, we have a list of N integers, from which we want to get K largest integers (unsorted). The problem is, this needs to be able to run in O(N + K). That's what stated in the assignment.

I've checked various algorithms and even made my own, but the best I can get is O((n-k)*k) which I don't think is close to O(N + K), unless I'm wrong.

Are there any algorithms out there that can do this in O(N + K) assuming the values in the list are pretty much random, and all positive? (We don't know the max value they can acheive)

Note that I need to find the K largest integers as in not the K-th largest but from N, K integers.

Example: N = 5, K = 2 Input: 5 6 8 9 3 Output: 9 8

data-structures time-complexity algorithm
2 Answers

A selection algorithm is used to find the kth largest element. Median of Medians is an O(n) selection algorithm.

Therefore, there's a simple O(n) algorithm for your problem: Let KTH be the kth largest element as returned by your selection algorithm. This takes O(n) time. Scan the array and extract all elements >= KTH. This takes O(n) time.

Quickselect is another selection algorithm worth knowing about. It's based on quicksort, so it's only O(n) in the average case.

user_3217720

The idea is to, make a Binary Search Tree, which can be done in O(log N), though in worst case O(N) [where N - is total nodes/array elements in this case].

Now we can do inorder traversal, to get all elements in sorted order, which can be done O(N) [Proof: Complexities of binary tree traversals ]

Now traverse the sorted elements K-times (descending order);

Therefore, overall complexity will be: O(N) + O(N) + O(K) => O(N+K)

IMPLEMENTATION:

public class Solution{
static class BST{
    int val;
    BST left, right;

    public BST(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}
// making bst from the array elements
static BST add(BST root, int item) {
    if(root == null) return new BST(item);

    if(root.val > item)
        root.left = add(root.left, item);

    else root.right = add(root.right, item);

    return root;
}
// doing inorder to get all elements in sorted order
static void inorder(BST root, List<Integer> list) {
    if(root.left != null)
        inorder(root.left, list);

    list.add(root.val);

    if(root.right != null)
        inorder(root.right, list);

}
public static void main(String[] args) {
    //Example: N = 5, K = 2 Input: 5 6 8 9 3 Output: 9 8
    int [] a = {1, 9, 2, 7, 3, -1, 0, 5, 11};

    BST root = null;

    for(int i=0; i<a.length; i++) {
        root = add(root, a[i]);
    }
    List<Integer> list = new ArrayList<Integer>();
    inorder(root, list);

   // process the list K times, to get K-th largest elements        
}

NB: in case of Duplicate values, you have to make sub-list for each node!

user_83596230
Related