Zero out duplicates and sort an array
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
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.
Input: ([4],)
Expected Output: [4]
Explanation: A single element has no duplicates, so the array is unchanged after sorting.
Input: ([4, 4, 4, 4],)
Expected Output: [0, 0, 0, 4]
Explanation: Only the first 4 is kept; the other three become 0, then the array is sorted.
Input: ([-1, 3, -1, 2, 3],)
Expected Output: [-1, 0, 0, 2, 3]
Explanation: After zeroing later -1 and 3 values, the array becomes [-1, 3, 0, 2, 0], which sorts to [-1, 0, 0, 2, 3].
Input: ([0, 2, 0, 2, 1],)
Expected Output: [0, 0, 0, 1, 2]
Explanation: Keep the first 0 and first 2. Later 0 and 2 are duplicates and become 0, giving [0, 2, 0, 0, 1], then sort.
Input: ([5, 3, 4, 1, 2],)
Expected Output: [1, 2, 3, 4, 5]
Explanation: All values are unique, so the task reduces to sorting the array without built-in sort utilities.
Solution
def solution(arr):
if isinstance(arr, tuple) and len(arr) == 1 and isinstance(arr[0], list):
arr = arr[0]
seen = set()
transformed = []
for value in arr:
if value in seen:
transformed.append(0)
else:
seen.add(value)
transformed.append(value)
temp = [0] * len(transformed)
def merge_sort(left, right):
if right - left <= 1:
return
mid = (left + right) // 2
merge_sort(left, mid)
merge_sort(mid, right)
i = left
j = mid
k = left
while i < mid and j < right:
if transformed[i] <= transformed[j]:
temp[k] = transformed[i]
i += 1
else:
temp[k] = transformed[j]
j += 1
k += 1
while i < mid:
temp[k] = transformed[i]
i += 1
k += 1
while j < right:
temp[k] = transformed[j]
j += 1
k += 1
for idx in range(left, right):
transformed[idx] = temp[idx]
merge_sort(0, len(transformed))
return transformedTime complexity: O(n log n). Space complexity: O(n).
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.