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: [4,3,2,7,8,2,3,1] Output: [2,3]
Idea:
To solve this in O(1) space and O(n) runtime, we have to do some modification in the original array.
In for loop:
- Flipping the index location number (to negative number)
- when we meet the duplicate number, we should see index location is negative, save the result
Solution:
/**
* @param {number[]} nums
* @return {number[]}
*/
var findDuplicates = function(nums) {
const res = [];
for (let i = 0; i < nums.length; i++) {
let index = Math.abs(nums[i]) - 1;
// flipping the index location number (to negative number)
// if we found they are negative, save the result
if (nums[index] < 0) res.push(index + 1); // because index = ABS(nums[i]) - 1
nums[index] = -nums[index];
}
return res;
};