Mark As Completed Discussion

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.