Last active
April 19, 2021 17:32
-
-
Save KingAshiru/acc0e4b9a19e352a2000a36e2a12724c to your computer and use it in GitHub Desktop.
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
class Solution: | |
def removeElement(self, nums, val) -> int: | |
# check for edge cases of None array, None value, or invalid values such as strings | |
if not nums: | |
return 0 | |
if (not val) or (type(val) is not int) or (type(val) is not float): | |
return len(nums) | |
nextNonKey = 0 | |
i = 0 | |
# The idea is to check each element from the first index, | |
# If the element is a val we don't want to remove, we update that position using the nextNonKey tracker | |
# When we are done with all operations in the loop, nextNonKey would be the length of our desired array of values. | |
while i < len(nums): | |
if nums[i] != val: | |
nums[nextNonKey] = nums[i] | |
nextNonKey += 1 | |
i += 1 | |
return nextNonKey | |
# The while loop takes O(N), where N is the length of nums array | |
# Since the operation is done in place, we create no extra space, space complexity is O(1) | |
# In total we have Time - O(N), Space - O(1) |
Hi @meekg33k, happy again to receive feedback from you.
Tbh, I always had the idea that a two-pointers solution comes in handy when
we are given a sorted array. So I honestly didn't think of it because our
array was unsorted. I would pay attention to that moving forward.
While I can argue that an O(N/2) solution is asymptotically the same as an
O(N) solution by ignoring constants, I think an O(N/2) would really make a
difference in large input cases. Therefore I would go with your solution.
Good that I always have something to learn whenever I engage these
problems. Looking forward to the next, hopefully, I win lol.
Cheers!
…On Mon, Apr 19, 2021 at 3:46 PM meekg33k ***@***.***> wrote:
***@***.**** commented on this gist.
------------------------------
Hello @KingAshiru <https://github.com/KingAshiru>, thank you for
participating in Week 2 of Algorithm Fridays.
Really decent and robust solution you got here, that handles a lot of edge
cases. This a huge improvement from last week's solution. Kudos to you! I
also like that you are performing in-place operations thus ensuring good
memory usage. Sweet!
The logic for your solution correctly centers around looping through the
array to check for elements whose values are not equal to val. Do you
think there's a faster way we can loop through the array?
I've posted my solution here
<https://meekg33k.dev/understanding-how-the-filter-function-works>. I am
curious to know what you think.
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
<https://gist.github.com/acc0e4b9a19e352a2000a36e2a12724c#gistcomment-3711382>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/AMLPOL55QWOOBAS6DZ3UJILTJQ63ZANCNFSM43F7KZSQ>
.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hello @KingAshiru, thank you for participating in Week 2 of Algorithm Fridays.
Really decent and robust solution you got here, that handles a lot of edge cases. This a huge improvement from last week's solution. Kudos to you! I also like that you are performing in-place operations thus ensuring good memory usage. Sweet!
The logic for your solution correctly centers around looping through the array to check for elements whose values are not equal to
val
. Do you think there's a faster way we can loop through the array?I've posted my solution here. I am curious to know what you think.