26. Remove Duplicates from Sorted Array

Remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]

Return the number of unique elements in nums.

---

Intuition

• A number is unique if nums[i] != nums[i-1]

• If its not unique we can overwrite it with the next greater element.

Approach

• Start from the beginning with i=0 & j=0

  • i is fast points to current element & j is slow pointing to the previous element.

• Only if the previous pointed element is not equal to the current element we increase j.

  • write current value in its place

Complexity

• Time complexity : $\text{O}(n)$

  • we iterate the array only once

• Space complexity : $\text{O}(1)$

  • we do operation in-place, no extra space needed

Code

public int removeDuplicates(int[] nums) {
	int j = 0;

	for (int i = 0; i < nums.length; ++i) {
		// If the element are not equal only then add to array
		if(nums[i] != nums[j]) {
			nums[++j] = nums[i];
		}
	}
	return j+1;
}

Alternate Solution

Count the number of places to shift each element

public int removeDuplicates(int[] nums) { 
	int shiftPlacesBy = 0; 
	for (int i = 1; i < nums.length; ++i) { 
		// if elements are equal we increase the shift count by
		if(nums[i] == nums[i-1]) { 
			shiftPlacesBy++; 
			continue; 
		} 
		nums[i - shiftPlacesBy] = nums[i]; 
	} 
	return nums.length - shiftPlacesBy; 
} 

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(n)$

• we iterate the array only once

• we do operation in-place, no extra space needed