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
  • we iterate the array only once

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

Last updated