20. Valid Parentheses

Problem Link

To check whether parentheses are valid, we need to ensure that every opening bracket is closed in the correct order. This can be done by pairing each closing bracket with the most recently opened bracket that has not yet been closed. If the two brackets match, the pair is considered valid.

Because the last opened bracket must always be closed first, this process follows a Last-In-First-Out (LIFO) pattern. A stack is well suited for this task since it allows constant-time access to the most recent element.

Pseudocode

If the current character is an opening bracket:

• Store it in a stack so it can be matched with a closing bracket later.
• You can use a hashmap (for example, { "{": "}", "(": ")", "[": "]" }) to define valid pairs.

If the current character is a closing bracket:

• Check whether the stack is empty. If it is, there is no corresponding opening bracket, so the string is invalid.
• Otherwise, compare the closing bracket with the expected closing bracket for the stack’s top element.
• If they match, remove the top element from the stack (the pair is successfully closed).
• If they do not match, the string is invalid.

After processing all characters:

• If the stack is empty, all brackets were properly closed.
• If the stack still contains elements, some opening brackets were never closed.

Runtime Complexity

Time: \(O(n)\), single pass + stack operation are constant time.

Space: \(O(n)\), stack can grow upto size of array.

PythonGo

class Solution:
    def isValid(self, s: str) -> bool:
        stk = []
        op = {"(": ")", "{": "}", "[": "]"}
        for ch in s:
            if ch in op:
                stk.append(ch)
            else:
                if len(stk) == 0 or (op[stk[-1]] != ch):
                    return False
                stk.pop()
        return len(stk) == 0

func isValid(s string) bool {
    var stk []rune
    op := map[rune]rune{'(': ')', '{': '}', '[': ']'}
    for _, ch := range s {
        val, ok := op[ch]
        if ok {
            stk = append(stk, val)
        } else {
            if len(stk) == 0 || stk[len(stk)-1] != ch {
                return false
            }
            stk = stk[:len(stk)-1]
        }
    }
    return len(stk) == 0
}

Go Implementation

Time complexity of stk = append(stk, val) is amortized \(O(1)\). Amortized because Go have to resize the slice when its capacity is used, which is an \(O(n)\) from copying and moving existing data. However, this happens infrequently making it \(O(1)\) most of the time.

stk = stk[:len(stk)-1] is \(O(1)\) since data is removed from end, Go just updates the header indicating length.

---