Last active
April 24, 2021 00:30
-
-
Save chygoz2/540ca2dcf141b8340b3194b4eeb5da8b to your computer and use it in GitHub Desktop.
Algo friday 2 solution
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
function removeInstance(nums, val) { | |
if (!Array.isArray(nums)) throw new Error('Invalid input') | |
return nums.filter(entry => entry !== val).length | |
} |
Very well said and I totally agree that in terms of algorithm complexity, O(n/2)
is effectively O(n)
. You got a clean solution nevertheless!
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Thanks @meekg33k. I agree with you about the
filter
function affecting the space complexity of the algorithm, thus your solution is better in this regard.The nature of the question revealed that it would be almost impossible to find a solution that wouldn't require going through the entire array, resulting in a time complexity of
O(n)
. Your approach to solving it is quite interesting, and one I didn't think of.In terms of algorithm complexity,
O(n/2)
is effectivelyO(n)
, since the growth rate of the solution is still linearly proportional to the size of the input, and constants are ignored in the calculation of algorithm complexities.N.B I'm sure you already know that, just pointing it out to others that may be reading this.
I very much like your solution as it actually results in shorter program execution time, even though the time complexity is still linear.