Find All Duplicates in an Array Medium 0 attempts
LeetCode ↗

Find All Duplicates in an Array

Medium ArrayTwo Pointers LeetCode

You're given an integer array nums of length n, where every value lies between 1 and n inclusive and each value occurs either once or twice. Return a list of all the values that occur exactly twice. Your solution should run in O(n) time while using only constant extra space.

Input Format
Implement findDuplicates(nums). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. The order of the outer result array does not matter.

Sample Input and Output

Example 1 ยท Run Sample

Input
nums = [4,3,2,7,8,2,3,1]
Output
[2,3]

Example 2

Input
nums = [1]
Output
[]
Constraints
  • n == nums.length
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= n
  • Each element appears once or twice
Test Cases (2)
Case 1
Args: [[4,3,2,7,8,2,3,1]] Expected: [2,3]
Case 2
Args: [[1]] Expected: []
Topics
ArrayTwo Pointers

Since all values are in the range [1, n], use them as indices. For each number, negate the value at that index. If the value is already negative, the number is a duplicate.

javascript
function findDuplicates(nums) {
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    const idx = Math.abs(nums[i]) - 1;
    if (nums[idx] < 0) {
      result.push(idx + 1);
    } else {
      nums[idx] = -nums[idx];
    }
  }

  return result;
}

Time: O(n) Space: O(1) (output array not counted)

Saved in this browser only. Private to you.

JavaScript