Remove duplicates from sorted array in place

0 / 247
remove duplicates

Problem Statement

 

Given an array of sorted numbers, remove all duplicates from it. You should not use any extra space; after removing the duplicates in-place return the new length of the array.

 
 
Example 1:

 

Input: [2, 3, 3, 3, 6, 9, 9]

Output: 4

Explanation: The first four elements after removing the duplicates will be [2, 3, 6, 9].

Example 2:

 

Input: [2, 2, 2, 11]

Output: 2

Explanation: The first two elements after removing the duplicates will be [2, 11].
 
 

Solution

 

In this problem, we need to remove the duplicates in-place such that the resultant length of the array remains sorted. As the input array is sorted, therefore, one way to do this is to shift the elements left whenever we encounter duplicates. In other words, we will keep one pointer for iterating the array and one pointer for placing the next non-duplicate number. So our algorithm will be to iterate the array and whenever we see a non-duplicate number we move it next to the last non-duplicate number we’ve seen.

 

Here is the visual representation of this algorithm:

 
 

remove duplicates

remove duplicates

 

 

Below is how the code will look like in javascript

 

 

<script>

function remove_duplicates(arr) {
  // index of the next non-duplicate element
  let nextNonDuplicate = 1;

  let i = 1;
  while (i < arr.length) {
    if (arr[nextNonDuplicate - 1] !== arr[i]) {
      arr[nextNonDuplicate] = arr[i];
      nextNonDuplicate += 1;
    }
    i += 1;
  }

  return nextNonDuplicate;
}


document.write(remove_duplicates([2, 3, 3, 3, 6, 9, 9])+'<br/>');
document.write(remove_duplicates([2, 2, 2, 11])+'<br/>');

</script>

 

Time Complexity 

 

The time complexity of the above algorithm will be O(N), where ‘N’ is the total number of elements in the given array.

Space Complexity

 

The algorithm runs in constant space O(1).

 
 

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.

Related Posts