Remove Duplicates from Sorted Array
(#26), Easy
Category: Array, Two Pointer
Problem Statement
You’re given a sorted array of integers. You need to remove duplicates in-place so that each element appears only once. Return the number of unique elements `k`, and modify the input array such that the first `k` elements are the unique ones. Their order should be preserved. Values beyond index `k-1` can be ignored.
Examples
Input: nums = [1, 1, 2]
Output: 2
Explanation: Modified array becomes [1, 2, _]. Only first 2 elements matter.
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5
Explanation: Modified array becomes [0,1,2,3,4,_,_,_,_,_]. First 5 elements are unique.
Approach
Two Pointer Approach
- Initialize `first = 0` and `sec = 1`.
- `first` tracks the position of the last unique element.
- `sec` scans the array for the next unique element.
- If a new unique value is found at `sec`, increment `first`, then swap `nums[first]` and `nums[sec]`.
- At the end of the loop, return `first + 1` as the number of unique elements.
var removeDuplicates = function (nums) {
let first = 0;
let sec = 1;
while (sec < nums.length) {
if (nums[first] === nums[sec]) {
sec++;
} else {
first++;
[nums[first], nums[sec]] = [nums[sec], nums[first]];
sec++;
}
}
console.log(nums.slice(0, first + 1)); // Shows the unique values
return first + 1;
};
console.log(removeDuplicates([0,0,1,1,1,2,2,3,3,4])); // Output: 5Complexity
Time: O(n) – one pass through the array.
Space: O(1) – in-place solution using no extra space.