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.
1public class RemoveDuplicates {
2 public int removeDuplicates(int[] nums) {
3 if (nums.length == 0) return 0;
4 int j = 0;
5 for (int i = 1; i < nums.length; i++) {
6 if (nums[i] != nums[j]) {
7 j++;
8 nums[j] = nums[i];
9 }
10 }
11 return j + 1;
12 }
13
14 public static void main(String[] args) {
15 RemoveDuplicates solution = new RemoveDuplicates();
16 int[] nums = {0,0,1,1,1,2,2,3,3,4};
17 int k = solution.removeDuplicates(nums);
18 System.out.print(k + ", nums = [");
19 for (int i = 0; i < k; i++) {
20 System.out.print(nums[i] + (i < k - 1 ? "," : ""));
21 }
22 System.out.println("]");
23 }
24}The Java solution follows the same logic, using two pointers, one to iterate through the array and the other to keep track of the position to fill with 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.