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

Recommended Posts

Algorithm Gymnastics 20 Remove Duplicates
Algorithm gymnastics 12
Algorithm gymnastics 10
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm Gymnastics 15
Algorithm Gymnastics 16
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 21 LinkedList Cycle
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 19 No-repeat Substring
Algorithm Gymnastics 24 Reverse a Linked List
Algorithm Gymnastics 20 Pair with Target Sum
Algorithm Gymnastics 22 Squaring a Sorted Array
Algorithm Gymnastics 24 Middle of the Linked List