Zero out duplicates and sort an array

Coding question

You are given an integer array arr of length about 75.

• The data is not sorted.
• The array may contain duplicate values.
• You must zero out duplicates and then sort the array.
• Try to keep time and space complexity in mind.
• Do not use built-in/native sorting utilities (e.g., sort()), and do not call library implementations of quicksort/bubblesort/etc.

Clarification to assume (if not specified)

If a value appears multiple times, keep exactly one occurrence and replace all other occurrences with 0. Then sort the entire array in non-decreasing order.

Input

• An integer array arr.

Output

• Return the transformed array after (1) zeroing duplicate occurrences and (2) sorting.

Example

• Input: [3, 1, 3, 2, 2]
• After zeroing duplicates (keeping first occurrence): [3, 1, 0, 2, 0]
• After sorting: [0, 0, 1, 2, 3]

Zero Out Duplicates and Sort an Array

You are given an integer array arr. Traverse the array from left to right and keep the first occurrence of each value. Every later occurrence of the same value must be replaced with 0. After that, sort the entire resulting array in non-decreasing order and return it.

Do not use built-in sorting utilities such as sort() or sorted(); implement the sorting yourself.

Note: if the duplicated value is 0, replacing it with 0 does not change its appearance, but it is still considered a duplicate occurrence.

Constraints

• 0 <= len(arr) <= 100000; the interview version often uses arrays of around 75 elements
• -1000000000 <= arr[i] <= 1000000000
• Keep the first occurrence of each value and replace every later duplicate with 0
• Do not use built-in/native sorting utilities

Hints

1. Use a hash set while scanning from left to right to decide whether a value has already appeared.
2. Once the array is transformed, implement an O(n log n) sorting algorithm yourself, such as merge sort.