The problem is not the erasing. The problem is having to traverse the big array (M), for every element. That makes a total time of O(N*M) 


([1,2,3,4,5,6,7,8,9,10], 0, null, 0, null)








There is an easy O(N^2) were you consider only the taken books, (not sure if fast enough) suppose that you want to borrow the K book, If there is a J, with J<=K, that was borrowed, then you need to take the K+1 book. 


helios wrote: 

because in the worst case, you have to iterate over the entire list every time a book is removed. 
helios wrote: 

The first time the list will contain one element; the second, two; the third, three; and so on. Adding up everything, we come up with (1/2)*N^2 + (1/2)*N iterations 
input 5 1 2 3 4 5 5 3 3 2 1 1 expected output 3 4 2 1 5 your output 3 4 2 1 2 


Well, this is true up to a point. Once we have removed N/2 books the (maximum) number of iterations required to traverse the list declines by one for each subsequent removal. (At that point there are only one element ranges left .) 
cire wrote: 

And, I suppose worst case should only be considering M < N/2, anyway. 