Decide what to store on the stack
Updated
Store the smallest thing that lets you resume or resolve: an opener, an index, a (value,min) pair, a fragment plus count, a frame phase. Storing the whole remaining array is usually too much.
What to focus on
If you need to write answer[i], store i. If you only compare values, values may suffice. If rollback needs extra, store the extra in the pair now.
Worked examples
brackets
s = "([])"- store the opener char (or its index)
Result: opener (or index)
next greater
a = [2, 1, 3]- store indices
Result: stack of indices
decode
s = "3[ab]"- store (frag, count) checkpoints
Result: (frag, count)
Try it
Write itemType(kind). kind is "brackets", "nextGreater", or "decode". Return what each stack item stores. Shrink it until you cannot still resume. s = \"([])\" → opener (or index). a = [2, 1, 3] → stack of indices. s = \"3[ab]\" → (frag, count).
s and a are well-formed examples of each pattern. Name the item type.