educative.io

Proposed solution

Courses
,
#1

@Educative_Admin, I’d like to propose a better solution.

The provided solution doesn’t fully satisfy the problem statement, as it doesn’t remove all duplicates. This is fixed with setting the original array to the shortened slice. The slice operation is O(n) however, causing the complexity to be O(n+n), asymptotically O(n).

A simpler solution starts the indexes at the end of the array and utilizes pop() which has an O(1) complexity. Pro’s:

  • Fully satisfies the problem statement without an extra step
  • It’s easier to understand and follow
  • It has a true O(n) complexity

def remove_duplicates(arr):
right_p = len(arr) - 1
left_p = right_p - 1

for i in range(len(arr)-1):
    if arr[left_p] == arr[right_p]:
        arr.pop(right_p)
    left_p -= 1
    right_p -= 1
return len(arr)
1 Like
#2

Popping from the middle of the array is an O(k) operation. So our time complexity could actually be O(n * k) if we had a long array with many duplicates in the center.

Also, pop is a list operation, not an array method. In other languages, given a true array, you won’t have that method, so it is not language-agnostic.

1 Like