These two questions were asked in Facebook interview.

**Part I**

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.

**My Solution**

The idea is very simple to get time complexity of O(n). Use the first pointer to point the position which element is being stored to, and the other pointer to iterate the elements. If the current element and the previous element are different, store the current element in the first pointer and move one. Make exception for the first element and in case element is only 0 or 1 size.

def remove_duplicates(nums):
if not nums:
return 0
idx = 0
for i in range(len(nums)):
if i==0 or nums[i] != nums[i-1]:
nums[idx] = nums[i]
idx += 1
return idx

**Part II**

Follow up for “Remove Duplicates”:

What if duplicates are allowed at most *twice*?

For example,

Given sorted array *nums* = `[1,1,1,2,2,3]`

,

Your function should return length = `5`

, with the first five elements of *nums* being `1`

, `1`

, `2`

, `2`

and `3`

. It doesn’t matter what you leave beyond the new length.

**My Solution**

The idea is to skip the middle element and check the previous and next elements. If these are different, store the current element to the position index. The time complexity for this would be O(n).

def max_two_duplicates(nums):
if len(nums) < 3:
return len(nums)
idx = 1
for i in range(1, len(nums)-1):
if nums[i-1] != nums[i+1]:
nums[idx] = nums[i]
idx += 1
# add the last element
nums[idx] = nums[-1]
return idx + 1

### Like this:

Like Loading...

*Related*