java 8 streams how to find min difference between elements of 2 lists

Question

I'm totally new to Streams of Java 8 and currently trying to solve this task, I have two lists as follow:

List<Integer> list1 = Arrays.asList(5, 11,17,123);
List<Integer> list2 = Arrays.asList(124,14,80);

I want to find the absolute min difference existing between all the elements out of these lists.

The expected result: 1(124-123=1)

It's not a problem to implement it with Java 7, but how i can achieve it with Streams of Java8? How i can iterate forEach element from List1 and also forEach from List2 and to keep the min value?

Just a quick note, are you using an IDE for your coding? Most of them should offer good help in what methods you can use to tackle stuff like this. — Koen De Groote, Apr 04 '18 at 12:55
It may help https://stackoverflow.com/questions/32131987/how-can-i-make-cartesian-product-with-java-8-streams basically just a foreach on the 2 lists to create a new difference list — pdem, Apr 04 '18 at 13:00

SEY_91 · Accepted Answer · 2018-04-04T13:35:17.597

7

Try this one

public static void main(String[] args) {
        List<Integer> list1 = Arrays.asList(5, 11,17,123); 
        List<Integer> list2 = Arrays.asList(124,14,80);
        OptionalInt min = list1.stream()
                          .flatMap(n -> list2.stream()
                          .map(r -> n-r > 0? n-r: r-n))
                          .mapToInt(t -> t).min();
        System.out.println(min.getAsInt());
    }

Edit(Holger suggestion)

 OptionalLong min = list1.stream()
.flatMapToLong(n -> list2.stream()
.mapToLong(r -> Math.abs(r-(long)n))).min();

edited Apr 04 '18 at 13:35

answered Apr 04 '18 at 13:09

SEY_91

1,615
15
26

2

`.mapToInt(t -> t)` becomes obsolete when you use `flatMapToInt` and `mapToInt` in the previous steps. Further, I’d use an indentation that makes it clear that the `map[ToInt]` belongs to the function passed to `flatMap[ToInt]`… – Holger Apr 04 '18 at 13:11
@Holger you mean like this `list1.stream().flatMapToInt(n -> list2.stream().mapToInt(r -> n-r > 0? n-r: r-n)).min()`. – SEY_91 Apr 04 '18 at 13:22
4

Exactly, but you shouldn’t roll out your own `abs` function. By the way, the distance between two `int` values may be larger than the `int` value range, so I’d recommend `OptionalLong min = list1.stream() .flatMapToLong(n -> list2.stream().mapToLong(r -> Math.abs(r-(long)n))) .min();` – Holger Apr 04 '18 at 13:33

score 7 · Answer 2 · answered Apr 04 '18 at 14:05

While it is easy to convert a “compare each element of list1 with each element of list2” logic to code using the Stream API and the solution’s source code might be short, it isn’t an efficient solution. If the lists are rather large, you will end up doing n × m operations.

Further, note that the distance between two int values can be up to 2³², which doesn’t fit into the (signed) int value range. So you should use long to express the result, if you’re looking for a general solution.

So a solution may look like this:

public static long smallestDistance(List<Integer> list1, List<Integer> list2) {
    int[] list2Sorted = list2.stream().mapToInt(Integer::intValue).sorted().toArray();
    if(list2Sorted.length == 0) throw new IllegalArgumentException("list2 is empty");
    long smallest = Long.MAX_VALUE;
    for(int i: list1) {
        int pos = Arrays.binarySearch(list2Sorted, i);
        if(pos >= 0) return 0;
        pos ^= -1;
        if(pos < list2Sorted.length) {
            long d = Math.abs(list2Sorted[pos] - (long)i);
            if(d < smallest) smallest = d;
        }
        if(pos > 0) {
            long d = Math.abs(list2Sorted[pos-1] - (long)i);
            if(d < smallest) smallest = d;
        }
    }
    if(smallest == Long.MAX_VALUE) throw new IllegalArgumentException("list1 is empty");
    return smallest;
}

By sorting one list, we can efficiently look up the closest element(s) for each element of the other list. This way, the time complexity reduces from O(n×m) (all cases) to O((n+m)×log(m)) (worst case). As a bonus, it will return immediately if it found a match, as that implies the smallest possible distance of zero.

If you want to test it, consider example input like a list of even and a list of odd numbers:

List<Integer> list1
    = IntStream.range(0, 100000).mapToObj(i -> i*2).collect(Collectors.toList());
List<Integer> list2
    = IntStream.range(0, 100000).mapToObj(i -> i*2+1).collect(Collectors.toList());

Since there is no exact match, short-cutting is not possible, but the different time complexity will become noticeable.

Excellent answer. Can `pos ^= -1` be replaced with `-pos - 1`? — Thiyagu, May 18 '18 at 04:37
@user7 yes, `pos ^= -1` is the same as `pos = -pos - 1` and also the same as `pos = ~pos`… — Holger, May 18 '18 at 06:13

java 8 streams how to find min difference between elements of 2 lists

2 Answers2