DSA: subarray, monotonic stack
Intuition
If something in the future could have impact on the present, potentially use a stack.
For example in the Valid parentheses problem, a current (
may be closed by a future )
, but we don’t know if or when that would happen. For example in ()
the first open parentheses is closed immediately, but in (((((())))))
, the first open parentheses is closed at the end, and in (((((
, the first parentheses is never closed.
Another intuition is deleting/collapsing/squeezing subarrays if that looks like its relevant to the problem. for example here ( ()() )
we can squeeze out ()()
to get ( squeezed was here )
. The squeezing pattern is visually intuitive.
The stack is useful when we think about problems where we have to connect non-contiguous subarrays.
Implementation
Visual