Find All Duplicates in an Array Medium 0 attempts
LeetCode ↗

Find All Duplicates in an Array

Medium ArrayTwo Pointers LeetCode

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears at most twice, return an array of all the integers that appears twice. You must write an algorithm that runs in O(n) time and uses only constant extra space.

Sample Input
nums = [4,3,2,7,8,2,3,1]
Sample Output
[2,3]
Constraints
  • n == nums.length
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= n
  • Each element appears once or twice
Test Cases
Case 1
Args: [[4,3,2,7,8,2,3,1]] Expected: [2,3]
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.

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