Remove Duplicates from Sorted Array In-Place

You are given an array of n integers sorted in non-decreasing order, which may contain duplicate values. Remove the duplicates in place so that each unique value appears only once, preserving the sorted order, and report the resulting deduplicated array. Conceptually you should overwrite the input array using two pointers, one scanning ahead and one marking the position of the last unique value written, rather than building a separate output array.

Input: The first line contains the integer n. The second line contains n space-separated integers representing the sorted array (duplicates allowed). Output: Print two lines. On the first line, print k, the number of unique elements remaining. On the second line, print the k unique elements in non-decreasing order, space-separated.

1 <= n <= 10^5 -10^9 <= arr[i] <= 10^9 arr is sorted in non-decreasing order

This 'write pointer trails behind a scanning pointer' technique is a broadly reusable in-place array compaction pattern, reappearing in problems like 'Move Zeroes to the End' with only minor variations.

Remove duplicate values from a sorted array in place, keeping only one copy of each distinct value. Brute force: Use a hash set to track values seen, building a separate output array or list - this works but uses O(n) extra space, when the sorted structure allows an in-place solution using no extra space at all. Optimised: Since the array is SORTED, duplicates are always ADJACENT - a two-pointer approach (one confirming unique writes, one scanning ahead) can compact the array in place in a single pass, without needing any extra hash set or output array.

1. Keep a 'WRITE POINTER' that tracks the last position holding a confirmed-unique value, starting at index 0. 2. Scan the array with a SECOND pointer; whenever you find a value DIFFERENT from the one at the write pointer, advance the write pointer and copy the new value there. 3. Because the array is sorted, all copies of the same value are ADJACENT, so a single left-to-right pass is enough.

Time: O(n) - a single pass through the array. Space: O(1) extra space - the array is modified in place.

Handle n = 1 (already unique), an array where every element is identical (k = 1), and an array with no duplicates at all (k = n); a single O(n) pass must suffice at n = 10^5.

Be ready to explain why this technique specifically REQUIRES sortedness - on an unsorted array, duplicates could be scattered anywhere, requiring a hash set (O(n) space) instead of this O(1)-space two-pointer compaction.