Complexity of Final Solution
Let n
be the length of the input. We iterate through the input once for O(n)
time complexity, and we can have up to n
elements on the stack (for example having an input only containing (
) for O(n)
space complexity as well.
Let's see it all together now.