Sponsored
Sponsored
The two-pointer technique is an efficient way to solve this problem in-place. We initialize two pointers, where one (called slow) tracks the position of unique elements, and the other (called fast) traverses the entire array.
Whenever we find a new unique element using the fast pointer, we move the slow pointer one step forward and place the unique element at that position. This way, the array elements from index 0 to the slow pointer are all unique.
Time Complexity: O(n), where n is the number of elements in the array, since each of the n elements is accessed once.
Space Complexity: O(1), since the solution uses only a constant amount of extra space.
1function removeDuplicates(nums) {
2 if (nums.length === 0) return 0;
3 let j = 0;
4 for (let i = 1; i < nums.length; i++) {
5 if (nums[i] !== nums[j]) {
6 j++;
7 nums[j] = nums[i];
8 }
9 }
10 return j + 1;
11}
12
13let nums = [0,0,1,1,1,2,2,3,3,4];
14let k = removeDuplicates(nums);
15console.log(`${k}, nums = [${nums.slice(0, k).join(',')}]`);The solution implements a dual-pointer technique using iterative logic. The array is modified in-place using the index of j for placement of unique elements found by i.
An alternative approach without pointers uses a simple loop to iterate over the array and compare each element with the previous one. The still unique elements overwrite duplicate positions directly in the initial part of the array.
Time Complexity: O(n)
Space Complexity: O(1)
1
This approach iterates from the second element, comparing it with its predecessor to check duplicates and copying only non-duplicates towards the start.