Problem

Given an unsorted integer array arr, remove every duplicate so that each value appears once, keeping the order of first appearance. Return the resulting array (or, in the in-place variant, the number of unique elements after packing them at the front).

Unlike the sorted version, duplicates are not adjacent, so the two-pointer scan alone is not enough.

Input / Output

• Input: integer array arr.
• Output: array of unique values in first-appearance order.

Examples

Example 1 Input: arr = [4, 2, 4, 1, 2, 3, 4] Output: [4, 2, 1, 3]

Example 2 Input: arr = [1, 1, 1] Output: [1]

Example 3 Input: arr = [] Output: []

Constraints

• 0 <= n <= 10^5
• -10^9 <= arr[i] <= 10^9

Approach

Hash set + write pointer (O(n)). Scan left to right with a seen set. Keep a write index w; when a value is not in seen, add it, copy it to arr[w], and increment w. The prefix arr[0..w-1] is the answer, and the relative order is preserved because each value is written the first time it is met.

Sorting (O(n log n), O(1) extra). Sort, then apply the sorted-array dedupe. This loses the original order — acceptable only if the problem does not require it.

Why not nested loops? Comparing each element against every earlier one is O(n²), too slow at 10^5.

The hash-set approach is the one interviewers expect; the follow-up is usually "what if memory is tight?" (answer: sort in place, or a bitset if values are bounded).

Complexity

• Time: O(n) average
• Space: O(k) for the set of distinct values.

Reference solution (Python)

def remove_duplicates_unsorted(arr):
    seen = set()
    w = 0
    for v in arr:
        if v not in seen:
            seen.add(v)
            arr[w] = v
            w += 1
    del arr[w:]
    return arr

Test cases

Input	Expected
[4,2,4,1,2,3,4]	[4,2,1,3]
[1,1,1]	[1]
[]	[]
[3,1,2]	[3,1,2]