Contains Duplicate
EasyPrompt
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.
Example 1:
Input: nums = [1,2,3,1]
Output: true
Explanation:
The element 1 occurs at the indices 0 and 3.
Example 2:
Input: nums = [1,2,3,4]
Output: false
Explanation:
All elements are distinct.
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Constraints:
1 <= nums.length <= 105-109 <= nums[i] <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
Compare each element with every other element in the array using nested loops to find duplicates.
Algorithm
- Iterate through the array with index i from 0 to n-1
- For each i, iterate with index j from i+1 to n-1
- If nums[i] equals nums[j], return true
- If no duplicates found, return false
Walkthrough
This approach involves using two nested loops to compare each element with every other element in the array. For each element at index i, we compare it with all elements at indices j > i. If we find any match, we return true indicating a duplicate was found. If no duplicates are found after checking all pairs, we return false.
public boolean containsDuplicate(int[] nums) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] == nums[j]) { return true; } } } return false;}Complexity
Time
O(n²) where n is the length of the array as we use nested loops
Space
O(1) as we only use a constant amount of extra space
Trade-offs
Pros
Simple to implement
No extra space required
Works well for very small arrays
Cons
Very inefficient for large arrays
Time complexity is quadratic
Not suitable for large scale applications
Sort the array first and then check adjacent elements for duplicates.
Algorithm
- Sort the input array in ascending order
- Iterate through the array from index 1 to n-1
- Compare each element with its previous element
- If any adjacent elements are equal, return true
- If no duplicates found, return false
Walkthrough
In this approach, we first sort the array in ascending order. After sorting, any duplicate elements will be adjacent to each other. We then iterate through the sorted array once and check if any adjacent elements are equal. If we find equal adjacent elements, we return true indicating a duplicate was found.
public boolean containsDuplicate(int[] nums) { Arrays.sort(nums); for (int i = 1; i < nums.length; i++) { if (nums[i] == nums[i-1]) { return true; } } return false;}Complexity
Time
O(n log n) where n is the length of the array, dominated by the sorting operation
Space
O(1) if using in-place sorting algorithm
Trade-offs
Pros
Better time complexity than brute force
Simple to implement
No extra space required (if using in-place sorting)
Cons
Modifies the original array
Not as efficient as hash set approach
Sorting overhead might be unnecessary
Use a HashSet to keep track of seen elements while iterating through the array.
Algorithm
- Create an empty HashSet
- Iterate through each element in the array
- If current element exists in set, return true
- Otherwise, add current element to set
- If no duplicates found, return false
Walkthrough
This approach uses a HashSet to store elements as we iterate through the array. For each element, we first check if it's already in the set. If it is, we've found a duplicate and return true. If not, we add it to the set. If we complete the iteration without finding any duplicates, we return false.
public boolean containsDuplicate(int[] nums) { HashSet<Integer> seen = new HashSet<>(); for (int num : nums) { if (seen.contains(num)) { return true; } seen.add(num); } return false;}Complexity
Time
O(n) where n is the length of the array as we only need to traverse the array once
Space
O(n) where n is the length of the array to store elements in the HashSet
Trade-offs
Pros
Optimal time complexity
Single pass through the array
Original array remains unchanged
Simple to implement
Cons
Requires extra space to store the HashSet
Space complexity is linear with input size
HashSet operations have some overhead
Solutions
Solution
public class Solution { public bool ContainsDuplicate(int[] nums) { return nums.Distinct().Count() < nums.Length; }}class Solution {public boolean containsDuplicate(int[] nums) { Set<Integer> s = new HashSet<>(); for (int num : nums) { if (!s.add(num)) { return true; } } return false; }}/** * @param {number[]} nums * @return {boolean} */ var containsDuplicate = function (nums) { return new Set(nums).size !== nums.length; };class Solution {public: bool containsDuplicate(vector<int> &nums) { unordered_set<int> s(nums.begin(), nums.end()); return s.size() < nums.size(); }};class Solution: def containsDuplicate(self, nums: List[int]) -> bool: return len(set(nums)) < len( nums) # class Solution ( object ): def containsDuplicate ( self , nums ): """ :type nums: List[int] :rtype: bool """ nums . sort () for i in range ( 0 , len ( nums ) - 1 ): if nums [ i ] == nums [ i + 1 ]: return True return FalseVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.