Remove Duplicates from Sorted Array: using two pointers

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 1122 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s