LeetCode #217 Contains Duplicate

Easy

Problem

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

Solution

Use a set to save all encountered element and return false once there is a duplicate in this set.

Complexity

It takes O(n) time for iterating entire list if n denotes to counts of numbers in nums. In each iteration, search and insertion of the hash set both takes O(logn) time in worst case and O(1) time in average cases. Therefore, it’s takes O(n * (2logn)) = O(nlogn) time in worst case but O(n) time in average cases.

For space complexity, it uses O(n) extra space for maintaining this hash set.