https://leetcode.com/problems/valid-parentheses/submissions/

The optimal solution for this one cannot be better than O(n) space – unless you are willing-to/allowed-to modify the input. Also, should that solution be considered O(1) space if you are reusing the space allocated for input?

Instead, the O(n) space optimal solution can be achieved using a stack/array to keep a record of open brackets. When we see a closed bracket – we should return false if the last open bracket is ‘nil’ or not the matching ‘type’. At the end of the loop – we should also not have any dangling open brackets – if we do, that means the sequence of brackets was not balanced – and we should return false.

Edit: Let’s say, that the problem states the input string could only contain one of ‘(‘, ‘[‘, “{” types – in that case we can keep a single integer var openBrackets that we increment when we see a open bracket and decrement when we see a closed one. At any point if openBrackets becomes negative we know that the sequence was unbalanced, similarly, at the end of the loop, openBrackets should be 0 for the string to be balanced. This is O(1) space solution since we do not need a stack/array to keep a track of open brackets.