Find Duplicate Elements In Array Using Swift

Question

How to find Duplicate Elements in Array? I have array of phone numbers so in the phone numbers i should start searching from the right side to the left side and find similar 6 integers. then i should print them out.

Extractor

why would you want to call your function from cellForRow... the correct approach is to first find duplicates and then display these... – Tabethatabib

with this function i should save all the contact info in the array and then perform search in this array yes? and after that i will gain a new array with duplicate items and it will be simple to display in the cell? am i correct? – Extractor

Your question is too broad and mixes two different (unrelated) problems: 1) How to find "duplicate contacts" in the address book. 2) How to display the result in a table view. – I would suggest that you restrict your question to a single problem. If that is solved you can post another question if necessary. – Jacobus

I have changed the question and posted single problem. – Extractor

Answer 1

To find duplicates, you could build cross reference by phone number, then filter that down to duplicates only. For example, consider:

let contacts = [
    Contact(name: "Rob",     phone: "555-1111"),
    Contact(name: "Richard", phone: "555-2222"),
    Contact(name: "Rachel",  phone: "555-1111"),
    Contact(name: "Loren",   phone: "555-2222"),
    Contact(name: "Mary",    phone: "555-3333"),
    Contact(name: "Susie",   phone: "555-2222")
]

You can build the cross reference dictionary with:

let crossReference = Dictionary(grouping: contacts, by: \.phone)

Then, to find the duplicates:

let duplicates = crossReference
    .filter { $1.count > 1 }

Clearly use whatever model types make sense for you, but the above uses the following Contact type:

struct Contact {
    let name: String
    let phone: String
}

There are many, many ways to implement this, so I would not focus on the implementation details above, but rather focus on the concept: Build cross reference original array by some key (e.g. phone number) and then filter results down to just those keys with duplicate values.

---

It sounds like you want to flatten this structure that reflects the duplicates, into a single array of contacts (I'm not sure why you'd want to do that, as you lose the structure identifying which are duplicates of each other), but if you want to do that, you can flatMap it:

let flattenedDuplicates = crossReference
    .filter { $1.count > 1 }                 // filter down to only those with multiple contacts
    .flatMap { $0.1 }                        // flatten it down to just array of contacts that are duplicates of something else

Thiol

thanks. so i made everything as you said but i didn't understand why it gives me on the console the duplicates but 100 times? – Extractor

It makes me wonder what the original array looked like. (One of your other questions you were adding rows to the array inside cellForRowAtIndexPath.) Double check the original array (e.g. look at the total count) and make sure the input is correct. – Thiol

sorry just one question, i have corrected my mistake and now i have correct count of numbers and names but how to fix this: [(555-1111, [name: Rob - phone [phone], name: Rachel - phone [phone]])]. As i have typed this should be: name: Rob - phone: [phone], name Rachel - phone [phone] ... – Extractor

It's entirely up to you as to how you want to display the results. I was assuming that you wanted a separate section in your table view for every set of duplicates, and then each row in that section would be the names of the contacts with that identical phone number. I imagined header with phone number, followed by rows with the contacts that share that phone number. If so, the model I've employed here is probably more conducive to that output. If you really want a single section with all of the duplicates running together, I guess you could do that, but it strikes me as less elegant. – Thiol

Thank you Rob it was all very helpful! – Extractor

your algorithm works fine it gives me an duplicate but in contact array i have changed phone numbers to my contact numbers and now it gaves me the count of contacts and each one is duplicate of it self. how can i fix this? – Extractor

The concept is fairly simple (build dictionary cross referencing contacts with array of each of the contacts associated with that number, filter out duplicates, sort, etc.), so it's hard for me to say where yours went wrong. Just go through each and every step and identify whether the input to that step was right, and whether the output is wrong. The most likely problem is that the original input to the first step is wrong, but it's impossible for me to say. You just have to go through, step by step, identifying where precisely it went awry. Good luck. – Thiol

Thanks. And in contacts array i have name and phone, so if i just enter one line with addressbook phone number it gives me --> [] <--- but when i add second line it gives me a duplicate of each self every time. – Extractor

i fixed all bugs i had but after to days trying i got this result: when i write manually the phone numbers it works fine and gives me only duplicates, but when am replacing phone number with my array of phone numbers its giving me an number which actually has no duplicate in the phone.... i get lost... – Extractor

i am trying to pass the data from your given code to the table view but whenever i get called them it gives me an empty space, i tried to take out some variables and some stupid things but it not helped me.. can you please help me? i just want to show the results on tableView without anything special. here is the code: gist.github.com/geowarsong/edb3b2b46dd875aecd12 – Extractor

