8
\$\begingroup\$

I have written this code for the question:

Finding k largest (or smallest) elements in an array

My approach uses a temporary array. Please suggest any improvements for readability or better performance.

public static void kLargest(int[] array, int k){

    if(k < 0 || k > array.length){
        return;
    }       
    int[] temp = new int[k];        

    for(int i = 0; i < k; i++){
        temp[i] = array[i];
    }       
    for(int i = k; i < array.length; i++){  
        int min = Integer.MAX_VALUE;
        int minIndex = 0;
        for(int j = 0; j < temp.length; j++){               
            if(temp[j] < min){
                min = temp[j];
                minIndex = j;
            }
        }   
        if(array[i] > min){
            temp[minIndex] = array[i];  
        }
    }
    for(int i : temp){
        System.out.print(i + " ");
    }
}
\$\endgroup\$
  • \$\begingroup\$ does the array have duplicates? \$\endgroup\$ – aakansha Jul 25 '15 at 4:55
  • \$\begingroup\$ Yeah, it has duplicates \$\endgroup\$ – Mehrdad Jul 25 '15 at 5:44
4
\$\begingroup\$

You can write it without extra space and with one less variable. Instead of considering a new array (temp array), do all the swap in the original array; in this case, you will skip O(k) extra space. Also, there is no need to keep track of min value. Keep tracking of min index and update it in every round will be enough.

public static void kLargest2(int[] array, int k){

    int minIndex = 0, i;                            //Find Min

    for (i = k; i < array.length; i++){
        minIndex = 0;
        for (int j = 0; j < k; j++){
            if(array[j] < array[minIndex]){
                minIndex = j;
                array[minIndex] = array[j];
            }
        }       
        if (array[minIndex] < array[i]){         //Swap item if min < array[i]

            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
    }
    for (int q = 0; q < k; q++){                            //Print output
        System.out.print(array[q] + " ");
    }
} 
\$\endgroup\$
  • \$\begingroup\$ Could you elaborate more on the improvements you've made? While we love reviewers and reviews, code-dumps often aren't very helpful to the asker if they don't have any explanations. \$\endgroup\$ – Ethan Bierlein Jul 25 '15 at 3:23
  • \$\begingroup\$ @EthanBierlein, Done :) \$\endgroup\$ – Hengameh Jul 25 '15 at 4:28
  • \$\begingroup\$ My intent is not to start a debate but I'd not write int minIndex = 0, i;. See also Java one line variable declaration?. \$\endgroup\$ – GeroldBroser reinstates Monica Jul 26 '15 at 18:09
  • \$\begingroup\$ I think, array[minIndex] = array[j]; statement is redundancy \$\endgroup\$ – isxaker Jan 24 '16 at 10:22
  • \$\begingroup\$ 1. You can still reduce scope of variables i and minIndex, 2. inner loop can skip 0th iteration. 3. You can keep track if the top kth portion of array has been modified otherwise there is no need to calculate minIndex again \$\endgroup\$ – Jigar Joshi Oct 3 '17 at 3:03
1
\$\begingroup\$
  • It's best practices to let statements like if, for, ... be followed by a space to disinguish them from method invocations.

  • I'd use:

    System.out.println(Arrays.toString(temp));
    

    instead of:

    for(int i : temp) {
        System.out.print(i + " ");
    }
    
\$\endgroup\$
  • \$\begingroup\$ I don't get your first suggestion. I didn't use spacing? And for the second improvement, I only need to print top 'k' elements of the array, not the whole array. So, if I want to use @Hengameh suggestion, I cannot use this statement. But in my code, I can use System.out.println(Arrays.toString(array)); instead of the enhanced for loop. Thanks anyway :) \$\endgroup\$ – Mehrdad Jul 27 '15 at 0:19
  • \$\begingroup\$ Sorry, I mean System.out.println(Arrays.toString(temp)); \$\endgroup\$ – Mehrdad Jul 27 '15 at 0:26
  • \$\begingroup\$ @Mehrdad You write if(...) and for(...). There are no spaces in front of the '('.You're right. I am referring to your code and it should be temp. I corrected it. \$\endgroup\$ – GeroldBroser reinstates Monica Jul 27 '15 at 9:15
1
\$\begingroup\$

Why don't you simply use Arrays.sort(), and get k largest or k smallest elements from the sorted array?

