We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

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.

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).

## Array Manipulation

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

mmay be larger thann. The space complexity is due to you creating an array of sizen.I do the same in my efficient Java solution.

HackerRank solutions.

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).

HackerRank solutions.