Remove Duplicates from Sorted Array

Problem Description

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Key Insights

• The input array is sorted, which allows us to use a two-pointer technique to efficiently identify unique elements.
• We can overwrite duplicates in the array while maintaining the order of unique elements.
• The remaining elements beyond the first k unique elements can be ignored.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in the array. Space Complexity: O(1), since we are modifying the array in place and not using additional data structures.

Solution

We will use a two-pointer technique:

1. Use one pointer to iterate through the array (the reader).
2. Use another pointer to track the position where the next unique element should be placed (the writer).
3. If the current element is different from the last unique element found, we place it at the writer's position and increment the writer pointer.
4. Finally, the writer pointer will represent the number of unique elements.

Code Solutions