Consider the following LeetCode problem.
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), ?>some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Example:
Input:
[4,3,2,7,8,2,3,1]Output:
[2,3]
I will present a few solutions to the problem in JavaScript, though I know there are some better options out there. My first approach was to create an empty object, run the array through a for loop, and count every instance of each number. Because the problems wants us to only return elements that appear twice, we would then filter the object by values equal to 2 and return the relevant keys. This looked like:
var findDuplicates = function(nums) {
let count = {}
for(const num of nums){
if (!count[num]){
count[num] = 1
} else {
count[num]++
}
}
let keys = Object.keys(count)
return keys.filter(x => count[x] === 2)
};
According to LeetCode, this took 132ms and registered a memory usage of 53MB. In contrast to other LeetCode submissions, this beat 60.12% of JS submission with runtime, but only 8.39% in terms of memory usage.
One initial change I wanted to make was to change the if/else in the for-loop, reducing it to one line:
count[num] = 1 + (count[num] || 0)
Oddly, this came back with a runtime of 148ms and a memory usage of 53.6 MB.
My first alternate solution addressed memory, and I chose to modify the array in place by first sorting the array and then iterating over it by comparing values and splicing duplicates and unique values. We know this will work because duplicates appear no more than twice according to the directions; if this stipulation was not in place, we would need another comparison that looks father ahead (something like nums[i] !== nums[i + 2]
).
var findDuplicates = function(nums) {
nums.sort();
for (let i = 0; i < nums.length; i++){
if (nums[i] === nums[i + 1]){
nums.splice(i + 1, 1)
} else {
nums.splice(i, 1)
i--;
}
}
return nums;
}
Once again, this works but produces a runtime of 1204ms beating only 10.12% of JS submissions, but improves a bit on memory usage, using only 47.7 MB, beating 37.52% of JS submissions.
Looking to come up with a one-line solution, I took the same logic from the previous submission and filtered the array.
var findDuplicates = function(nums){
return nums.sort().filter((val, idx, arr) => arr[idx - 1] === val);
}
This improved on the previous submission's runtime: 168 ms, beating 34.12% of JS submissions. Memory usage was 46.8 MB, beating just under 50% of other JS submission; this was our best bet in memory usage so far.
None of these are the fastest or most efficient solutions, but it is good to see different possibilities and I will keep working on something better and faster.
Top comments (1)
how to find duplicate in this type of arrays, please help
arr=[
“Pakistan”,
“pakistan”,
“paKISTAN”,
“USA”,
“INDIA”,
“LONDON”,
“PATOKI”,
“Patoki”,
“Brazil”,
“CaNada”,
“canada”,
]