public static void kLargest (int [] array, int k) {
        Arrays.sort(array);
        for (int i = array.length-k; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }
\$\endgroup\$
  • 1
    \$\begingroup\$ The algorithm of the OP has complexity O(nk) while sorting has complexity O(n log n). If k is small with respect to n the OP method should be faster. \$\endgroup\$ – Emanuele Paolini Jul 30 '15 at 16:25
1
\$\begingroup\$

Here is a way to improve the performance to O(n + k log n):

  1. Build a max heap out of the entire array

  2. Extract the maximum element k times

Code:

/**
 * A function to fix a heap located in an array at a particular position
 * Returns a next position to fix the heap at, or -1.
 */
public static int fixHeap(int[] array, int position, int heapSize) {
    int child = position * 2 + 1;
    if (child >= heapSize) {
        return -1;
    }
    // Notice the different comparator, this is now a max heap
    if (child+1 < heapSize && array[child] < array[child+1]) {
        child++;
    }
    if (array[child] > array[position]) {
        // swap the two values
        int temp = array[child];
        array[child] = array[position];
        array[position] = temp;
        return child;
    }
    return -1;
}
public static void kLargest(int[] array, int k) {
    // Build a heap
    for (int i=array.length-1;i>=0;i--) {
        int index = fixHeap(array, i, array.length);
        while (index != -1) {
            index = fixHeap(array, index, array.length);
        }
    }
    for (int i=0;i<k;i++) {
        // print the maximum
        System.out.print(array[0] + " ");
        // replace it
        array[0] = array[array.length-1-i];
        // fix the heap
        int position = 0;
        while (position != -1) {
            position = fixHeap(array, position, array.length-1-i);
        }
    }
}
\$\endgroup\$
1
\$\begingroup\$

This is a little optimized version of Hengameh's answer. We can save on finding min. We don't actually have to find min on every iteration. However, in the worst case we will end up finding it.

public static void printTopK(int[] array, int k) {
    // validations
    if (k < 0 || k >= arr.length) {
        return;
    }
    int minIndex = 0;
    boolean minChanged = true;
    for (int i = k; i < array.length; i++) {
        if (minChanged) {
            // find minimum from top k
            for (int j = 0; j < k; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                    array[minIndex] = array[j];
                }
            }
        }
        // if my minimum from topK is less than current array's element
        // then swap it
        // or else we won't have different minIndex on next iteration
        if (array[minIndex] < array[i]) {
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
            minChanged = true;
        } else {
            minChanged = false;
        }
    }
    for (int i = 0; i < k; i++) {
        System.out.println(array[i]);
    }
}
\$\endgroup\$
0
\$\begingroup\$

Here is a performance improvement that solves the problem in \$\mathcal{O}(n \log k)\$ using a min heap.

A min heap is constructed on the first k elements of the array. The elements in the min heap form a candidate solution for the k largest elements. This takes O(k) time.

Then a loop is done on the rest of the elements of the array. If the current element is larger then the smallest element in the current candidate solution, the smallest element is replaced by the current element.

/**
 * A function to fix a heap located in an array at a particular position
 * Returns a next position to fix the heap at, or -1.
 */
public static int fixHeap(int[] array, int position, int heapSize) {
    int child = position * 2 + 1;
    if (child >= heapSize) {
        return -1;
    }
    if (child+1 < heapSize && array[child] > array[child+1]) {
        child++;
    }
    if (array[child] < array[position]) {
        // swap the two values
        int temp = array[child];
        array[child] = array[position];
        array[position] = temp;
        return child;
    }
    return -1;
}
public static void kLargest(int[] array, int k) {
    // Build a heap (on the first k elements, at least)
    for (int i=k-1;i>=0;i--) {
        int index = fixHeap(array, i, k);
        while (index != -1) {
            index = fixHeap(array, index, k);
        }
    }
    for (int index=k;index<array.length;index++) {
        if (array[index] > array[0]) {
            // swap the two values
            int temp = array[index];
            array[index] = array[0];
            array[0] = temp;
            // fix the heap
            int position = 0;
            while (position != -1) {
                position = fixHeap(array, position, k);
            }
        }
    }
    for (int i=0;i<k;i++) {
        System.out.print(array[i] + " ");
    }
}
\$\endgroup\$
  • \$\begingroup\$ I found a bug with the loop that fixes the heap. I would be fixing it shortly. \$\endgroup\$ – Element118 Aug 24 '16 at 9:45
  • \$\begingroup\$ Welcome to CodeReview! This is almost a code-only answer, which is discouraged on this site. Perhaps you could some text, references, to explain why and what changes you made. \$\endgroup\$ – ferada Aug 24 '16 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.