CODEWITHSUNDEEP
dart
Andrey Gordeev
Andrey Gordeev

Reputation: 32449

Check if a list contains any element of another list in Dart

I have an array:

const list1 = [0, 1, 2];

How do I check if other arrays contain any of the target array elements?

For example:

[2, 3] //returns true;

[2, 3, 4] //returns true;

[3, 4] //returns false;

Upvotes: 4

Views: 5682

Answers (2)

jamesdlin
jamesdlin

Reputation: 89926

Using list1.indexWhere(list2.contains) should be fine for small lists, but for large lists, the asymptotic runtime complexity would be O(m * n) where m and n are the sizes of the lists.

A different way to pose the problem of checking if a list contains any element of another list is to check if the set-intersection of two lists is non-empty. The direct way to implement that would be:

var contains = list1.toSet().intersection(list2.toSet()).isNotEmpty;

Since the default Set implementation is a LinkedHashSet, lookups would be O(1), and computing the intersection would be linear with respect to one of the Sets. However, converting each List to a Set would take linear time, making the whole operation take O(m + n).

That's asymptotically efficient, but it computes the entire intersection just to determine whether it's empty or not, which is wasteful. You can do a bit better by using .any to stop earlier and noting that .any doesn't benefit from the receiving object being a Set:

var set2 = list2.toSet();
var contains = list1.any(set2.contains);

Note that if you can use Sets in the first place instead of Lists, then the conversion cost would disappear and make the operation O(m).

Upvotes: 18

Andrey Gordeev
Andrey Gordeev

Reputation: 32449

final contains = list1.indexWhere((e) => list2.contains(e)) > -1

Explanation

indexWhere returns an index of an element where the test function returned true.

contains returns true if the given element is presented in the array.

Upvotes: 2

Related Questions