Remove Duplicates from Sorted Array

Deepak Sikka
2 min readMar 25, 2021

Question:

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2],Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.It doesn't matter what you leave beyond the returned length.

Solution:

In this problem, the key point to focus on is the input array being sorted. As far as duplicate elements are concerned, what is their positioning in the array when the given array is sorted? Look at the image above for the answer. If we know the position of one of the elements, do we also know the positioning of all the duplicate elements?

Hence, we will solve this problem by using two pointers sliding window pattern. We’ll keep two pointers (indexes) -

  • One index i, to iterate over the array, and
  • Another index j, to keep track of the number of unique elements found so far. This index will move only when we modify the array in-place to include a new non-duplicate element.
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int j = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[j]) {
j++;
nums[j] = nums[i];
}
}
return j + 1;
}
}

--

--

Deepak Sikka

Senior Android Developer. Working on technology Like Java,Kotlin, JavaScript.Exploring Block Chain technology in simple words.