The Brackets challenge from Codility was a fun exercise.
A solution with O(N) complexity requires a single run of the array.
At each step, we operate on a stack following three cases:
- If the stack is empty and we the current element is a closing bracket of any kind, then the string is not properly nested
- If the stack is not empty and we are placing a closing bracket, then if the closing bracket matches the last opened bracket in the stack, then we eliminate the last opening bracket from the stack
- Otherwise, we add to the stack the element if it is an opening bracket. If we are trying to push a closing bracket that did not match, again we have the conclusion that the string is not properly nested.
Here is the report. Let me know if you can think of a better solution!