Blog

Valid Parentheses (Leetcode Problem #20)

  • Post last modified:December 15, 2022
  • Reading time:3 mins read

Java Solution for https://leetcode.com/problems/valid-parentheses/

Understanding Problem

  • We have been given an input string of open and closed parentheses that made of (,[,{ , ),],}.
  • We need to determine if the input string is valid
  • Input string valid only if , open bracket is closed with same type of close bracket and they should be in correct order
  • So we need to return true of parentheses are valid and need to return false if input string is invalid .
"()"   <- valid parentheses
"([]"  <- invalid parentheses
"([])" <- valid parentheses

My Thought About Solution

  • If we traverse each charater in input string and if the current character is of close type , then logically last traversed charcter should be of open type i.e, if current character is “)“ type then last traversed character has to be “(“ in order for string to be valid otherwise it will be invalid.
  • Now to store the list of last traversed open brackets we need data structure that would support LIFO ( last in first output ) and Stack data structure support Last In First Out.
  • Data structure: We will use stack data structure to support LIFO ( last input first out )
    Time-complexity: O(N) where N is the length of input string
    Space-complexity: O(N) space which we need to store list of last traversed open brackets

Pseudocode

1: Create stack data structure
2: Traverse each charater in input string
3: Check if the type of open parentheses is of (, [, { and push it to stack.
4: Check if the type of parentheses is closed ) && check if the    last pushed element in the stack is open ( 
then pop that open parentheses from the stack since parentheses are     valid.  (Since current parentheses is closed and last pushed is open, that means we have continous open and closed parentheses)
5:  Check if the type of parentheses is closed ] && check if the    last pushed element in the stack is open [
then pop that parentheses from the stack since parentheses are     valid.
6:  Check if the type of parentheses is closed } && check if the    last pushed element in the stack is open {
then pop that parentheses from the stack since parentheses are     valid.
7: Return if stack is empty( stack will be empty when all the open brackets that pushed in stack have find closed bracket, if its not then stack will not be empty).

Solutions

Result

Our runtime beats 98% of the java submission , which is satisfying result.

Conclusion

  • This problem is good excercise to use Stack data structure. Stack data structure is stores data in LIFO i.e Last In First Out that solves very important problems in computer programming.
  • One of the most important use case is call stack in Java. So whenever we make nested call of methods , JVM stores these calls on call stack and executes in LIFO fashion. Ex, A()->B()->C()->D(), in the Stack it would store as D(), C(),B(),A(). so D will executes first , then C, B and finally A.

Let me know if you have some opinion on the solution in the comment!

Bonus Tip

  • If you want to upskill your coding interview game, you can definitely check out this bestseller course ( this is in Java )

Happy Leetcoding!

Tags: , ,

Leave a Reply