Start learning free

LESSON 321 OF 414 · STACK

Valid Parentheses in Scala: O(n) with a Stack

Practice O(n) Read the full explanation

Given a string input containing just the characters '(', ')', '{', '}', '[' and ']', determine if it 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.

Example 1:

Input: input = "()"
Output: true

Example 2:

Input: input = "()[]{}"
Output: true

Example 3:

Input: input = "(]"
Output: false

Example 4:

Input: input = "([)]"
Output: false

Example 5:

Input: input = "{[]}"
Output: true

Constraints:

  • The length of input is between 1 and 104.
  • input consists of parentheses only '()[]{}'.

Note:

Your algorithm should run in O(n) time and use O(n) extra space.


STEP 1 OF 11
    Ctrl + Enter to check

    SCALA · STACK

    Valid Parentheses in Scala, explained

    Problem overview

    The method isValid receives a string input made only of the characters (, ), {, }, [ and ]. It returns true when every opening bracket is closed by a bracket of the same type, and the brackets are closed in the right order.

    "()", "()[]{}" and "{[]}" are valid. "(]" is not, because the types don't match. "([)]" is not either: each bracket has a partner of the right type, but the pairs cross, and the ) arrives while the [ is still open.

    Approach: the most recent opening bracket must close first

    Look at a valid string such as {[()]}. The first bracket to be closed is the last one that was opened, the (. After it, the [ is the last unclosed one, and so on. Brackets nest like boxes inside boxes, and the innermost box closes first. That is the last in, first out behaviour of a stack.

    So the algorithm scans the string once:

    • an opening bracket is pushed on the stack and waits for its partner;
    • a closing bracket must match the bracket on top of the stack, so pop it and compare;
    • if the stack is empty when a closing bracket arrives, nothing is open for it, so the string is invalid;
    • at the end, the stack must be empty, otherwise some opening bracket was never closed.

    To compare, the code stores a map from each opening bracket to the closing one that matches it. Take "([)]": ( and [ are pushed. The ) arrives and pops [. The bracket that closes [ is ], not ), so the method returns false immediately.

    Step by step

    1. Build the lookup map. Declare closingBrackets as an immutable Map with val, with one entry per opening bracket written as key -> value: '(' to ')', '{' to '}' and '[' to ']'.
    2. Create the stack. Declare stack as a val holding an empty scala.collection.mutable.Stack[Char](). Opening brackets wait on it, and the most recent is on top.
    3. Loop over the characters with for (bracket <- input).
    4. Test for an opening bracket with closingBrackets.contains(bracket). A character that is a key of the map is an opening bracket.
    5. Push it with stack.push(bracket).
    6. Handle closing brackets in the else branch, written as } else { on one line.
    7. Reject a closing bracket with nothing open. If stack.isEmpty, return false.
    8. Pop the partner into val openBracket = stack.pop(). It is the only opening bracket this closing one may close.
    9. Compare. If bracket != closingBrackets(openBracket), return false. The lookup always succeeds because everything on the stack is a key of the map.
    10. Check for leftovers. After the loop, return stack.isEmpty: any bracket still on the stack was never closed.

    The solution in Scala

    class Solution {
    def isValid(input: String): Boolean = {
        val closingBrackets = Map(
            '(' -> ')',
            '{' -> '}',
            '[' -> ']'
        )
        val stack = scala.collection.mutable.Stack[Char]()

        for (bracket <- input) {
            if (closingBrackets.contains(bracket)) {
                stack.push(bracket)
            } else {
                if (stack.isEmpty) {
                    return false
                }
                val openBracket = stack.pop()
                if (bracket != closingBrackets(openBracket)) {
                    return false
                }
            }
        }

        return stack.isEmpty
    }
}

    The Scala details worth a closer look:

    • Characters versus strings. '(' with single quotes is a Char, and "(" with double quotes is a String. The map's keys and values and the stack's elements are Chars, which matches what for (bracket <- input) produces: looping over a String yields its characters.
    • -> builds a tuple. '(' -> ')' is the pair ('(', ')'), and Map(...) turns pairs into entries. The default Map is immutable, which suits a fixed table.
    • Looking up in a map. closingBrackets(openBracket) returns the value, and throws NoSuchElementException for a missing key. For a key that might be missing, use get, which returns an Option. Here every popped value was pushed only after contains succeeded.
    • pop() on an empty stack throws. That is why the code tests stack.isEmpty before popping.
    • != compares values. For Chars, bracket != closingBrackets(openBracket) compares the characters themselves.
    • return inside for. The two early return false lines leave the whole method. Scala 3.5 accepts this and prints a warning that non-local returns are no longer supported; the code still compiles and works.

    Complexity

    Time: O(n). Each character is visited once, and each map lookup, push and pop takes constant time on average.

    Space: O(n). A string made only of opening brackets, like "(((((", puts every character on the stack.

    Edge cases and common mistakes

    • A closing bracket first. ")" and "][" return false, thanks to the empty-stack check.
    • Unclosed brackets. "(", "((" and "(()" return false because the stack isn't empty at the end. A solution that only checks the pairs it sees would accept "((" wrongly.
    • Extra closing brackets. "))" returns false on its first character.
    • Crossing pairs. "([)]" returns false. Counting the brackets of each type would say it is valid, which is why a count is not enough.
    • Deep nesting. "{[()]}" returns true.
    • Odd length. A valid string always has an even length, because every bracket has a partner. The method doesn't check this first, but it gives the right answer anyway.
    • The empty string. It returns true, since the stack is empty at the end. The constraints say the input has at least one character.
    • Popping before checking. Calling stack.pop() on an empty stack throws an exception instead of returning false.

    Testing

    • "()" gives true.
    • "()[]{}" gives true.
    • "(]" gives false.
    • "([)]" gives false.
    • "{[]}" gives true.
    • "(()" gives false.
    • ")(" gives false.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free