LeetCode 20 · Solution & editorial

20. Valid Parentheses

EasyStack PatternsStringStack

How to solve Valid Parentheses (LeetCode 20): the approach in brief

The problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

Pattern

Valid Parentheses is a Stack Patterns problem, in the Valid Parentheses Matching subpattern. The pattern covers parentheses matching, monotonic stack, histogram, and expression evaluation

Master parentheses validation and balancing using stack. Handle multiple bracket types and minimum additions.

Approach outline

Use a stack of characters.
When you encounter an opening bracket, push it to the top of the stack.
When you encounter a closing bracket, check if the top of the stack was the opening for it. If yes, pop it from the stack. Otherwise, return false.

Complexity

The reference solution runs in O(n) time and O(n) space.

Asked at

Valid Parentheses has been reported in interviews at Amazon, Bloomberg, Facebook, Apple, Microsoft, Expedia, Spotify, Google.

The full editorial is part of Pro

It explains the core insight, the complexity analysis and the common mistakes, with a worked solution.

Unlock the full editorial with Pro Solve it first, free

Practise Valid Parentheses and the problems around it

Valid Parentheses is a Stack Patterns problem, in the Valid Parentheses Matching subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Related problems

Longest Valid Parentheses — Hard, same subpattern
Minimum Add to Make Parentheses Valid — Medium, same subpattern
Minimum Number of Swaps to Make the String Balanced — Medium, same subpattern
Minimum Remove to Make Valid Parentheses — Medium, same subpattern
Valid Parenthesis String — Medium, same subpattern
Asteroid Collision — Medium, same pattern

Preparing this workspace.