Grokking the Coding Interview: Patterns for Coding Questions
Vote

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!
Nash Luffman

Nash Luffman

· 3 years ago

It's possible to track the duplicates while performing the cyclic sort. I think this is preferable to iterating over the array twice. The algorithm looks the exact same as Find the Duplicate Number, except instead of returning when a duplicate is found, you add it to the output array.

R

Richard Yuan

· 4 years ago

For the first example, the input array after a cycle sort is performed on it is [5, 4, 3,4, 5]. In the python3 example, performing another iteration to track the duplicates will result in an answer of [5, 4] rather than [4, 5] in case the order of the answer matters to the question.

Show 1 reply
V

vetaranto

· 2 years ago

"Each element in nums appears once or twice"

Enrique Fernández

Enrique Fernández

· 2 years ago

class Solution:
  def findNumbers(self, nums):
    duplicateNumbers = []
    # TODO: Write your code here
    i, n = 0, len(nums)
    while i < n:
      num = nums[i]
      if num != nums[num - 1]:
        nums[i], nums[num - 1] = nums[num - 1], nums[i]
      else:
        if num != i + 1:
          duplicateNumbers.append(num)
        i += 1
        
    return duplicateNumbers
J

Joe

· 2 years ago

It would seem both Find the Duplicate Number and Find all Duplicate Numbers should be the same solution only this time capturing a list for all dupes. However the duplicate number has the line:

  `if nums[i] != i + 1:  # Check if the current element is in its correct position`

Why does this solution work without this and the previous problem does not if they are essentially the same problem?

G

Gary

· 4 years ago

When I try [3, 1, 3, 4, 2] as the input, the nums list looks like [1, 2, 3, 4, 3] after running through the while loop in the solution, which does not appear to be sorted correctly even though the results are correct?

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findNumbers(self, nums):
    duplicates = []

    def swap(i, j):
      nums[i], nums[j] = nums[j], nums[i]

    for i in range(len(nums)):
      # keep swaping while item is not in position and not pointing to an index that has an item that is in position
      while nums[i] != i + 1 and nums[i] != nums[nums[i] - 1]:
        swap(i, nums[i] - 1)

    # if an item is not at the right index add it to the result
    for i in range(len(nums)):
      if nums[i] != i + 1:
        duplicates.append(nums[i])

    return duplicates