How to check if a value in a dictionary has duplicates?

Question

The algorithm below checks to see if an array has at least two or more duplicates. It uses a dictionary to store the occurrences; the time complexity is linear because it has to traverse the dictionary to see if a key occurs twice. In swift, how can I look up a value to see if it occurs more than twice in constant time ?

 func containsDuplicate(_ nums: [Int]) -> Bool {
        var frequencyTable = [Int:Int]()
        
        for num in nums {
            frequencyTable[num] = (frequencyTable[num] ?? 0 ) + 1
        }
        
        
        for value in frequencyTable.values{
            if value >= 2 {
                return true
            }
            
        }
        return false
    }
    
    containsDuplicate([1,1,2,3,3,3,3,4])

Answer 1

The second loop is not necessary if the first loop checks if the current element has already been inserted before, and returns from the function in that case:

func containsDuplicate(_ nums: [Int]) -> Bool {
    var frequencyTable = [Int:Int]()
    for num in nums {
        if frequencyTable[num] != nil {
            return true
        }
        frequencyTable[num] = 1
    }
    return false
}

Then it becomes apparent that we don't need a dictionary, a set is sufficient:

func containsDuplicate(_ nums: [Int]) -> Bool {
    var seen = Set<Int>()
    for num in nums {
        if seen.contains(num) {
            return true
        }
        seen.insert(num)
    }
    return false
}

This can be further simplified: The “insert and check if element was already present” operation can be done in a single call:

func containsDuplicate(_ nums: [Int]) -> Bool {
    var seen = Set<Int>()
    for num in nums {
        if !seen.insert(num).inserted {
            return true
        }
    }
    return false
}

This is similar to the solution from this answer

return nums.count != Set(nums).count

but possibly more efficient: The function returns immediately when a duplicate element has been detected.

Finally we can make the function generic, so that it works with all arrays of a hashable type:

func containsDuplicate<T: Hashable>(_ array: [T]) -> Bool {
    var seen = Set<T>()
    for element in array {
        if !seen.insert(element).inserted {
            return true
        }
    }
    return false
}

Example:

print(containsDuplicate([1,1,2,3,3,3,3,4])) // true
print(containsDuplicate(["A", "X"])) // false

Or as an extension for arbitrary collections of a hashable type:

extension Collection where Element: Hashable {
    func containsDuplicate() -> Bool {
        var seen = Set<Element>()
        for element in self {
            if !seen.insert(element).inserted {
                return true
            }
        }
        return false
    }
}
    
print([1,1,2,3,3,3,3,4].containsDuplicate())
print(["A", "X"].containsDuplicate())