Valid Parentheses
We can solve this problem using a stack data structure. The idea is to push the opening brackets into the stack and pop them out when a matching closing bracket is found. If the string is valid, the stack should be empty at the end.


Explanation:
 If the current character is an opening bracket, it’s pushed onto the stack.
 If it’s a closing bracket, the top element of the stack is popped, and we check if it matches the corresponding opening bracket.
 If the stack is empty at the end of the iteration, the brackets are balanced, and the string is valid. If not, the string is invalid.
This solution takes linear time, as it scans through the string once, and constant extra space, as it uses a fixedsize mapping and a stack whose size is proportional to the length of the input string.
title: Valid Parentheses excerpt: This covers using stack to solve problems. tags: linearscan stack
Given a string s containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:
 Open brackets must be closed by the same type of brackets.
 Open brackets must be closed in the correct order.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Example 4:
Input: s = "([)]"
Output: false
Example 5:
Input: s = "{[]}"
Output: true
Constraints
 1 <= s.length <= 104
 s consists of parentheses only ‘()[]{}’.
Problem Definition
Define the Interface
Input: string Output: boolean
Identify Implicit Inputs
Possible brackets are: ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’
If you begin the string with closing parenthesis, it is false.
Search the Problem Space
Look for clues in the problem statement. In this case, the order of the brackets matter. So we need to think of using either queue or stack.
Brute Force Approach
 Push the open parenthesis
 Pop if the closing parenthesis matches
 The stack is empty and we have scanned all characters in the string. We return true.
 I have scanned all the characters in the string. The stack is not empty. We return false.
 When we encounter a closing parenthesis, it must be a closing parenthesis for the type of parenthesis at the top of the stack. If it is not, return false immediately.






Variant
A simpler version of the problem is there is only one type of bracket in the string and the code can be simplified.


Building Block
 Linear Scan
 Stack
Identifying Problem Isomorphism
“Valid Parentheses” shares a close resemblance to “Balanced Brackets”.
In “Valid Parentheses”, you’re given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’. You have to determine if the input string is valid, with an input string being valid if:
 Open brackets must be closed by the same type of brackets.
 Open brackets must be closed in the correct order.
“Balanced Brackets” presents a similar problem where you’re given a string of brackets and you have to decide whether the sequence of brackets is balanced. The rules of balanced brackets are:
 For every bracket that is opened, the same type of bracket must close it.
 The brackets must close in the correct order.
The concept of using a data structure like a stack to keep track of the opening brackets until we encounter a closing bracket can be applied to both problems, making them isomorphic problems. When a closing bracket is encountered, we check the top of the stack and if the opening bracket of the same type is there, we remove it, otherwise, the sequence is not balanced.
Both problems are of similar complexity as they involve the same logical steps. “Valid Parentheses” is simpler due to the lesser variety of bracket types in the input.
10 Prerequisite LeetCode Problems
“Valid Parentheses” (LeetCode 20) is a common introductory problem for understanding stacks, for simpler problems, consider the following:
“344. Reverse String”: This problem is about reversing a string, and although it’s straightforward, it can help you understand strings and arrays in more depth.
“1. Two Sum”: This is a classic introductory problem for understanding arrays and hashmaps.
“13. Roman to Integer”: This problem asks you to convert a Roman numeral to an integer. It can help you get familiar with the concept of a lookup table, which is essentially a kind of hash map.
“26. Remove Duplicates from Sorted Array”: This problem asks you to remove duplicates inplace in a sorted array. It can help you understand the concept of two pointers.
“283. Move Zeroes”: This problem requires you to move all zeroes in an array to the end while maintaining the order of the other elements. It’s a good practice problem for inplace array manipulation.
“35. Search Insert Position”: This problem is about binary search, which is a common technique for efficient searching in sorted arrays.
“58. Length of Last Word”: This problem requires you to find the length of the last word in a string, helping to understand string manipulation concepts.
“217. Contains Duplicate”: This problem asks you to determine if an array contains any duplicates, providing practice with array manipulation and set data structures.


Problem Classification
String manipulation: The problem requires you to handle and process string inputs, specifically strings containing various types of brackets. Thus, a good understanding of strings and string operations is needed.
Stack data structure: The problem uses the LIFO (Last In First Out) principle to check for balanced parentheses. This is a fundamental use case for the stack data structure.
Parentheses/Brackets Matching: This is the specific problem domain  the task of checking if the openclose brackets in a given string are properly paired and nested.
The problem is a mix of string manipulation, data structure (specifically, stack), and parentheses matching.
Language Agnostic Coding Drills
Understanding Stacks: The stack data structure follows the LastInFirstOut (LIFO) principle, which is essential to understand the solution. A stack allows adding an item or “pushing” to the top of the stack, and removing an item or “popping” from the top of the stack.
Understanding Parentheses Balance Concept: The problem is about validating if the given string has balanced parentheses. Balanced parentheses mean that each opening symbol has a corresponding closing symbol and the pairs of parentheses are properly nested.
Conditionals and Loops: The problem requires a knowledge of iterative constructs like forloops and conditional constructs like ifelse statements to traverse through the string and to perform operations based on certain conditions.
String Manipulation: This involves understanding how to iterate over a string, access individual characters, and compare characters.
Problem Solving Approach:
Initialization: Start by initializing an empty stack. The stack is used to keep track of the opening brackets.
Iterating through the string: Loop over each character in the string. If the character is an opening bracket, push it onto the stack. If it’s a closing bracket, check the top element of the stack.
Matching Brackets: If the top element in the stack is the corresponding opening bracket, pop it from the stack. If not, return False, as the string is not balanced.
Stack Check after Iteration: After we’ve iterated through all the characters in the string, check if the stack is empty. If it’s empty, it means all opening brackets had their corresponding closing ones (the string was balanced), and we return True. If not, return False.
This general approach can be used in most modern programming languages. You’ll need to understand the languagespecific syntax for implementing stacks and string manipulation, but the overall strategy remains the same.
Targeted Drills in Python
Drill 1: Understanding Stacks Here you need to learn how to create a stack, and how to use push and pop operations. The list data structure in Python can be used as a stack.


Drill 2: Conditionals and Loops Understanding how to use conditional (ifelse) statements and loops is vital for this problem.


Drill 3: String Manipulation In this problem, you’re dealing with strings. You need to understand how to iterate through a string and how to compare characters.


Drill 4: Understanding Parentheses Balance Concept Finally, you need to understand how to check for balanced parentheses. This is where you’ll put everything together.


Once you’ve worked through these drills and understand each of the concepts, you can then combine them to solve the problem in the final integrated drill, which would involve modifying the is_balanced
function to handle all types of brackets, not just parentheses.