Back to ArraysFind All Duplicates in an Array
Medium

Find All Duplicates in an Array

MediumRecommendedIndex MarkingHashing

Given an array of n integers where every value is between 1 and n and each value appears once or twice, return every value that appears twice, using only O(1) extra space beyond the output.

Examples

Example 1

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

Explanation: 2 and 3 each appear twice in the array; every other value from 1-8 appears exactly once.

Example 2

Input:
nums = [1,1,2]
Output:
[1]

Explanation: Only 1 is repeated.

Example 3

Input:
nums = [1,2,3]
Output:
[]

Explanation: No value repeats, so no duplicates are reported.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= nums.length
  • Each value appears once or twice.
  • This approach mutates the input array in place while scanning it.

Follow-up

How would you restore the input array to its original values after collecting the duplicates, and why might a caller want that?

Loading editor…

Code execution is coming soon.