Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Find all Duplicate Numbers (easy)

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.

Try it yourself

Try solving this question here:

.....

.....

.....

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