How to get list of common elements of 2 array in Swift?
ArraysSwiftArrays Problem Overview
I have two arrays:
fruitsArray = ["apple", "mango", "blueberry", "orange"]
vegArray = ["tomato", "potato", "mango", "blueberry"]
How can I get the list of common items in those two array which gives
ouptput = ["mango", "blueberry"]
I can't use if contains(array, string) as I want to compare 2 arrays.
Arrays Solutions
Solution 1 - Arrays
You can also use filter and contains in conjunction:
let fruitsArray = ["apple", "mango", "blueberry", "orange"]
let vegArray = ["tomato", "potato", "mango", "blueberry"]
// only Swift 1
let output = fruitsArray.filter{ contains(vegArray, $0) }
// in Swift 2 and above
let output = fruitsArray.filter{ vegArray.contains($0) }
// or
let output = fruitsArray.filter(vegArray.contains)
#Set vs Array for a single computation of common elements
We consider the following code snippet:
let array1: Array = ...
let array2: Array = ...
// `Array`
let commonElements = array1.filter(array2.contains)
// vs `Set`
let commonElements = Array(Set(array1).intersection(Set(array2)))
// or (performance wise equivalent)
let commonElements: Array = Set(array1).filter(Set(array2).contains)
I have made some (artificial) benchmarks with Int and short/long Strings (10 to 100 Characters) (all randomly generated). I always use array1.count == array2.count
I get the following results:
If you have more than critical #(number of) elements converting to a Set is preferable
data | critical #elements
-------------|--------------------
Int | ~50
short String | ~100
long String | ~200
###Explanation of the results
Using the Array approach uses "Brute force"-search which has time complexity O(N^2) where N = array1.count = array2.count which is in contrast to the Set approach O(N). However the conversion from Array to Set and back is very expensive for large data which explains the increase of critical #elements for bigger data types.
#Conclusion
For small Arrays with about 100 elements the Array approach is fine but for larger ones you should use the Set approach.
If you want to use this "common elements"-operation multiple times it is advisable to use Sets only if possible (the type of the elements has to be Hashable).
###Final Remarks
A conversion from Array to Set is kind of expensive while the conversion from Set to Array is in contrast very inexpensive.
Using filter with .filter(array1.contains) is performance wise faster than .filter{ array1.contains($0) } since:
-
the last one creates a new closure (only once) whereas the first one passes only a function pointer
-
for the last one the call of the closure creates an additional stack frame which costs space and time (multiple times:
O(N))
Solution 2 - Arrays
Convert them to Set
let fruitsArray = ["apple", "mango", "blueberry", "orange"]
let vegArray = ["tomato", "potato", "mango", "blueberry"]
let fruitsSet = Set(fruitsArray)
let vegSet = Set(vegArray)
let output = Array(fruitsSet.intersection(vegSet))
Solution 3 - Arrays
You don't need a Set (as the comments above have mentioned).
You could instead use a generic function, similar to the one Apple use in their Swift Tour, and thus avoid casting:
func anyCommonElements <T, U where T: SequenceType, U: SequenceType, T.Generator.Element: Equatable, T.Generator.Element == U.Generator.Element> (lhs: T, rhs: U) -> Bool {
for lhsItem in lhs {
for rhsItem in rhs {
if lhsItem == rhsItem {
return true
}
}
}
return false
}
This function can take any two arrays (SequenceTypes) and if any of their elements are the same it returns true.
You could simply modify this generic function to package up an array of strings and return that instead.
For example like this:
func arrayOfCommonElements <T, U where T: SequenceType, U: SequenceType, T.Generator.Element: Equatable, T.Generator.Element == U.Generator.Element> (lhs: T, rhs: U) -> [T.Generator.Element] {
var returnArray:[T.Generator.Element] = []
for lhsItem in lhs {
for rhsItem in rhs {
if lhsItem == rhsItem {
returnArray.append(lhsItem)
}
}
}
return returnArray
}
Usage like this:
var one = ["test2", "dog", "cat"]
var other = ["test2", "cat", "dog"]
var result = arrayOfCommonElements(one,other)
print(result) //prints [test2, dog, cat]
The added benefit here is that this function also works with all same typed arrays. So later if you need to compare two [myCustomObject] arrays, once they both conform to equatable, you're all set! (pun intended)
Edit: (For non common elements) you could do something like this
func arrayOfNonCommonElements <T, U where T: SequenceType, U: SequenceType, T.Generator.Element: Equatable, T.Generator.Element == U.Generator.Element> (lhs: T, rhs: U) -> [T.Generator.Element] {
var returnArray:[T.Generator.Element] = []
var found = false
for lhsItem in lhs {
for rhsItem in rhs {
if lhsItem == rhsItem {
found = true
break
}
}
if (!found){
returnArray.append(lhsItem)
}
found = false
}
for rhsItem in rhs {
for lhsItem in lhs {
if rhsItem == lhsItem {
found = true
break
}
}
if (!found){
returnArray.append(rhsItem)
}
found = false
}
return returnArray
}
This implementation is ugly though.
Solution 4 - Arrays
A generic method, inspired by The Swift Programming Language (Swift 3) exercise:
func commonElements<T: Sequence, U: Sequence>(_ lhs: T, _ rhs: U) -> [T.Iterator.Element]
where T.Iterator.Element: Equatable, T.Iterator.Element == U.Iterator.Element {
var common: [T.Iterator.Element] = []
for lhsItem in lhs {
for rhsItem in rhs {
if lhsItem == rhsItem {
common.append(lhsItem)
}
}
}
return common
}
Then, use it like this:
var a = [3,88,74]
var b = [1,3,88]
print("commons: \(commonElements(a, b))")
--> commons: [3, 88]
Solution 5 - Arrays
The following works with swift 4:
let fruitsArray = ["apple", "mango", "blueberry", "orange"]
let vegArray = ["tomato", "potato", "mango", "blueberry"]
var someHash: [String: Bool] = [:]
fruitsArray.forEach { someHash[$0] = true }
var commonItems = [String]()
vegArray.forEach { veg in
if someHash[veg] ?? false {
commonItems.append(veg)
}
}
print(commonItems)
Solution 6 - Arrays
Using Set and also intersection as follows:
func findIntersection (firstArray : [Int], secondArray : [Int]) -> [Int]
{
return [Int](Set<Int>(firstArray).intersection(secondArray))
}
print (findIntersection(firstArray: [2,3,4,5], secondArray: [1,2,3]))