Algorithm Gymnastics 20 Remove Duplicates

Remove Duplicates

An array of sorted numbers is passed as an argument to remove all duplicates from it. No new data structure used After removing the duplicates in-place, it returns the new length of the array.

Example

Input: [2, 3, 3, 3, 6, 9, 9] Output: 4 ([2, 3, 6, 9])

Input: [2, 2, 2, 11] Output: 2 ([2, 11])

Solution

# The time complexity: O(N)
# Space Complexity: O(1)

def remove_duplicates(arr):
  # index of the next non-duplicate element
  next_non_duplicate = 1

  i = 1
  while(i < len(arr)):
    if arr[next_non_duplicate - 1] != arr[i]:
      arr[next_non_duplicate] = arr[i]
      next_non_duplicate += 1
    i += 1

  return next_non_duplicate

Similar

Specifies an array of unsorted numbers and the target "key", removes all elements that match the "key", and returns the new length of the array.

Example

Input: [3, 2, 3, 6, 3, 10, 9, 3], Key=3 Output: 4 ([2, 6, 10, 9])

Input: [2, 11, 2, 2, 1], Key=2 Output: 2 ([11, 1])

Implementation

# The time complexity: O(N)
# Space Complexity: O(1)

def remove_element(arr, key):
  nextElement = 0  # index of the next element which is not 'key'
  for i in range(len(arr)):
    if arr[i] != key:
      arr[nextElement] = arr[i]
      nextElement += 1

  return nextElement