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
Solutions
Solution
public class Solution { public bool ContainsDuplicate(int[] nums) { return nums.Distinct().Count() < nums.Length; }}Video 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.