217. Contains Duplicate

INFO

Problem: Contains Duplicate

Pattern: Hash set / frequency map

Contains Duplicate asks whether any value appears more than once. The simplest brute-force version compares every pair, but a hash-based lookup gives a cleaner linear solution.

As we scan the array, we keep track of numbers already seen. If the current number has been seen before, the answer is immediately true. If the loop finishes without finding a repeat, the answer is false.

Approach

1. Create a dictionary or set for seen numbers.
2. Loop through nums.
3. If the current value already exists, return true.
4. Otherwise, store it and continue.
5. Return false after the loop.

A Set<Int> is the most direct structure for this problem, but a dictionary works too. The current solution uses a dictionary where the value is not important; the key is what matters.

Swift Notes

Dictionary lookup returns nil when a key does not exist. The implementation checks numCount[i] != nil to detect a repeated value. You could also write this with Set and insert, but the dictionary version makes the lookup logic explicit for beginners.

Complexity

• Time complexity: O(n).
• Space complexity: O(n).

Edge Cases

• A single-element array cannot contain duplicates.
• Duplicates can appear next to each other or far apart.
• Negative numbers and zero are handled the same as positive numbers.

class Solution {
    func containsDuplicate(_ nums: [Int]) -> Bool {
        var numCount: [Int: Int] = [:]
        for i in nums {
            if numCount[i] != nil {
                return true
            } else {
                numCount[i] = 1
            }
        }
        return false
    }
}

var solution = Solution()

var testcase1 = solution.containsDuplicate([1,2,3,1])
print(testcase1) // true

var testcase2 = solution.containsDuplicate([1,2,3,4])
print(testcase2) // false

var testcase3 = solution.containsDuplicate([1,1,1,3,3,4,3,2,4,2])
print(testcase3) // true