The Stack Trick for Longest Valid Parentheses
44sReveals a counterintuitive stack approach that transforms a seemingly impossible problem into an O(N) solution.
▶ Play ClipAI Summary
This video explains how to solve the 'Longest Valid Parentheses' problem, a common hard-level coding interview question. It demonstrates an efficient stack-based approach that runs in O(N) time by storing indices of unmatched parentheses rather than the characters themselves.
Chapters
[00:01]
Problem Definition
Given a string of parentheses, find the length of the longest valid (well-formed) substring.
[00:13]
Naive Approach
Storing the brackets themselves in a stack leads to O(N^2) complexity. Instead, store the indices of the parentheses.
[00:27]
Stack Initialization
Seed the stack with -1 as a base case to handle cases where the valid substring starts at index 0.
[00:41]
Processing Example
Walkthrough: push open bracket indices, pop on closed brackets, and compute length as current index minus stack top after popping.
[01:19]
Key Insight
The stack top always marks the start of the current valid run, enabling a one-pass O(N) solution.
The optimal solution uses a stack of indices to track the start of valid substrings, achieving linear time complexity. This approach is a classic pattern for parentheses-related problems.
Mentioned in this Video
Tutorial Checklist
Study Flashcards (5)
What is the time complexity of the naive stack approach for Longest Valid Parentheses?
easy
Click to reveal answer
What is the time complexity of the naive stack approach for Longest Valid Parentheses?
easy
Click to reveal answer
O(N^2)
00:13
What should be stored in the stack to achieve O(N) time?
medium
Click to reveal answer
What should be stored in the stack to achieve O(N) time?
medium
Click to reveal answer
Indices of parentheses, not the characters themselves.
00:13
Why is -1 seeded into the stack initially?
medium
Click to reveal answer
Why is -1 seeded into the stack initially?
medium
Click to reveal answer
To handle cases where the valid substring starts at index 0.
00:27
How do you compute the length of a valid substring when encountering a closing bracket?
medium
Click to reveal answer
How do you compute the length of a valid substring when encountering a closing bracket?
medium
Click to reveal answer
Subtract the index of the new stack top from the current index.
00:47
What does the stack top always represent during the algorithm?
hard
Click to reveal answer
What does the stack top always represent during the algorithm?
hard
Click to reveal answer
The start of the current valid run.
01:19
💡 Key Takeaways
🔧
Optimization Insight
Storing indices instead of characters is the key to reducing complexity from O(N^2) to O(N).
00:13
🔧
Base Case Seeding
Seeding the stack with -1 elegantly handles edge cases where the valid substring starts at the beginning.
00:27
💡
One-Pass Solution
The algorithm achieves linear time by maintaining the start of the current valid run at the stack top.
01:19Full Transcript
[00:01] looks impossible until you see what the stack is actually storing. See, you're given a string of parentheses and your goal is to find the length of the longest substring of parentheses. Now, hearing parentheses, your mind probably
[00:13] went to let me store the brackets in the stack. If you do this, you'd build the string, which would be O of N squared complexity. And we can do a lot better storing the brackets or the parentheses in the stack, store their indices.
[00:27] Specifically, the index of the last unmatched opening parenthesis. Let's example. You want to seed the stack with negative one as the base case. Now, index zero is an open bracket. So, push zero to the stack. Index one is also an
[00:41] stack, too. But now, index two is a closed bracket. And so, we pop one from closed bracket. And so, we pop one from the stack. Stack top is now zero and the length equals two minus zero, which is two. So, the current max length is two.
[00:54] Similarly, index three is an open bracket. So, we push three onto the stack. Now, index four is again a closed bracket. So, we can pop that three from the stack. The stack top now again is zero and the length equals four minus
[01:06] zero, which is four. So, the current max length is four. Finally, index five is a closed bracket. So, we can pop zero from the stack. The stack top is now that negative one and the length equals five minus negative one, which is six. So,
[01:19] the current max length is six and that's our final answer. So, the key is that the stack top always marks where the current valid run started, giving you a one pass O of N solution. Learn more with interactive visualizations at
[01:31] hellonerd.com and go ahead and smash that follow button.