I've revised my gist to illustrate how you might update tableview. gist.github.com/robertmryan/f90fc05a519dcdff01f2 – Thiol

Answer 2

Feeling ~clever~. Given an array of Ints

let x = [1, 1, 2, 3, 4, 5, 5]
let duplicates = Array(Set(x.filter({ (i: Int) in x.filter({ $0 == i }).count > 1})))
// [1, 5]

Please note, this is horrendously inefficient for everyone involved, including the compiler, and you.

I'm just showing off.

Edit: lol someone downvoted this, which leads me to reiterate, just in case: please DO NOT USE THIS in production or anywhere else.

Fortune

Indeed clever!! – Obsolete

Do you know what protocol I have to conform to in case to implement this method? – Domeniga

I love this one-liner! Cooooooool!👍😎 – Shirlyshiroma

Answer works as Aspected. But It is not memory efficient Solution. If u run above Code in X-code Playground That One Single Line will run for 57 Times. So, if you are Focusing to solve large Array of Data. In that case, I will not apply this Solution. – Bisk

Nice answer. In Swift 4, you can replace the (i: Int) with just i and let the compiler handle the types. – Cementite

As @MehulVekariya suggested, this isn't the most efficient for large arrays. It's O(n^2). If you have a large array, consider mergesort (O(nlogn)) or counting using a hashmap (O(n)). But those are more complicated. Rob's answer includes the hashmap solution, assuming Swift dictionaries are hashmaps. – Cementite

Converting the above solution to an extension will reduce the count of execution to 20 times. extension Array where Element: Hashable{ var removeDuplicates: Array{ return filter { i in filter { $0 == i }.count > 1 } } } print(Set(data.removeDuplicates)) – Litre

Answer 3

Swift 4+

One line, fast solution:

var numbers = [1,2,3,4,5,6,6,6,7,8,8]
let dups = Dictionary(grouping: numbers, by: {$0}).filter { $1.count > 1 }.keys

//Results: [6, 8]

Staunch

A useful spin on this if you're working with Identifiables: ` func duplicateIds() -> Dictionary<Iterator.Element.ID, [Iterator.Element]>.Keys { Dictionary(grouping: self, by: { $0.id }) .filter { $1.count > 1 } .keys } ` – Traceytrachea

Answer 4

Entirely derived from Rob's very neat answer. I've made it in to an Array extension and given names to the intermediate steps for clarity:

extension Array where Element: Hashable {
    func duplicates() -> Array {
        let groups = Dictionary(grouping: self, by: {$0})
        let duplicateGroups = groups.filter {$1.count > 1}
        let duplicates = Array(duplicateGroups.keys)
        return duplicates
    }
}

[1, 2, 2, 3, 1].duplicates() -> [1, 2]

Charissacharisse

Answer 5

You could implement it using "Merge sort", but you need to make one modification, during the merge step you should ignore the duplicates.

The easiest way to find duplicate elements is if the phone number is just a 6-digit number and has type Int, you could sort the array of phone numbers and than filter that to find duplicates.

var phoneNumbers = [123456, 234567, 345678, 123456, 456789, 135790, 456789, 142638]

func findDuplicates(sortedArray array: [Int]) -> [Int]
{
    var duplicates: [Int] = []

    var prevItem: Int = 0
    var addedItem: Int = 0

    for item in array
    {
        if(prevItem == item && addedItem != item)
        {
            duplicates.append(item)
            addedItem = item
        }

        prevItem = item
    }

    return duplicates
}

func sortPhoneNumbers(phoneNumbers: [Int]) -> [Int]
{
    return phoneNumbers.sorted({ return $0<$1 })
}

sortPhoneNumbers(phoneNumbers)
findDuplicates(sortPhoneNumbers(phoneNumbers))

In addition, you could implement the findDuplicates method in different ways:

Using Set (Swift 1.2+):

func findDuplicates(array: [Int]) -> [Int]
{
    var duplicates = Set<Int>()
    var prevItem = 0       

    for item in array
    {
        if(prevItem == item)
        {
            duplicates.insert(item)
        }

        prevItem = item
    }

    return Array(duplicates)
}

And so on.

Classicize

@Mazyod - from the answer: "you could SORT the array of phone numbers and than FILTER that to find duplicates." – Classicize

1. the function should do that then, since the name doesn't imply the input is sorted. 2. Look closely, you reset prevItem to 0 in each iteration. – Linguistics

if the function name was findDuplicates(sortedArray array: [Int]) -> [Int], that will make sense. But a developer reading the current name will not realize the array you pass in must be sorted. – Linguistics

