How to get Kth largest element of a DoubleStream in java

Question

What's the best way of getting the Kth largest element in a DoubleStream in java?

I know we can do .max().getDouble() to get the largest element.

Did you try to search for it? There are plenty of questions dealing with finding the k-th largest element in various data structures. — Henry, Oct 19 '17 at 04:04
[No code](http://idownvotedbecau.se/nocode) and [no attempt](http://idownvotedbecau.se/noattempt), please see [ask]. — Alex, Oct 19 '17 at 04:06
Possible duplicate of [How to find the kth largest element in an unsorted array of length n in O(n)?](https://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on) — geocar, Oct 19 '17 at 15:01

ZhekaKozlov · Answer 1 · 2017-10-19T07:44:52.517

2

OptionalDouble kthLargest = stream
        .map(i -> -i) // Trick to sort in reverse order
        .sorted()
        .distinct() // Remove duplicates
        .map(i -> -i)
        .skip(k - 1)
        .findFirst();

edited Oct 19 '17 at 07:44

answered Oct 19 '17 at 07:35

ZhekaKozlov

36,558
20
126
155

@Holger Stream may contain less than `k` elements – ZhekaKozlov Oct 19 '17 at 07:41
@Holger would this solution better faster/more memory efficient than using a boxed stream to sorted descending (which might be easier to read)? – Malte Hartwig Oct 19 '17 at 07:57
2

@Malte Hartwig: that depends on the stream size and on the implementation. AFAIK, when using `distinct()` with the current implementation, you have the boxing overhead anyway. But if you really need this operation to be efficient, you should use neither, but rather do something [like this](https://stackoverflow.com/q/5380568/2711488); it’s the same for the k smallest or largest elements. – Holger Oct 19 '17 at 08:08
What requirement is satisfied by calling `distinct()`? – shmosel Oct 19 '17 at 18:40
1

@shmosel some commenters asked how duplicate entries should be treated: Should the second largest element of [1,2,3,3] be 3, or 2? Since NeedleBallista hadn't answered in time, the distinct call was added as an option to ignore duplicates. – Malte Hartwig Oct 20 '17 at 07:11

Malte Hartwig · Accepted Answer · 2017-10-19T08:00:55.627

2

doubleStream.boxed()
            .sorted(Comparator.reverseOrder())
            .skip(k - 1)
            .findFirst()
            .orElse(null);

Will give you the k^th largest element, or null if there are less than k elements in the stream.

edited Oct 19 '17 at 08:00

answered Oct 19 '17 at 07:37

Malte Hartwig

4,477
2
14
30

Nir Alfasi · Answer 3 · 2017-10-20T19:31:50.853

0

Sort the stream, transform it to an array and get the item at array.length-k.

Example:

private static double getKth(DoubleStream ds, int k) {
    double[] array = ds
        .sorted()
        .toArray();
    return array[array.length-k];
}

You should add validation to make sure k has a legit value

edited Oct 20 '17 at 19:31

answered Oct 19 '17 at 04:06

Nir Alfasi

53,191
11
86
129

Or use skip and limit instead of `.toArray();` – c0der Oct 19 '17 at 04:52
@c0der mind showing some code ? – Nir Alfasi Oct 19 '17 at 05:10
I will give it a try (I am not the down voter) – c0der Oct 19 '17 at 07:54
I did post some code, but got a not-so-nice comment from @Holger, so I deleted it. Anyway I see others who used skip and limit – c0der Oct 19 '17 at 12:02
hmmm two downvotes without comments. Very helpful... I tested it with a few different cases on my machine and it seems to work just fine! – Nir Alfasi Oct 19 '17 at 18:35
@c0der yes, if you sort in reverse order you can skip (no need to limit though). – Nir Alfasi Oct 20 '17 at 19:30
See other answers that use limit. Your answer produces the Kth smallest. – c0der Oct 21 '17 at 02:32
@c0der the others use limit/skip since they sorted in reverse order. I'm using normal sorting which means that the last element is the biggest and `array.length-k` is the kth element. Had I returned `array[k]` it was the kth smallest. – Nir Alfasi Oct 21 '17 at 03:08
Try running: `double[] array = DoubleStream.of(4,3,5,6,7,2,1,8,9,0) .sorted() .toArray(); System.out.println(array[array.length-2]);` and see that it outputs 8 as required. – Nir Alfasi Oct 21 '17 at 03:12
You are right. My mistake. – c0der Oct 21 '17 at 03:21

xenteros · Answer 4 · 2017-10-19T07:35:11.070

-1

Once you have DoubleStream, make it sorted() in reverse order (DESC). Then limit(k) and sort ASC and take the first.

.boxed()
.distinct() //in case you want to ignore repeating values
.sorted(Comparator.reverseOrder())
.limit(k)
.sorted()
.findFirst());

edited Oct 19 '17 at 07:35

answered Oct 19 '17 at 07:09

xenteros

15,586
12
56
91

1

It will return k-th smallest element instead of the largest. – ZhekaKozlov Oct 19 '17 at 07:17
1

what if the list has duplicates till the nth number suppose we want to find the 2nd largest and the array is 2,1,6,6 by sorting it will give 6,6,2,1 and the 2nd will give 6 but that isn't true – Saram Ali Azhar Oct 19 '17 at 07:21
@xenteros You limit `k` smallest elements – ZhekaKozlov Oct 19 '17 at 07:21
@Saramali check the update. It depends on the definition of kth largest value.Some people will skip the repeated values and some won't – xenteros Oct 19 '17 at 07:22
It still finds the Kth **smallest** element. Imagine `k=1`, it would take the smallest element. – Malte Hartwig Oct 19 '17 at 07:25
1

Have you tried your code? I just did for the benefit of the doubt, and it returns the kth smallest element. – Malte Hartwig Oct 19 '17 at 07:29
`DoubleStream.of(1, 2, 6, 3, 8, 1) .sorted() .limit(1) .boxed() .sorted((Comparator.reverseOrder())) .findFirst() .ifPresent(System.out::println);` prints 1.0, should print 8.0. – Malte Hartwig Oct 19 '17 at 07:31
I didn't wake up yet, sorry for that guys – xenteros Oct 19 '17 at 07:33
@xenteros wouldn't it be `.limit(k)` instead of `.limit(1)`? – Lino Oct 19 '17 at 07:35
@MalteHartwig now it works – xenteros Oct 19 '17 at 07:35
3

`.boxed() [.distinct()] .sorted(Comparator.reverseOrder()) .skip(k) .findFirst()` that’s all. – Holger Oct 19 '17 at 07:36

How to get Kth largest element of a DoubleStream in java

4 Answers4