You have an integer array nums and need to determine if there are any duplicate elements in the array.
What is a Duplicate?
A duplicate is an element that appears more than once in the array.
Task:
Write a function to check if any value appears at least twice. If so, return true. If all elements are unique, return false.
Input: array = [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
The array will contain between 1 and 100,000 elements.
Each element will be an integer within the range of -1,000,000,000 to 1,000,000,000.
function containsDuplicateWithSet(nums) {
if (nums.length < 1 || nums.length > 10**5) {
throw new Error("Array length out of bounds.");
}
const seen = new Set();
for (const num of nums) {
if (seen.has(num)) {
return true;
}
seen.add(num);
}
return false;
}
const array1 = [1,2,3,1];
containsDuplicateWithSet(array1); //output: true
const nums2 = [1,2,3,4];
containsDuplicateWithSet(nums2); //output: false
const nums3 = [1,1,1,3,3,4,3,2,4,2];
containsDuplicateWithSet(nums3); //output: true
function containsDuplicateWithSorting(nums) {
if (nums.length < 1 || nums.length > 10**5) {
throw new Error("Array length out of bounds.");
}
nums.sort((a, b) => a - b);
for (let i = 1; i < nums.length; i++) {
if (nums[i] === nums[i - 1]) {
return true;
}
}
return false;
}
const array1 = [1,2,3,1];
containsDuplicateWithSorting(array1); //output: true
const nums2 = [1,2,3,4];
containsDuplicateWithSorting(nums2); //output: false
const nums3 = [1,1,1,3,3,4,3,2,4,2];
containsDuplicateWithSorting(nums3); //output: true
function containsDuplicateWithHashMap(nums) {
if (nums.length < 1 || nums.length > 10**5) {
throw new Error("Array length out of bounds.");
}
const countMap = {};
for (const num of nums) {
if (countMap[num]) {
return true;
}
countMap[num] = 1;
}
return false;
}
const array1 = [1,2,3,1];
containsDuplicateWithHashMap(array1); //output: true
const nums2 = [1,2,3,4];
containsDuplicateWithHashMap(nums2); //output: false
const nums3 = [1,1,1,3,3,4,3,2,4,2];
containsDuplicateWithHashMap(nums3); //output: true
function containsDuplicateWithTwoPointer(nums) {
if (nums.length < 1 || nums.length > 10**5) {
throw new Error("Array length out of bounds.");
}
nums.sort((a, b) => a - b);
let left = 0;
let right = 1;
while (right < nums.length) {
if (nums[left] === nums[right]) {
return true;
}
left++;
right++;
}
return false;
}
const array1 = [1,2,3,1];
containsDuplicateWithTwoPointer(array1); //output: true
const nums2 = [1,2,3,4];
containsDuplicateWithTwoPointer(nums2); //output: false
const nums3 = [1,1,1,3,3,4,3,2,4,2];
containsDuplicateWithTwoPointer(nums3); //output: true
function containsDuplicateWithSetSpread(nums) {
if (nums.length < 1 || nums.length > 10**5) {
throw new Error("Array length out of bounds.");
}
return new Set(nums).size !== nums.length;
}
const array1 = [1,2,3,1];
containsDuplicateWithSetSpread(array1); //output: true
const nums2 = [1,2,3,4];
containsDuplicateWithSetSpread(nums2); //output: false
const nums3 = [1,1,1,3,3,4,3,2,4,2];
containsDuplicateWithSetSpread(nums3); //output: true
function containsDuplicateWithBitVector(nums) {
if (nums.length < 1 || nums.length > 10**5) {
throw new Error("Array length out of bounds.");
}
const bitVector = new Uint8Array(2**16); // Example for limited range, adjust size if needed
for (const num of nums) {
const index = num & (bitVector.length - 1); // Modulo operation
if (bitVector[index]) {
return true;
}
bitVector[index] = 1;
}
return false;
}
const array1 = [1,2,3,1];
containsDuplicateWithBitVector(array1); //output: true
const nums2 = [1,2,3,4];
containsDuplicateWithBitVector(nums2); //output: false
const nums3 = [1,1,1,3,3,4,3,2,4,2];
containsDuplicateWithBitVector(nums3); //output: true
function containsDuplicateWithFrequencyArray(nums) {
// Validate the input constraints
if (nums.length < 1 || nums.length > 100000) {
throw new Error("Array length out of bounds.");
}
// Initialize the frequency map
const frequencyMap = new Map();
// Check for duplicates
for (const num of nums) {
if (frequencyMap.has(num)) {
return true; // Duplicate found
}
frequencyMap.set(num, true); // Mark this number as seen
}
// No duplicates found
return false;
}
const array1 = [1,2,3,1];
containsDuplicateWithFrequencyArray(array1); //output: true
const nums2 = [1,2,3,4];
containsDuplicateWithFrequencyArray(nums2); //output: false
const nums3 = [1,1,1,3,3,4,3,2,4,2];
containsDuplicateWithFrequencyArray(nums3); //output: true
function containsDuplicateWithSortingAndHelper(nums) {
if (nums.length < 1 || nums.length > 10**5) {
throw new Error("Array length out of bounds.");
}
nums.sort((a, b) => a - b);
const hasDuplicate = (arr) => {
for (let i = 1; i < arr.length; i++) {
if (arr[i] === arr[i - 1]) {
return true;
}
}
return false;
};
return hasDuplicate(nums);
}
const array1 = [1,2,3,1];
containsDuplicateWithSortingAndHelper(array1); //output: true
const nums2 = [1,2,3,4];
containsDuplicateWithSortingAndHelper(nums2); //output: false
const nums3 = [1,1,1,3,3,4,3,2,4,2];
containsDuplicateWithSortingAndHelper(nums3); //output: true
function containsDuplicateTrie(nums) {
const root = new TrieNode();
function insert(num) {
let currentNode = root;
const bitSize = 32;
let isDuplicate = true;
for (let bit = 0; bit < bitSize; bit++) {
const mask = 1 << bit;
const setBit = (num & mask) !== 0 ? 1 : 0;
if (!(setBit in currentNode.children)) {
isDuplicate = false;
currentNode.children[setBit] = new TrieNode();
}
currentNode = currentNode.children[setBit];
}
if (isDuplicate) {
isDuplicate = currentNode.isEnd;
}
currentNode.isEnd = true;
return isDuplicate;
}
for (const num of nums) {
if (insert(num)) {
return true;
}
}
return false;
}
class TrieNode {
constructor() {
this.children = {}; // Maximum size could be 2, since we only care about bits 0 and 1
this.isEnd = false;
}
}
const array1 = [1,2,3,1];
containsDuplicateTrie(array1); //output: true
const nums2 = [1,2,3,4];
containsDuplicateTrie(nums2); //output: false
const nums3 = [1,1,1,3,3,4,3,2,4,2];
containsDuplicateTrie(nums3); //output: true
function containsDuplicateHeapBased(nums) {
let start = Math.floor(nums.length / 2);
let end = nums.length;
while (end > 1) {
if (start > 0) {
start -= 1;
} else {
if (end < nums.length && nums[0] === nums[end]) {
return true;
}
end -= 1;
[nums[0], nums[end]] = [nums[end], nums[0]]; // Swap elements
}
let root = start;
while ((2 * root + 1) < end) {
let child = (2 * root + 1);
if (child + 1 < end && nums[child] < nums[child + 1]) {
child = child + 1;
}
if (nums[root] < nums[child]) {
[nums[root], nums[child]] = [nums[child], nums[root]]; // Swap elements
root = child;
} else if (nums[root] === nums[child]) {
return true;
} else {
break;
}
}
}
return false;
}
const array1 = [1,2,3,1];
containsDuplicateHeapBased(array1); //output: true
const nums2 = [1,2,3,4];
containsDuplicateHeapBased(nums2); //output: false
const nums3 = [1,1,1,3,3,4,3,2,4,2];
containsDuplicateHeapBased(nums3); //output: true
function containsDuplicateDivide(numbers) {
try {
const elementCounts = getElementsCount(numbers);
return elementCounts.some(([_, count]) => count > 1);
} catch (error) {
console.error(`[ERROR] containsDuplicate: ${error}`);
return false;
}
}
function countNumbers(numbers, low, high, table) {
if (high - low === 1) {
const num = numbers[low];
table[num] = (table[num] || 0) + 1;
return;
}
const mid = Math.floor((high + low) / 2);
countNumbers(numbers, low, mid, table);
countNumbers(numbers, mid, high, table);
}
function getElementsCount(numbers) {
const mappingTable = {};
countNumbers(numbers, 0, numbers.length, mappingTable);
return Object.entries(mappingTable);
}
const array1 = [1,2,3,1];
containsDuplicateDivide(array1); //output: true
const nums2 = [1,2,3,4];
containsDuplicateDivide(nums2); //output: false
const nums3 = [1,1,1,3,3,4,3,2,4,2];
containsDuplicateDivide(nums3); //output: true
function containsDuplicateMergeSort(nums) {
mergeSort(nums, 0, nums.length - 1);
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i] === nums[i + 1]) return true;
}
return false;
}
function mergeSort(nums, l, r) {
if (l >= r) return;
const mid = Math.floor((l + r) / 2);
mergeSort(nums, l, mid);
mergeSort(nums, mid + 1, r);
const temp = new Array(r - l + 1);
let a = l, b = mid + 1, count = 0;
while (a <= mid && b <= r) {
if (nums[a] <= nums[b]) {
temp[count++] = nums[a++];
} else {
temp[count++] = nums[b++];
}
}
while (a <= mid) temp[count++] = nums[a++];
while (b <= r) temp[count++] = nums[b++];
for (let i = 0; i < count; i++) {
nums[l + i] = temp[i];
}
}
const array1 = [1,2,3,1];
containsDuplicateMergeSort(array1); //output: true
const nums2 = [1,2,3,4];
containsDuplicateMergeSort(nums2); //output: false
const nums3 = [1,1,1,3,3,4,3,2,4,2];
containsDuplicateMergeSort(nums3); //output: true