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.
1#include <stdio.h>
2
3int removeDuplicates(int* nums, int numsSize) {
4 if (numsSize == 0) return 0;
5 int j = 0;
6 for (int i = 1; i < numsSize; i++) {
7 if (nums[i] != nums[j]) {
8 j++;
9 nums[j] = nums[i];
10 }
11 }
12 return j + 1;
13}
14
15int main() {
16 int nums[] = {0,0,1,1,1,2,2,3,3,4};
17 int size = sizeof(nums) / sizeof(nums[0]);
18 int k = removeDuplicates(nums, size);
19 printf("%d, nums = [", k);
20 for (int i = 0; i < k; i++) {
21 printf("%d%s", nums[i], (i == k - 1) ? "" : ",");
22 }
23 printf("]\n");
24 return 0;
25}We start with the assumption that the array has at least one element if it's non-empty. We initialize two indices: j which tracks the last position of unique elements and starts at 0, and i, which iterates from 1 to the end of the array.
Whenever a non-duplicate element is found by comparing nums[i] with nums[j], j is incremented, and nums[j] is updated with nums[i]. Finally, we return j + 1 as it represents the count of unique elements.
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.