Valid Parentheses — Complete LeetCode Solution with Stack Pattern

Use a stack to track opening brackets. When encountering a closing bracket, check if the top of the stack matches. If the stack is empty at the end, the string is valid. This problem is classified as Easy difficulty, though the Stack technique it requires appears in problems across all difficulty levels. Understanding the core mechanic here unlocks solutions to many harder problems. Let us first examine what makes this problem well-suited for this approach: we need to process elements in a way that avoids redundant computation, and the pattern gives us exactly that efficiency. The brute force approach would check all possible combinations, resulting in O(n squared) or worse time complexity. The Stack optimization reduces this dramatically by maintaining state intelligently as we traverse the input. Before coding, always verify your understanding by working through small examples by hand — this catches misunderstandings early and demonstrates thoroughness to your interviewer.

Here is the optimal Python solution using the Stack pattern. Python's clean syntax makes the algorithm's logic easy to follow. Pay attention to how we initialize our data structures and handle edge cases before entering the main loop. The variable naming reflects the algorithmic concept to make the code self-documenting. In an interview, writing clean and readable code like this signals professionalism and attention to detail. Let us walk through the code line by line and understand why each decision was made.

The TypeScript implementation uses the same algorithmic approach with proper type annotations. TypeScript's type system helps catch errors at compile time and makes the code more maintainable. Notice how the generic types and interfaces document the expected input and output formats. If your target company uses TypeScript (which is increasingly common in 2026), demonstrating fluency in typed solutions gives you an edge. The logic mirrors the Python solution exactly, so understanding one helps you write the other quickly.

Time complexity: O(n). Space complexity: O(n). Understanding complexity analysis is critical because interviewers almost always ask about it, and incorrect analysis can cost you the problem even if your code is correct. For time complexity, count how many times each element is processed — in the Stack pattern, each element is typically visited a constant number of times, giving us linear time. For space complexity, consider the auxiliary data structures used beyond the input and output. In this solution, the space usage is O(n) because we store at most n elements in our auxiliary data structure. When comparing approaches, an algorithm that is O(n) time and O(n) space is generally preferred over O(n log n) the and O(1) the for most interview contexts, since the complexity is usually the primary optimization target.

The Stack pattern is applicable when you see these characteristics in a problem: the input involves a linear data structure (array, string, or linked list), you need to find or optimize something among contiguous or related elements, and a brute force approach would involve nested loops. Common signal words include "subarray," "substring," "consecutive," "contiguous," "minimum/maximum window," and "pair." Practice recognizing these signals across different problem phrasings. The Stack pattern also combines well with other techniques: you might use Stack as the outer strategy and binary search or hash maps as inner tools. Building this pattern recognition through deliberate practice is more effective than solving hundreds of random problems. Focus on understanding why the pattern works, not just how to apply it mechanically.

Interviewers frequently modify this problem to test deeper understanding. Common variations include: changing the constraint (find all pairs vs first pair, minimum vs maximum), modifying the input format (sorted vs unsorted, with duplicates vs without), adding constraints (in-place modification, space limit), or extending to higher dimensions (2D matrix version). For each variation, the core Stack technique remains but the implementation details change. Practice at least 3 to 4 variations of every core problem to build the flexibility needed for interview success. When you encounter a variation in an interview, explicitly state how it differs from the base problem and how that difference affects your approach — this demonstrates depth of understanding that impresses interviewers. The Valid Parentheses problem also frequently appears as a subproblem within harder questions, so understanding it thoroughly provides building blocks for tackling complex problems.