217. Contains Duplicate

Prompt

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Examples

• Example 1:
  • Input: nums = [1,2,3,1]
  • Output: true
• Example 2:
  • Input: nums = [1,2,3,4]
  • Output: false
• Example 3:
  • Input: nums = [1,1,1,3,3,4,3,2,4,2]
  • Output: true

Solution

In C++

bool containsDuplicate(vector<int>& nums) {
	unordered_set<int> set;
	for (int num : nums) {
		if (set.contains(num)) return true;
		set.insert(num);
	}
	return false;
}

Explanation

Gradually add the numbers from the input list into an unordered set, checking if the current number is already in the set. If there is a duplicate true, else false. Very simple.

Big O Analysis

Time Complexity

The time complexity is $O(n{)}^{\ast }$, where $n$ is the size of the input list. See Amortized Notation.

Auxiliary Space Complexity

The space complexity is $O(n)$, where $n$ is the size of the input list