Given an integer array nums, return true if some value appears at least twice, and false if every element is distinct.
Example 1
Input: nums = [1,2,3,1]
Output: true
The value 1 appears at index 0 and index 3.
Example 2
Input: nums = [1,2,3,4]
Output: false
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Hints
Frequently asked at: Amazon, Apple, Adobe, Zoho, Cognizant
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force compares every pair in O(n^2). Sorting and checking neighbours is O(n log n). A hash set answers "have I seen this before?" in O(1) on average, so one pass over the array is enough, and we can stop early at the first repeat.
Algorithm
- Create an empty hash set.
- For each number, if it is already in the set, return
true. - Otherwise add it to the set.
- If the loop finishes, return
false.
Time:
O(n)Space: O(n)Interview tip: Interviewers may ask for O(1) extra space: then sort in place and compare neighbours in O(n log n), and mention that this modifies the input.
class Solution: def containsDuplicate(self, nums: List[int]) -> bool: seen = set() for x in nums: if x in seen: return True seen.add(x) return FalseCtrl + Enter runs the examples