Jan Vladimir Mostert Jan Vladimir Mostert - 1 year ago 54
Java Question

Find first matching string in two lists in less than O(n^2) time using a Java8 one-liner

Simple question, I have two arrays / lists, I'm looking for an efficient one-liner in Java8 to match the first argument against a long list of possible arguments.

Arguments are from

public static void main(String... args)
and the other one is from a list of predefined strings which I'll call secondArray,
["a", "b", "cc", "de", ...]
. I want to match the two incoming arrays against each other and find the first matching
ument against a

args = Arrays.asList("r", "b", "c", "d", ...)

secondList = Arrays.asList("q", "z", "x", "c", "d", ...)

The first matching argument would be

The Java7 (inefficient) way of doing this would have been:

String profile = "default";
for (String arg : args){
if (secondArray.contains(arg)){
profile = arg;


In Java8, this is what I've done so far, was wondering if there's a better way to do it (more efficient, faster, etc - let's assume both args and secondArray can potentially contain up to 100k entries):

String profile = Arrays.stream(args)


My assumption is that the filter doing
will mean O(n^2) complexity, since
will be called for each of the arguments. Anything closer to O(n) while still maintaining a single line of Java8 is what I'm after.

Answer Source

The trick to make it a one liner would be to create a set in filter cause

String profile = Arrays.stream(args)
            .filter(new HashSet(secondList)::contains)

Such set is going to be created only once. The same instance of set will be used for each item in args.

So this code is O(n) to create a set and then O(n) to finding first arg.

Just keep in mind that expanded lambda like

.filter(arg -> new HashSet(secondList).contains(arg))

will create a set for each argument and will blowup complexity to O(n^2).

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download