Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Solution: Find all Duplicate Numbers

Problem Statement

We are given an unsorted array containing n numbers taken from the range 1 to n. The array has some numbers appearing twice, find all these duplicate numbers using constant space.

Example 1:

Input: [3, 4, 4, 5, 5]
Output: [4, 5]

Example 2:

Input: [5, 4, 7, 2, 3, 5, 3]
Output: [3, 5]

Constraints:

nums.length == n
1 <= n <= $10^5$
1 <= nums[i] <= n
Each element in nums appears once or twice.

Solution

This problem follows the Cyclic Sort pattern and shares similarities with Find the Duplicate Number

.....

.....

.....

Like the course? Get enrolled and start learning!