Last active
April 12, 2021 18:58
-
-
Save patnebe/26f499ec34127d0258a488858d07fbb2 to your computer and use it in GitHub Desktop.
Algorithm Fridays Challenge One
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Algorithm Fridays Code Snippet |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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) |
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
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
Nonevalue 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!