Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Find all Duplicate Numbers

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 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
A

Anonymous

· 3 years ago

"Each element in nums appears once or twice"

A

Anonymous

· 3 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?

A

Anonymous

· 4 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.

Show 2 replies
A

Anonymous

· 5 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
A

Anonymous

· 5 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

Reading Progress

0%

Vote for new content