Solution


Approach 1: Two Pointers

Algorithm

Since the array is already sorted, we can keep two pointers and , where is the slow-runner while is the fast-runner. As long as , we increment to skip the duplicate.

When we encounter , the duplicate run has ended so we must copy its value to . is then incremented and we repeat the same process again until reaches the end of array.

Complexity analysis

  • Time complextiy : . Assume that is the length of array. Each of and traverses at most steps.

  • Space complexity : .