You are given a sorted array arr[] containing positive integers. Your task is…

Concept

In a sorted array all copies of the same value sit next to each other in one contiguous block. Therefore a value is a duplicate exactly when it equals the value kept immediately before it — a purely local test that needs no searching and no extra bookkeeping.

This makes in-place compaction with two indices possible: a read index scans every position once, while a separate write index marks the slot where the next distinct value belongs. The write index never runs ahead of the read index: k ≤ i holds at the start of every iteration, and k ≤ i + 1 immediately after a value has been written, with k = i exactly while no duplicate has been seen yet — so the slot written to has always been read already, and no element still waiting to be read is ever overwritten. Sortedness is what licenses the adjacent comparison; on an unsorted array the same one-pass test would be invalid.

Application

1. Read n from the first line, then read the n values of arr[] from the second line.

2. If n is 0 there is nothing to print. Otherwise the first element can never be a duplicate, so keep arr[0] and start the write index at k = 1.

3. Move a read index i from 1 to n - 1, visiting every position exactly once.

4. At each step compare arr[i] with the last value already kept, arr[k - 1].

5. If arr[i] == arr[k - 1], this element repeats the block currently being scanned: skip it and leave k unchanged.

6. If arr[i] != arr[k - 1], a new distinct value has started: write arr[k] = arr[i] and increment k.

7. After the pass the first k slots hold every distinct value in its original order; print those k values on one line, separated by single spaces.

Trace on arr[] = [1, 1, 2, 2, 3] (start: keep arr[0] = 1, k = 1):

The prefix of length k = 3 is [1, 2, 3], so the line printed is 1 2 3.

Cross-check and cost

• arr[] = [2, 2, 2, 2, 2]: after keeping the leading 2, every later element equals arr[k - 1] = 2, so k never moves past 1 and the printed line is 2 — matching the first example.

• arr[] = [1, 2, 4]: each element differs from the one kept before it, so k reaches 3 and all three values are printed unchanged — matching the second example.

• Cost: arr[0] is kept in O(1) before the loop, and the loop then visits each of the remaining n - 1 positions exactly once, doing O(1) work at each — one comparison against arr[k - 1] and at most one write. That gives O(n) time and O(1) auxiliary space overall. With n up to 105 this passes comfortably.

• Contrast with a hash-set approach: a set also removes duplicates but spends O(n) extra memory and discards the very property — sortedness — that makes the single adjacent comparison sufficient here.