Home/

...

/

Find all Duplicate Numbers (easy)

Find all Duplicate Numbers (easy)

Dry-run templates

This is the implementation of the solution provided for the problem posed in the Find all Duplicate Numbers (easy) lesson:

Press + to interact
Python 3.5
def find_all_duplicates(nums):
  i = 0
  while i < len(nums):
    j = nums[i] - 1
    if nums[i] != nums[j]:
      nums[i], nums[j] = nums[j], nums[i]  # swap
    else:
      i += 1
  duplicateNumbers = []
  for i in range(len(nums)):
    if nums[i] != i + 1:
      duplicateNumbers.append(nums[i])
  return duplicateNumbers
def main():
  print(find_all_duplicates([3, 4, 4, 5, 5]))
  print(find_all_duplicates([5, 4, 7, 2, 3, 5, 3]))
main()

Students may be encouraged to run through the provided solution with the following sample inputs:

Sample Input #1

nums: [1,4,4,3,2,5,6,6,7]

Iteration No.

Line No.

i

j

nums[i]

nums[j]

nums

duplicateNumbers

-

2

0

-

-

-

[1,4,4,3,2,5,6,6,7]

-

1

5

0

0

1

1

[1,4,4,3,2,5,6,6,7]

-

2

5

1

3

4

3

[1,4,4,3,2,5,6,6,7]

-

2

6

1

3

4

3

[1, 3, 4, 4, 2, 5, 6, 6, 7]

-

3

5

1

2

3

4

[1, 3, 4, 4, 2, 5, 6, 6, 7]

-

3

6

1

2

3

4

[1, 4, 3, 4, 2, 5, 6, 6, 7]

-

4

5

1

3

4

4

[1, 4, 3, 4, 2, 5, 6, 6, 7]

-

5

5

2

2

3

3

[1, 4, 3, 4, 2, 5, 6, 6, 7]

-

6

5

3

3

4

4

[1, 4, 3, 4, 2, 5, 6, 6, 7]

-

7

5

4

1

2

4

[1, 4, 3, 4, 2, 5, 6, 6, 7]

-

7

6

4

1

2

4

[1, 2, 3, 4, 4, 5, 6, 6, 7]


8

5

4

3

4

4

[1, 2, 3, 4, 4, 5, 6, 6, 7]

-

9

5

5

4

5

4

[1, 2, 3, 4, 4, 5, 6, 6, 7]

-

9

6

5

4

5

4

[1, 2, 3, 4, 5, 4, 6, 6, 7]

-

10

5

5

3

4

4

[1, 2, 3, 4, 5, 4, 6, 6, 7]

-

11

5

6

5

6

4

[1, 2, 3, 4, 5, 4, 6, 6, 7]

-

11

6

6

5

6

4

[1, 2, 3, 4, 5, 6, 4, 6, 7]


12

5

6

3

4

4

[1, 2, 3, 4, 5, 6, 4, 6, 7]

-

13

5

7

5

6

6

[1, 2, 3, 4, 5, 6, 4, 6, 7]

-

14

5

8

6

7

4

[1, 2, 3, 4, 5, 6, 4, 6, 7]

-

14

6

8

6

7

4

[1, 2, 3, 4, 5, 6, 7, 6, 4]

-

15

5

8

3

4

4

[1, 2, 3, 4, 5, 6, 7, 6, 4]

-

1

13

8

-

6

-

[1, 2, 3, 4, 5, 6, 7, 6, 4]

[6]

2

13

9

-

4

-

[1, 2, 3, 4, 5, 6, 7, 6, 4]

[6,4]

Sample Input #2

Students may be encouraged to complete the dry-run with this input:

nums: [1,1,2,2,3,3]

Iteration No.

Line No.

i

j

nums[i]

num[j]

nums

duplicateNumbers

-

2

0

-

-

-

[1,1,2,2,3,3]

-

1

5

0

0

1

1

[1,1,2,2,3,3]

-

2

5

1

0

1

1

[1,1,2,2,3,3]

-

3

5

2

1

2

1

[1,1,2,2,3,3]

-

3

5

2

1

2

1

[1, 2, 1, 2, 3, 3]

-

...

...

...

...

...

...

....

...

Step-by-step solution construction

The solution requires two steps:

  1. Cyclic sort (lines 3-15): Place the first occurrence of each number n in nums at the index n-1(lines 9-11). Duplicate occurrence of any number will be placed after index len(nums) - max(nums)-1. This will happen when we swap a number to bring it to its correct position at line 11.

Press + to interact
Python 3.5
def find_all_duplicates(nums):
  i = 0
  while i < len(nums):
    j = nums[i] - 1
    print("\ti:",i, end="")
    print("\t\tnums[", i, "]: ", nums[i], sep="")
    print("\tj:",j, end="")
    print("\t\tnums[", j, "]: ", nums[j], sep="")
    if nums[i] != nums[j]:
      print("\tElement not in its place. --> Swapping " + str(nums[i]) + " and " + str(nums[j]))
      nums[i], nums[j] = nums[j], nums[i]  # swap
      print("\tnums after swap: " + str(nums))
    else:
      print("\tSame values, no need to swap.")
      i += 1
  print("\tnums after the cyclic sort",nums,sep=":")
  duplicateNumbers = []
  return duplicateNumbers
def main():
  nums_arr = [[1,4,4,3,2,5,6,6,7],[1,2,3,4,5,6]]
  for i in nums_arr:
    print("Find duplicates in " + str(i))
    result = find_all_duplicates(i)
    print("Duplicates are: " + str(result))
    print(("-"*100)+"\n")
main()
  1. Once nums is sorted cyclically, the following property will be true for each of its index i

nums[i] = i+1, otherwise, nums[i] is a duplicate number.

Now, scan nums from left to right and add nums[i] to the duplicateNumbers whenever nums[i] != i+1 (lines 19-25).

Press + to interact
Python 3.5
def find_all_duplicates(nums):
  i = 0
  while i < len(nums):
    j = nums[i] - 1
    print("\ti:",i, end="")
    print("\t\tnums[", i, "]: ", nums[i], sep="")
    print("\tj:",j, end="")
    print("\t\tnums[", j, "]: ", nums[j], sep="")
    if nums[i] != nums[j]:
      print("\tElement not in its place. --> Swapping " + str(nums[i]) + " and " + str(nums[j]))
      nums[i], nums[j] = nums[j], nums[i]  # swap
      print("\tnums after swap: " + str(nums))
    else:
      print("\tSame values, no need to swap.")
      i += 1
  print("\tnums after the cyclic sort",nums,sep=":")
  duplicateNumbers = []
  print("\tTraversing " + str(nums) + " to find duplicate numbers")
  for i in range(len(nums)):
    print("\tComparing value ("+str(nums[i]) + ") with place (" + str(i+1) + ")")
    if nums[i] != i + 1:
      print("\tDuplicate FOUND --> Appending " + str(nums[i]) + " to duplicateNumbers")
      duplicateNumbers.append(nums[i])
    else:
      print("\tNo duplicate found at index: " + str(i+1))
  return duplicateNumbers
def main():
  nums_arr = [[1,4,4,3,2,5,6,6,7],[1,2,3,4,5,6]]
  for i in nums_arr:
    print("Find duplicates in " + str(i))
    result = find_all_duplicates(i)
    print("Duplicates are: " + str(result))
    print(("-"*100)+"\n")
main()