@Linguistics if the developer reads the answer from start to end it makes sense as well. I've provided a snippet of code that helps to solve the problem. That's it. Also, if you find a typo mistake, you can just fix it (like 2.) – Classicize

Let us continue this discussion in chat. – Classicize

Answer 6

To filter an array based on properties, you can use this method:

extension Array {

    func filterDuplicates(@noescape includeElement: (lhs:Element, rhs:Element) -> Bool) -> [Element]{
        var results = [Element]()

        forEach { (element) in
            let existingElements = results.filter {
                return includeElement(lhs: element, rhs: $0)
            }
            if existingElements.count == 0 {
                results.append(element)
            }
        }

        return results
    }
}

Which you can call as followed, based on the contacts example of Rob:

let filteredContacts = myContacts.filterDuplicates { $0.name == $1.name && $0.phone == $1.phone }

Lefler

Answer 7

I've found a way by using reduce, here is the code(Swift 4):

let testNumbers = [1,1,2,3,4,5,2]
let nondupicate = testNumbers.reduce(into: [Int]()) {
    if !$0.contains($1) {
        $0.append($1)
    } else {
        print("Found duplicate: \($1)")
    }
}

As a side effect, it returns an array with no duplicated elements.

You can easily modify it for counting duplicated elements numbers, checking string arrays etc.

Larimer

Answer 8

let inputArray = [9820213496, 9546533545, 9820213496, 995543567]
var outputArray = [Int]()
for element in inputArray{
    if outputArray.contains(element){
        print("\(element) is Duplicate")
    }else{
        outputArray.append(element)
    }
}
print(outputArray) // print Array without duplication

Larimor

Answer 9

Same as in @tikhop's answer, but as Array extension (Swift 3):

extension Array where Element: Comparable & Hashable {

   public var duplicates: [Element] {

      let sortedElements = sorted { $0 < $1 }
      var duplicatedElements = Set<Element>()

      var previousElement: Element?
      for element in sortedElements {
         if previousElement == element {
            duplicatedElements.insert(element)
         }
         previousElement = element
      }

      return Array(duplicatedElements)
   }

}

Epidote

Answer 10

Antoine's solution in Swift 3+ syntax

extension Array {

    func filterDuplicates(includeElement: @escaping (_ lhs: Element, _ rhs: Element) -> Bool) -> [Element] {

        var results = [Element]()

        forEach { (element) in

            let existingElements = results.filter {
                return includeElement(element, $0)
            }

            if existingElements.count == 0 {
                results.append(element)
            }
        }
        return results
    }
}

Topic

Answer 11

Simple solution:

let numbers = ["1","2","3","6","8","3","6","3","5","8","9","7"]

func findDuplicate(list: [String]) -> [String] {
    var duplicates = Set<String>()
    for element in list {
        if list.firstIndex(of: element) != list.lastIndex(of: element) {
            duplicates.insert(element)
        }
    }
    
    return duplicates.sorted()
}

Parlour

Please read How to Answer and edit your question to contain an explanation as to why this code would actually solve the problem at hand. Always remember that you're not only solving the problem, but are also educating the OP and any future readers of this post. – Slipshod

Answer 12

A very simple answer which preserves all duplicates

let originalNums = [5, 3, 2, 3 , 7 , 5,3]
var nums = Array(originalNums)

let numSet = Set(nums)

for num in numSet {
  if let index = nums.index(of: num) {
     nums.remove(at: index)
  }
}

output

[3, 5, 3]

Drug

Answer 13

I also had a similar problem and have overcome in the following way. (Xcode 8.3.2)

let a = [123456, 234567, 345678, 123456, 456789, 135790, 456789, 142638]
var b = a // copy-on-write so that "a" won't be modified

while let c = b.popLast() {
  b.forEach() {
    if $0 == c {
      Swift.print("Duplication: \(c)")
    }
  }
}

//  Duplication: 456789
//  Duplication: 123456

The point is that the number of comparison. It would be smaller than others.

Assume that the number of items in the array is N. In each loop, the number will be decrementing by one. So, the total number will be (N-1) + (N-2) + (N-3) + ... + 2 + 1 = N * (N-1) / 2 When N = 10, that will be 9 + 8 + ... = 45

In contrast, that of some algorithms might be N * N. When N = 10 that will be 100.

In spite of that, taking into account of the cost of deep-copy or shallow-copy, I agree that @Patrick Perini's brilliant way would be better than this in some situations even the number of that would be N * N.

EDIT:

Alternative way with IteratorProtocol

let a = [123456, 234567, 345678, 123456, 456789, 135790, 456789, 142638]
var i = a.makeIterator()

