Last active
April 27, 2021 12:02
-
-
Save Fredpwol/c50dce0f62812819dde3cae775181de2 to your computer and use it in GitHub Desktop.
Find num start and end position in a list after sorting
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 findSortedPosition(nums, val): | |
| "This solution takes O(n) time complexity and O(1) space complexity" | |
| if nums == None: return [-1, -1] | |
| if val == None or type(val) != int: return [-1, -1] | |
| nums_less = 0 | |
| num_val = 0 | |
| for num in nums: | |
| if num < val: | |
| nums_less += 1 | |
| elif num == val: | |
| num_val += 1 | |
| if num_val > 0: | |
| return [nums_less, (nums_less+num_val)-1] #subtract one here because of 0 based indexing | |
| return [-1, -1] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hello @Fredpwol, congratulations, you are one of the winners of the $20 award 🎉🎉for Week 3 of #AlgorithmFridays.
Your solution was selected because it is most optimal in terms of time complexity. You were able to find a way to solve the problem without sorting the array. Smart!
I have made a blog post here about the different solutions and also announcing you as one of the winners for Week 3 of #AlgorithmFridays.
We will contact you in less than 24 hours for your award.
Congratulations once again and thanks for participating!