How to remove duplicated data in multiple parallel arrays

Question

I'm trying to remove certain array elements of the same exact order in swift which have multiple identical values ie.

assume now I have 3 arrays

array1 = [a,b,c,d,d,c,d]
array2 = [1,2,3,4,4,3,4]
array3 = [aa,bb,cc,dd,dd,cc,dd]

The problem is: I need to remove from the array the elements which have all 3 duplicated values altogether

Which means, I need to get rid of elements with index: [4], [5], [6] from arrays 1, 2 and 3.

ps. 3 arrays have to be in separated arrays and can't rearrange its order since they have some critical information related to each other

Any suggestions would be appreciated.

Answer 1

var array1 = ["a","b","c","d","d","c","d"]
var array2 = [1,2,3,4,4,3,4]
var array3 = ["aa","bb","cc","dd","dd","cc","dd"]
var set: Set<Int> = []   // you can use a set to check the duplicated elements

for index in array2.indices.reversed() { // reversed is necessary to remove your elements
    if !set.insert(array2[index]).inserted {
        array1.remove(at: index)
        array2.remove(at: index)
        array3.remove(at: index)
    }
}

---

array1  // ["a", "b", "c", "d"]
array2  // [1, 2, 3, 4]
array3  // ["aa", "bb", "cc", "dd"]

Answer 2

Tuples are Equatable (given that their elements are Equatable) up to arity 6, which we could make use of here to zip the three arrays into a sequence of 3-tuples, identifying repeated 3-tuple elements, and removing the indices associated with these tuples from the original three arrays. Tuples are not, however, Hashable, so instead of using 3-tuples we could fall back on a utility Hashable type storing the three values (that the 3-tuple did type anonymously).

Utility type:

struct ZippedElement: Hashable {
    let a: String
    let b: Int
    let c: String

    init(_ a: String, _ b: Int, _ c: String) {
        self.a = a
        self.b = b
        self.c = c
    }

    // Use a very simple common hashValue calculation, simply
    // falling back on the hashValue of the Int member.
    var hashValue: Int { return b.hashValue }

    static func ==(lhs: ZippedElement, rhs: ZippedElement) -> Bool {
        return lhs.a == rhs.a && lhs.b == rhs.b && lhs.c == rhs.c
    }
}

Which allows us to perform the filtering/mutating operations on array1 through array3 as follows:

var seen = Set<ZippedElement>()
zip(zip(array1, array2), array3)
    .map { ZippedElement($0.0, $0.1, $1) }
    .enumerated().filter { !seen.insert($1).inserted }
    .map { $0.offset }.reversed()
    .forEach {
        array1.remove(at: $0)
        array2.remove(at: $0)
        array3.remove(at: $0)
    }

With, as a result, the last three elements being removed in each array:

print(array1) // ["a", "b", "c", "d"]
print(array2) // [1, 2, 3, 4]
print(array3) // ["aa", "bb", "cc", "dd"]

---

Your example data setup doesn't pose many challenges for the different solutions here, however, so @dasblinkenlight asks a good question:

Would it change the desired result if I replaced the last "dd" of array3 with "dx"?

In this case, I believe most of us assume that the 7th element in all the original arrays should be kept, as the "vertical" zip combination over all three arrays, for the 7th element (/column), is unique.

Applying the same approach as above for such a modified example:

var array1 = ["a",  "b",  "c",  "d",  "d",  "c",  "d"]
var array2 = [ 1,    2,    3,    4,    4,    3,    4]
var array3 = ["aa", "bb", "cc", "dd", "dd", "cc", "dx"]
                                               /*  ^^ obs */

var seen = Set<ZippedElement>()
zip(zip(array1, array2), array3)
    .map { ZippedElement($0.0, $0.1, $1) }
    .enumerated().filter { !seen.insert($1).inserted }
    .map { $0.offset }.reversed()
    .forEach {
        print($0)
        array1.remove(at: $0)
        array2.remove(at: $0)
        array3.remove(at: $0)
    }

print(array1) // ["a", "b", "c", "d", "d"]
print(array2) // [1, 2, 3, 4, 4]
print(array3) // ["aa", "bb", "cc", "dx"]
                                  /* ^^ ok */

---

Another comment to your question is asked by @SteveKuo, stating what is on probably on most of our minds (in excess of a somewhat fun algorithmic exercise) for all questions such as this one (index-tracking separate arrays ...):

Seems like a more appropriate data structure is to create struct/class/tuple of the array1/2/3 attributes.

And I believe this is the core answer you should take with you here, so even if you explicitly state

... ps. 3 arrays have to be in separated arrays

You probably want a single array of a custom type instead.

Answer 3

You can put the array into a set (which will inherently not contain duplicates), and then transfer it back to an array.

e.g.

var array2: [Int] = [1,2,3,4,4,3,4]
let set2 = Set<Int>(array2)
array2 = Array(set2).sorted()

If you need to to do set logic against other arrays as well, you can do something like set2.subtract(otherSequence).

Answer 4

The other solutions cover a working approach but all do so in O(n^2) time due to iterating through the array and calling remove(at:) repeatedly which is itself an O(n) operation.

Assuming all 3 arrays have duplicates in the same spots, here is a functional O(n) approach which instead uses swapping and then just trims the array once at the end. Not sure how much performance matters but this should run significantly quicker on larger datasets.

var array1 = ["a","b","c","d","d","c","d"]
var array2 = [1,2,3,4,4,3,4]
var array3 = ["aa","bb","cc","dd","dd","cc","dd"]

var set: Set<Int> = []

var lastIndex = 0
for index in array2.indices
{
    if set.insert(array2[index]).inserted
    {
        array1.swapAt(index, lastIndex)
        array2.swapAt(index, lastIndex)
        array3.swapAt(index, lastIndex)
        lastIndex += 1
    }
}

let numToRemove = array1.count - lastIndex
array1.removeLast(numToRemove)
array2.removeLast(numToRemove)
array3.removeLast(numToRemove)