-
Notifications
You must be signed in to change notification settings - Fork 18
/
217.Contains-Duplicate.js
53 lines (48 loc) · 1.6 KB
/
217.Contains-Duplicate.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
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.
*/
//Brute force solution Time Complexity: O(n^2), Space Complexity: O(1)
const containsDuplicate = (nums) => {
if (nums.length <= 0) return false;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] === nums[j]) {
return true;
}
}
}
return false;
};
// Optimal solution 1, using sorting Time Complexity: O(nlogn), Space Complexity: O(1)
const containDuplicate = (nums) => {
if (nums.length <= 1) return false;
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length; i++) {
if (nums[i] === nums[i + 1]) {
return true;
}
}
return false;
};
// Optimal solution 2, using hashmaps Time Complexity: O(n), Space Complexity: O(n)
const containDuplicate1 = (nums) => {
let map = new Map();
let num;
for (num of nums) {
if (map.has(num)) return true;
map.set(num);
}
return false;
};
//Optimal solution 3, using sets Time Complexity: O(n), Space Complexity: O(n)
//A set forms a new data type with no duplicates and is unordered
const containDuplicate2 = (nums) => {
//returns true if the length of the array is not equal to the size of the set created
return nums.length !== new Set(nums).size
}
//tests
console.log(containsDuplicate([1, 2, 3, 1])); //Output: true
console.log(containDuplicate([1, 2, 3, 4])); //Output: false
console.log(containsDuplicate1([1, 1, 1, 3, 3, 4, 3, 2, 4, 2])); //Output: true
console.log(containsDuplicate1([])); //Output: false