Valid Parenthesis

Question link: https://leetcode.com/problems/valid-parentheses/

Problem: Valid Parenthesis

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"

Output: true

Example 2:

Input: s = "()[]{}"

Output: true

Example 3:

Input: s = "(]"

Output: false

Example 4:

Input: s = "([])"

Output: true

Constraints:

• 1 <= s.length <= 10^4
• s consists of parentheses only '()[]{}'.

Walkthrough

Reading the question, we can see that what they want us to do is to check if the latest open bracket has been closed in the correct order and with the correct bracket type and that every type of close bracket has the same corresponding type of open bracket. This signifies to me that we should be using a FILO (First in last out) approach, i.e. the first open bracket has to be closed last. FILO suggests the usage of a stack.

Finding a solution in words

Let’s think of an intuitive approach to solving this problem.

1. We would need to loop through the entire string.
2. If we reach an open bracket we need to store it in the right order. i.e. we need to store it in a way that we keep the order in tack and have a way to access the latest open bracket
3. If we reach a close bracket, we need to lookup the latest open bracket(as mentioned in point 2) and compare whether or not the closing bracket matches the latest open bracket, i.e. ) matches ( , ] matches [ and } matches {.

The above seems to be a general solution to solve the problem. Now let’s think of edge cases.

1. What if there are more open brackets than the corresponding close bracket?
2. What if there are more closed brackets than corresponding open brackets?

A few of you keen eyed folks might also think of the case when the input is empty, i.e. “”. We do not have to worry about this case as the constraint is 1 <= s.length <= 10^4 . Regardless it is a good catch!

Transitioning words to coding terms

Now that we have the solution in english, let’s now think about what we need to solve this problem. We’ve mentioned earlier that we would need a way to keep track of the brackets in the right order, i.e. FILO. This suggests that we need a stack. The main methods of a stack is Push() and Pop(). Push pushes an element to the end of the stack and Pop retrieves and removes the last element of the stack. Exactly what we need.

Now for the problem of finding corresponding open/close bracket. We could make if else statements each time to check if the open/close brackets matches correspondingly OR we could just make a mapping of the open and closing brackets, something like {'(':')', '[':']', '{':'}'} which will make things more verbose.

Solution

Now that we have a plan of attack, let’s get to coding!

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {

		// We have a mapping as mentioned before to check for corresponding brackets
    const map = {'(':')', '[':']', '{':'}'}


    // Have a stack of open brackets to keep track of
    const openBrackets = []

	
    for (let bracket of s) {
    
		    // If it is an open bracket, store it in our openBrackets stack
        if (brackets === '(' || brackets === '[' || brackets === '{') {
            openBrackets.push(brackets)
        }

				// If it is a closed bracket, check if it matches the corresponding latest open bracket
        else {
            const latestOpenBracket = openBrackets.pop()
            if (brackets !== map[latestOpenBracket]) {
                return false
            }
        }
    }

    
    // Our edge cases
    // Check if openBracket stack is empty once our main logic is done
    if (openBrackets.length === 0) {
        return true
    }

    // return false if there are brackets that haven't been closed off
    return false
};

Analysis

Let’s analyze our code, what is the time and space complexity of our solution.

Time complexity

• We have looped through the entire string once, this alone makes our solution O(n) .
• We would have to loop through our openBrackets stack, which is worst case O(n) . i.e. in the case where s is all open brackets.
• Lookup on mapping is O(1) .

Therefore from this we can say that the time complexity of our code is O(n).

Space complexity

• Our mapping is constant O(1)
• openBrackets is worst case O(n) . i.e. in the case where s is all open brackets

Therefore, our space complexity is O(n).