217. Contains Duplicate

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.

This is a straightforward question—we go through the list, tracking values that already have appeared previously. If we encounter a value that has already been seen, we return true; if we reach the end of the list, we return false.

The tricky part is how we can efficiently check if a value has already appeared—and this essentially boils down to the data structure we choose to store our seen values. If we use a list, for example, then we would have to iterate through the seen list for every element, which would give us a runtime complexity in $\mathcal{O}(n^2)$. We can instead use a set or a hash table, since it has the property of checking if a element is in the set in constant time.

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

Time Complexity

Since checking if an element is in a set take $\mathcal{O}(1)$ time, and we iterate through the entire list, we have a worst-case time complexity in $\mathcal{O}(n)$.

Space Complexity

At most, we store $n - 1$ elements in the set, during the last iteration of the for loop. Therefore, we have a worst-case space complexity in $\mathcal{O}(n)$.