Easy · Slow and Fast Pointers
Understand → Visualise → Practice.
Return the unique prefix values obtained by removing duplicates from an ascending array in place.
In a sorted array duplicates are adjacent. A slow pointer marks the end of the unique prefix; a fast pointer copies each new value into it.
Look at each value in order.
If it differs, write it at the slow position and advance slow.
The first slow values are the distinct values in order.
O(n) time and O(1) extra space.
Comparing with the next element instead of the last kept one fails for runs longer than two.
Read the full guide first: Two Pointers and Sliding Windows.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.