Contains Duplicate
Problem Statement
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.
Constraints:
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Input Format:
- An array of integers nums
Output Format:
- Return true if the array contains any duplicates, otherwise return false.
Examples:
Example 1:
Input:
nums = [1,2,3,1]
Output:
true
Explanation:
1 appears twice in the array.
Example 2:
Input:
nums = [1,2,3,4]
Output:
false
Explanation:
There are no duplicate elements in the array.
Example 3:
Input:
nums = [1,1,1,3,3,4,3,2,4,2]
Output:
true
Explanation:
Both 1, 2, 3, and 4 appear multiple times in the array.
Solutions
Hash Set Approach
Use a hash set to track elements seen so far. For each new element, check if it's already in the set.
Sorting Approach
Sort the array first, then check for adjacent duplicate elements.
Algorithm Walkthrough
Example input: nums = [1,2,3,1]
Step-by-step execution:
- Initialize an empty set
- i=0: nums[0]=1, 1 is not in the set, add 1 to set
- i=1: nums[1]=2, 2 is not in the set, add 2 to set
- i=2: nums[2]=3, 3 is not in the set, add 3 to set
- i=3: nums[3]=1, 1 is already in the set
- Return true
Hints
Hint 1
Hint 2
Hint 3
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the array and track the hash set as elements are processed to find duplicates.
Key visualization elements:
- current element
- hash set state
- duplicate found
Implementation Notes
This is a fundamental problem demonstrating hash set usage for efficient duplicate detection. It's a good introduction to using sets for quick lookups.