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.
Example:
Input: nums = [1,2,3,1]
Output: true
Input: nums = [1,2,3,4]
Output: false
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Approach 1: Brute Force
This approach is straightforward but has a time complexity of O(n^2), making it less efficient for large arrays.
class Solution {
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;
}
}
Got TLE for this code
Constraints:
1 <= nums.length <= 105
-109 <= nums[i] <= 109
Approach 2: Sorting
Sorting helps in bringing duplicates together, simplifying the check. However, sorting has a time complexity of O(n log n).
class Solution {
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
for (int i = 1; i < n; i++) {
if (nums[i] == nums[i - 1]) {
return true;
}
}
return false;
}
}
Runtime: 20ms
Approach 3: HashSet
// Time complexity: O(n)
// Space complexity: O(n)
class Solution {
public boolean containsDuplicate(int[] nums) {
HashSet<Integer> hashset = new HashSet<Integer>();
for(int i=0;i<nums.length;i++){
if(hashset.contains(nums[i])){
return true;
}
hashset.add(nums[i]);
}
return false;
}
}
Runtime: 12ms
Approach 4: HashMap
class Solution {
public boolean containsDuplicate(int[] nums) {
Map<Integer, Boolean> mp = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (mp.containsKey(nums[i])) {
return true;
}
mp.put(nums[i], true);
}
return false;
}
}
Runtime: 12ms
Approach 5: Set
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
if (set.contains(num)) {
return true;
}
set.add(num);
}
return false;
}
}
Runtime: 10ms
Learnings:
- Time Complexity
- Sorting
- HashSet
- HashMap
- Set
Solution with Comments:
import java.util.HashSet;
import java.util.Set;
public class ContainsDuplicate {
public static boolean containsDuplicate(int[] nums) {
// Step 1: Create a HashSet to store unique elements
Set<Integer> seen = new HashSet<>();
// Step 2: Iterate through the array
for (int num : nums) {
// Step 3: Check if the element is already in the set (duplicate)
if (seen.contains(num)) {
// Step 4: If duplicate found, return true
return true;
}
// Step 5: Add the element to the set
seen.add(num);
}
// Step 6: If loop completes, no duplicates found, return false
return false;
}
public static void main(String[] args) {
// Test cases
int[] nums1 = {1, 2, 3, 1};
System.out.println(containsDuplicate(nums1)); // Output: true
int[] nums2 = {1, 2, 3, 4};
System.out.println(containsDuplicate(nums2)); // Output: false
int[] nums3 = {1, 1, 1, 3, 3, 4, 3, 2, 4, 2};
System.out.println(containsDuplicate(nums3)); // Output: true
}
}
Time Complexity Analysis:
HashSet Operations: The key operations affecting time complexity in this solution are contains(num) and add(num) on the HashSet.
Contains Operation: Checking if an element is in a HashSet (using contains) has an average time complexity of O(1). This is because HashSet uses hashing to store elements, allowing for constant-time lookups on average.
Add Operation: Adding an element to a HashSet (using add) also has an average time complexity of O(1), assuming the hash function distributes elements uniformly.
Loop Iteration: The for loop in the containsDuplicate function iterates through each element in the input array once.
Overall Time Complexity:
O(n): Considering all the operations together, the time complexity of the containsDuplicate function is O(n), where n is the number of elements in the input array nums.
Each num in the array is either added to the HashSet (O(1)) or checked if it's already in the HashSet (O(1)).
Since we have a single loop that goes through each element once, the time complexity is linear with respect to the input size.
Step-by-Step Explanation:
1. Create a Set: We create a HashSet named seen to store unique elements from the input array nums. HashSet allows for constant time (O(1)) lookup.
2. Iterate through the Array: We iterate through the given array nums using an enhanced for-loop (for (int num : nums)).
3. Check for Duplicate: For each element num in the array, we check if it is already in the seen set. We use seen.contains(num) to check if the element is a duplicate.
4. Return True if Duplicate Found: If seen already contains num, it means we've found a duplicate. We return true immediately.
5. Add to Set: If num is not in the seen set, it is a new element, so we add it to the seen set using seen.add(num).
6. Return False if No Duplicates: If the loop completes without finding any duplicates, we return false because there are no duplicates in the array.
5 Problems similar to 217 Contains Duplicate leetcode problem
Top comments (0)