while let c = i.next() {
  var j = i
  while let d = j.next() {
    if c == d {
      Swift.print("Duplication: \(c)")
    }
  }
}

//  Duplication: 123456
//  Duplication: 456789

That looks more complex, but uses the same idea as before. This does not have unnecessary memory allocations or copies.

My concern is efficiency, i.e. quicker UI response, longer battery life, smaller memory footprint, etc. Avoiding unnecessary memory allocations and/or memory copies which are automatically done by Swift in the behind scene would be crucial if we are providing competitive products. (-;

Monogenic

Answer 14

// find duplicate number in an array 
var arrNum = [1, 2, 3 , 3, 2, 5, 6, 2] 
let setOfNum = Set(Array(arrNum))
print(setOfNum)

Output: [6, 3, 5, 1, 2]

// find duplicate string in an array 
var arrStr = ["1", "2", "3" , "3", "2", "5", "6", "2"]  
let setOfStr = Set(Array(arrStr))
print(setOfNum)

Output: [6, 3, 5, 1, 2]

Draftee

Answer 15

Here's an efficient, O(n) method to do it. Some of the other answers here use .filter on a duplicates array or even the return value array, which makes the operation work in O(n^2) (using .contains is the same). Using a Set to store the duplicates we can make it O(n).

The other method that's been shown here is using a dictionary to first store the array elements. The idea being that a dictionary can't have duplicate elements. However, this doesn't guarantee the original order of the array to be preserved, so we need a different method.

Here's an Array extension that adds a removeDuplicates method that is efficient and guarantees the same result order as the original array's order.

extension Array where Iterator.Element == Int {
    func removeDuplicates() -> [Int] {
        var retVal: [Int] = []
        var duplicates: Set<Int> = []
        
        for number in self {
            if !duplicates.contains(number) {
                duplicates.insert(number)
                retVal.append(number)
            }
        }
        
        return retVal
    }
}

If you want to return the duplicate elements, just reverse some of the checks in the for loop (Still O(n)).

extension Array where Iterator.Element == Int {
    func findDuplicates() -> [Int] {
        var retVal: [Int] = []
        var duplicates: Set<Int> = []
        
        for number in self {
            if duplicates.contains(number) {
                retVal.append(number)
            } else {
                duplicates.insert(number)
            }
        }
        
        return retVal
    }
}

Quinn

Answer 16

There's still quite a bit of useful reusable stuff missing from Swift to make this simple, but OrderedCollections, which have not been used by the other answers yet, make it easier to get the duplicates "in order".

XCTAssertEqual(
  .init("💞❤️‍🔥💝❤️‍🔥🫀💕💔❤️‍🔥💕💝💘".duplicates),
  "❤️‍🔥💝💕"
)

import OrderedCollections

public extension Sequence where Element: Hashable {
  /// The non-unique elements of this collection, in the order of their first occurrences.
  var duplicates: OrderedSet<Element> {
    OrderedDictionary(bucketing: self).filter { $1 > 1 }.keys
  }
}

import struct OrderedCollections.OrderedDictionary

public protocol DictionaryProtocol {
  associatedtype Key
  associatedtype Value

  init<KeysAndValues: Sequence>(
    _: KeysAndValues,
    uniquingKeysWith: (Value, Value) throws -> Value
  ) rethrows where KeysAndValues.Element == (Key, Value)
}

extension Dictionary: DictionaryProtocol { }
extension OrderedDictionary: DictionaryProtocol { }

public extension DictionaryProtocol where Value == Int {
  /// Create "buckets" from a sequence of keys,
  /// such as might be used for a histogram.
  init<Keys: Sequence>(bucketing unbucketedKeys: Keys)
  where Keys.Element == Key {
    self.init(zip(unbucketedKeys, 1), uniquingKeysWith: +)
  }
}

/// `zip` a sequence with a single value, instead of another sequence.
@inlinable public func zip<Sequence: Swift.Sequence, Constant>(
  _ sequence: Sequence, _ constant: Constant
) -> LazyMapSequence<
  LazySequence<Sequence>.Elements,
  (LazySequence<Sequence>.Element, Constant)
> {
 sequence.lazy.map { ($0, constant) }
}

Oxide

Answer 17

extension Array where Element: Hashable {
     func similar() -> Self {
        var used = [Element: Bool]()

        return self.filter { used.updateValue(true, forKey: $0) != nil }
    }
}

Kucera

Can you update your answer to include some explanation of what you're doing and why it is different than other existing answers? This is always a good idea for Stack Overflow answers, but it's especially important on these old questions with a lot of established answers. – Deryl