|Given a sorted array containing duplicates this function|
|returns the length of the array without the duplicates|
|i.e. the number of unique items in the array|
|# O(n) time, O(1) space complexity|
|array_length = len(input_array)|
|if array_length <= 1:|
|num_unique_items = 1|
|# index of the current unique number|
|left_index = 0|
|# index of the current possible duplicate|
|right_index = 1|
|# iterate through the array from left to right|
|# for each new unique number encountered,|
|# move through the array to find the first non-duplicate|
|# Once a non-duplicate is encountered, we know we are now dealing with the next unique item|
|# increment the necessary counters and repeat the process for this new unique number|
|while right_index < array_length:|
|current_unique_num = input_array[left_index]|
|num_to_test = input_array[right_index]|
|if num_to_test != current_unique_num:|
|# no more duplicates for the current unique number|
|# we are now dealing with another unique number|
|num_unique_items += 1|
|left_index = right_index|
|right_index += 1|
|print(remove_duplicates([0,0,1,1,2,2,3,3,4]) == 5)|
|print(remove_duplicates([1,2,3,4,5]) == 5)|
Hello @Dev-Nebe, thank you for participating in Week 1 of Algorithm Fridays.
I like your solution especially because it is memory-optimal and also you wrote out the different test cases - that was really good!
The only one assumption you made is that the input array cannot have a null value because if I pass a
That said, your solution definitely got a special mention in the blog post here where I posted our solution. Please read through and let me know what you think.
Thanks once again and see you on Friday!