My O(n^2) solution is showing Time Out

class Solution:
# @param A : list of integers
# @return an integer
def removeDuplicates(self, A):
c=len(A)
q=0
for i in range(c-1):
if A[i-q]==A[i+1-q]:
q+=1
del A[i-q+1]

    return len(A)

Can somebody help me out?

You need to solve in O(n) time complexity, approach is that you first use two pointers technique to place unique elements in front of array(for this time complexity will be O(n) ), than delete remaining elements from last so worst case time complexity of deletion process also remains O(n), otherwise if we do not delete elements from from last worst case time complexity will shoot to O(n^2). Here worst case is when all elements in array are equal.

Defenitely the time should be below O(n^2) dude…otherwise there is no point in asking this question…

Click here to start solving coding interview questions