217.contains-duplicate.md

217. Contains Duplicate

There are lots of different ways to implement.

Brute force

fun containsDuplicate(nums: IntArray): Boolean {
    for (i in 0 until nums.size) {
        for (j in i + 1 until nums.size) {
            if (nums[i] == nums[j]) return true
        }
    }
    return false
}

• Time Complexity: O(n^2)
• Space Complexity: O(1)

Sorting

def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i - 1] == nums[i]:
                return True
        return False

fun containsDuplicate(nums: IntArray): Boolean {
    nums.sort()
    for (i in 1 until nums.size) {
        if (nums[i - 1] == nums[i]) return true
    }
    return false
}

• Time Complexity: O(n log n)
• Space Complexity: O(log n)

Counting

def containsDuplicate(self, nums: List[int]) -> bool:
    counter = Counter(nums)
    for num in nums:
        if counter[num] > 1: 
            return True
    return False

fun containsDuplicate(nums: IntArray): Boolean {
    val count = HashMap<Int, Int>()
    for (i in 0 until nums.size) {
        count[nums[i]] = (count[nums[i]] ?: 0) + 1
    }
    for (key in count.keys) {
        if (count[key]!! > 1) return true
    }
    return false
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Hash Table

def containsDuplicate(self, nums: List[int]) -> bool:
    seen_set = set()
    for n in nums:
        if n in seen_set:
            return True
        seen_set.add(n)
    return False

fun containsDuplicate(nums: IntArray): Boolean {
    val seenSet = hashSetOf<Int>()
    for (i in 0 until nums.size) {
        if (seenSet.contains(nums[i])) {
            return true
        }
        seenSet.add(nums[i])
    }
    return false
}

• Time Complexity: O(n)
• Space Complexity: O(n)

This sum approach is not applicable because the value of array is not in range of 0..n.