2

In java 8 how do I find the Kth smallest efficiently? Kth smallest is

http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/

I've attempted below. If there is a more efficient solution which provides securities of Java-8 such as I should not have to check size before accessing indices in case of an empty array etc. I believe that my own solution is safe against empty array.

A provable time complexity comparison of my Java-8 approach and a better Java-8 approach will be appreciated if there exists one. Thank you.

package lab.rat.jerry.kthsmallest;

import static java.util.stream.Collectors.toList;

import java.util.Arrays;
import java.util.List;

public class KthSmallest {

    // Inputs
    static int k = 3;

    static Integer[] myIntArray = {2, 3, 1, 4, -2, 0, -3, 0, -1, 5 };

    public static void main(String[] args) {

        List<Integer> list = Arrays.asList(myIntArray);

        System.out.println(list
            .stream()
            .sorted()
            .distinct()
            .limit(k)
            .skip(k-1)
            .collect(toList())
            );
    }
}
15
  • 2
    You are sorting your input, which means your running time is O(nlog(n)). If I remember correctly, the best algorithm to find the k'th smallest (or largest) element takes O(n) time. The algorithm is similar to Quicksort, but runs faster, since it doesn't have to sort the entire input.
    – Eran
    Feb 8, 2017 at 13:12
  • 2
    I'm not sure that question about time complexity analysis is proper for this site. It's better to go to cs or codereview subsite
    – Andremoniy
    Feb 8, 2017 at 13:13
  • 2
    Why do you collect a single element into a List?
    – Holger
    Feb 8, 2017 at 13:18
  • 1
    This is an algorithmic question, so should be asked on cs. Feb 8, 2017 at 13:44
  • 1
    What @Eran means, is quickselect. Regarding the actual question, there is no java-8 specific improvement. The TreeSet based solution mentioned by Peter Lawrey is easier to implement and still better than the Stream based approach. But like quickSelect, it’s still not Java 8 specific.
    – Holger
    Feb 8, 2017 at 13:48

3 Answers 3

2

You can use a simple Data Structure PrioretyQueue in Java. You can fastly get and remove the Largest or the Smallest element:

public static int kthLargestElement(int[] nums, int k) {

    PriorityQueue<Integer> queue = new PriorityQueue<>();
    for (int i = 0; i < nums.length ; i++) {
        queue.add(nums[i]);
    }
    while (k > 1){
        queue.poll();
        k-=1;
    }
    return queue.poll();
}
4
  • You method returns the element based on position. What about duplicate elements?
    – WJS
    Aug 12, 2019 at 18:31
  • 1
    This method found the kth largest element in an unsorted array. This will be the kth largest element in sorted order, not the kth distinct element.
    – Mr Fun
    Aug 12, 2019 at 18:49
  • I understand that. But the OP used distinct in their code so I presumed duplicates were of concern. But I could be wrong.
    – WJS
    Aug 12, 2019 at 18:54
  • 1
    Yep, it working for duplicates also. In my case (Question from codesignal.com to find KTh larger element ) it works efficiently.
    – Mr Fun
    Aug 13, 2019 at 10:16
1

I do not know how efficient this is but it takes into consideration if:

  1. The array contains duplicate values.
  2. k is greater than the final list.
      int k = 4;
      int[] numbs = { 1, 2, 3, 3, 3, 3, 3, 3,10,11,12
      };

      int smallest =
            Arrays.stream(numbs).distinct().sorted().skip(k - 1).limit(
                  1).findFirst().orElse(Integer.MIN_VALUE);

      System.out.println(smallest);
  1. This converts the array to a stream.
  2. removes duplicates
  3. sorts whats left.
  4. skips the first k-1 values.
  5. limits the rest of the list to one
  6. Returns it.

If k is too large, the minimum int value is returned.

0

You can try this :

package lab.rat.jerry.kthsmallest;

import java.util.Arrays;
import java.util.List;

public class KthSmallest {

       // Inputs
      static int k = 3;

      static Integer[] myIntArray = {2, 3, 1, 4, -2, 0, -3, 0, -1, 5 };

      public static void main(String[] args) {

         List<Integer> list = Arrays.asList(myIntArray);

         int smallest = list.stream()
                            .mapToInt(Integer::intValue)
                            .sorted()
                            .limit(k)
                            .skip(k-1)
                            .findFist()
                            .getAsInt();
         System.out.println(smallest);
     }
}

By using this approach you can avoid NullPointerException. because findFist() will return optional.

Hope it help :)

2
  • Please note that it is not using distinct (though its not that important). Please note that my own code is also safe against empty array. Please note that time complexity related information is not in the answer. Can you please share some more details?
    – zur
    Feb 10, 2017 at 5:08
  • There is no real difference to the code that is already contained in the question. Since the question’s code already selects a single element, there is no sense in appending a min() operation, a simple findFirst() would do as well. Or just forEach(System.out::println).
    – Holger
    Feb 10, 2017 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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