---
title: 'Longest Valid Parentheses | Hard'
source: 'https://youtube.com/watch?v=h-tLxMBKA0g'
video_id: 'h-tLxMBKA0g'
date: 2026-08-04
duration_sec: 95
---

# Longest Valid Parentheses | Hard

> Source: [Longest Valid Parentheses | Hard](https://youtube.com/watch?v=h-tLxMBKA0g)

## 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.

### Key Points

- **Problem Definition** [00:01] — Given a string of parentheses, find the length of the longest valid (well-formed) substring.
- **Naive Approach** [00:13] — Storing the brackets themselves in a stack leads to O(N^2) complexity. Instead, store the indices of the parentheses.
- **Stack Initialization** [00:27] — Seed the stack with -1 as a base case to handle cases where the valid substring starts at index 0.
- **Processing Example** [00:41] — Walkthrough: push open bracket indices, pop on closed brackets, and compute length as current index minus stack top after popping.
- **Key Insight** [01:19] — The stack top always marks the start of the current valid run, enabling a one-pass O(N) solution.

### Conclusion

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.

## Transcript

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
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.
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
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.
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
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,
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
hellonerd.com and go ahead and smash that follow button.