Remove Duplicates from Sorted Array
LeetCode #26 · Easy · Arrays · C++ solution with worked-out approach and complexity analysis.
Approach
Two-pointer (fast-slow)
Use 'uniq' as the position to write the next unique element. Iterate through the array; when we find a value greater than the last unique value, we write it to nums[uniq] and increment uniq. This works because the array is sorted.
Time
O(n)
Space
O(1)
Problem description(from LeetCode)
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. Do not allocate extra space for another array; you must do this by modifying the input array in-place with O(1) extra memory.
Examples
Example 1
- Input:
- nums = [1,1,2]
- Output:
- 2, nums = [1,2,_]
- Note:
- Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively. It does not matter what you leave beyond the returned k.
Constraints
- •1 <= nums.length <= 3 * 10^4
- •-10^4 <= nums[i] <= 10^4
- •nums is sorted in non-decreasing order.
C++ Solution
solution.cpp
class Solution {
public:
int removeDuplicates(vector<int> &nums) {
int uniq = 0;
int curr = INT_MIN; // sentinel smaller than any possible value
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] > curr) {
curr = nums[i];
nums[uniq] = nums[i];
uniq++;
}
}
return uniq;
}
};