Zero out duplicates and sort an array
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## 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]`
Quick Answer: This question evaluates proficiency in array manipulation, duplicate handling, and custom sorting logic with attention to time and space complexity, and it falls within the Coding & Algorithms domain.
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
Examples
Input: ([3, 1, 3, 2, 2],)
Expected Output: [0, 0, 1, 2, 3]
Explanation: Keep the first 3 and first 2, replace later duplicates with 0 to get [3, 1, 0, 2, 0], then sort.
Input: ([],)
Expected Output: []
Explanation: An empty array stays empty.
Hints
- Use a hash set while scanning from left to right to decide whether a value has already appeared.
- Once the array is transformed, implement an O(n log n) sorting algorithm yourself, such as merge sort.