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.
1def removeDuplicates(nums):
2 if not nums:
3 return 0
4 j = 0
5 for i in range(1, len(nums)):
6 if nums[i] != nums[j]:
7 j += 1
8 nums[j] = nums[i]
9 return j + 1
10
11nums = [0,0,1,1,1,2,2,3,3,4]
12k = removeDuplicates(nums)
13print(f"{k}, nums = {nums[:k]}")In Python, we iterate using a for loop and compare each element with the last found unique element. The unique elements are stored in place, updating the existing array.
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.