Zero out duplicates and sort an array

Q: Zero out duplicates and sort an array

This is a Coding & Algorithms interview question from Apple for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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]