Bhupesh Kumar

Posted on

# 217. 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.

## 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;
}
}
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;
}
}

return false;
}
}
``````

Runtime: 10ms

Learnings:

• Time Complexity
• Sorting
• HashSet
• HashMap
• Set

``````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
}

// 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