You are viewing a single comment's thread. Return to all comments →
Your solution is O(n+m) runtime and O(n) space complexity, which is slower than what you mentioned in your post, but is still great. The O(n+m) is a result of the fact that m may be larger than n. The space complexity is due to you creating an array of size n.
I do the same in my efficient Java solution.
The runtime complexity is O(N) because M upper bound (2 * 10^5) is lower than N upper bound and even if it was equal (M upper bound = N upper bound), it would be O(N+N), which is O(2N), which could be reduced to O(N).
I usually analyze runtimes assuming variables are unbounded. I find it to be more useful that way since HackerRank usually creates arbitrary bounds for variables.
In the bounded case, you are correct, you can consider it to be O(N).