top of page
Writer's pictureHui Wang

80. Interview: Contains Duplicate (LeetCode Easy)



Solution 1:

  • Time complexity : O(nlogn)

  • Space complexity : O(1)

After sorting an array, iterate through it using Two Pointers.

  • If two pointers (index and index + 1) that are next to each other have the same value, there is a duplicate element, and the function returns true.

  • If there are no duplicate elements, both pointers continue to move simultaneously.

  • If the iteration is complete and there are no duplicate elements, return false.


class Solution {
    func containsDuplicate(_ nums: [Int]) -> Bool {
        var newNums = nums
        newNums.sort()
        for index in 0..<newNums.count - 1 {
            if newNums[index] == newNums[index + 1] {
                return true
            }
        }
        return false
    }
}

Solution 2:


Use Set:

  • Iterate over the array and put the numbers in the Set.

  • If the number is already in the Set, return true.

  • If the iteration is complete and there are no duplicate elements, return false.


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

Solution 3:

  • Time complexity : O(n)

  • Space complexity : O(n)

This problem can be solved with one line of code.


class Solution {
    func containsDuplicate(_ nums: [Int]) -> Bool {
        nums.count != Set(nums).count
    }
}

 

Follow me on:

Commentaires


bottom of page