[Leetcode] Remove Duplicates from Sorted Array

Posted on by

Problem

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 in place with constant memory.
For example,
Given input array 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 new length.

Analysis

  • Keep track of the right positive to write the valid number, it is also the length of the valid numbers
  • Keep track of current number
    • Write it to the array only when it is different from next number
  • Time: O(n)
  • Extra space: O(1)

Code

Leave a Reply