So I've solved Valid Parentheses on Leetcode a few times now for space repetition. I totally get the stack solution now, but what I don't understand is how to come upon the intuition that helps you realize you need a stack data structure. First couple attempts I tried a weird two pointer approach, which I totally understand why it doesn't work. What are parts of the problem that clue you into the fact you need to use a stack?
Matching brackets requires ensuring that the different types of brackets are nested properly. E.g.
([])
is correctly balanced, but
(])[
is not.
So you can't just use counters for the opening and closing brackets, you need to keep track of the relative order. Closing brackets have to be in the reverse order of the corresponding opening brackets.
The last-in/first-out nature of stacks makes them a natural fit for processing most kinds of nested or hierarchical data. An opening bracket corresponds to a push operation, while a closing bracket corresponds to a pop, and you can check that you're popping the opening bracket that matches the closing bracket that you're processing during that iteration.