Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Algorithm Fridays Challenge One
Algorithm Fridays Code Snippet
def remove_duplicates(input_array):
"""
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
Input: nums=[0,0,1,1,2,2,3,3,4]
Output: 5
# O(n) time, O(1) space complexity
"""
array_length = len(input_array)
if array_length <= 1:
return array_length
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
return num_unique_items
print(remove_duplicates([0,0,1,1,2,2,3,3,4]) == 5)
print(remove_duplicates([1,2,3,4,5]) == 5)
print(remove_duplicates([1,2])==2)
print(remove_duplicates([1])==1)
print(remove_duplicates([])==0)
print(remove_duplicates([3,3,3])==1)
print(remove_duplicates([1,2,2,3,3,3,4,4,5])==5)
@meekg33k

This comment has been minimized.

Copy link

@meekg33k meekg33k commented Apr 12, 2021

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 None value as input to your function, it breaks on line 14. Ideally, you want to write code that is robust and doesn't fail on edge cases or unexpected input.

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!

@Dev-Nebe

This comment has been minimized.

Copy link
Owner Author

@Dev-Nebe Dev-Nebe commented Apr 12, 2021

Lol, I can't believe I missed that test case. I'll definitely keep that in mind going forward.

Thanks for the feedback and for the special mention :) @meekg33k

I'll be looking forward to the next challenge on Friday.

Cheers.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment