JavaScript Algorithms: Find All Duplicates in an Array (LeetCode)
Description
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.
Could you do it without extra space and in O(n) runtime?
Example:
Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]Solution
The first solution that comes to my mind was two nested for loops:
The time complexity is O(n²) and space complexity is O(1). However, we need to do that with linear time complexity.
The second solution that I came up with is to count all characters using a map and after that loop through it and push to result all characters with a number greater than 1.
The time complexity is O(n) as well as space complexity. We’ve done it but still not good enough. Let’s think about how we can solve it without extra memory and with linear time…
The hint was in the description above. Given an array of integers, 1 ≤ a[i] ≤ n. If we start from 1 we can say that 1 is the index of this item. So, let’s imagine we have an array of indexes starting from 1. How we can find all elements which appear only twice? We can mark each nums[index] their negative copy. And as we decided index will be nums[i].
I know, it looks very tricky. Let’s go through this solution with Example 1:
The time complexity is linear and space complexity is constant as we wanted.
I hope, it was useful for you. Thanks for reading! Looking forward to your feedback. See you soon ✌️
