LESSON 297 OF 348 · STACK

Valid Parentheses in Kotlin: O(n) with an ArrayDeque 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 <= 10⁴
s consists of parentheses only '()[]{}'.

Note:

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

STEP 1 OF 10

Guided

Ctrl + Enter to check

KOTLIN · STACK

Valid Parentheses in Kotlin, explained

Problem overview

You get a string input made only of the characters (, ), {, }, [ and ]. The function returns true if the brackets are valid, which needs two things:

every opening bracket is closed by a bracket of the same type;
brackets are closed in the correct order, so the most recently opened one is closed first.

So "()", "()[]{}" and "{[]}" are valid. "(]" is not, because the types differ. "([)]" is not either: each bracket has a partner of the right type, but the ) arrives while [ is still open, so the order is wrong.

The lesson asks for O(n) time and O(n) extra space.

Approach

Read the string from left to right and ask one question at each closing bracket: which opening bracket does it have to close? It has to be the most recent one that is still open. "The most recent one that is still open" is exactly what the top of a stack gives you:

an opening bracket is pushed on the stack and waits for its partner;
a closing bracket pops the top and must match it;
at the end, nothing may be left on the stack.

Each character is handled once, with constant-time stack operations, so the time is O(n). In the worst case, for example a string of only opening brackets, the stack holds all n characters, so the space is O(n).

Step by step

A map of pairs. closingBrackets is a read-only map from each opening bracket to the closing bracket that matches it. mapOf builds it from pairs written as key to value. The map also serves as the test for "is this an opening bracket?": opening brackets are its keys.
A stack. stack is an empty ArrayDeque<Char>. The end of the deque is the top of the stack. It holds opening brackets that still wait for their partner.
Visit each character with for (bracket in input).
Is it an opening bracket? closingBrackets.containsKey(bracket) is true for (, { and [.
Push it with stack.addLast(bracket).
Otherwise it is a closing bracket. The else branch deals with it.
Nothing to close. If stack.isEmpty(), a closing bracket has no opening partner, as in ")", so return false.
Pop the partner. stack.removeLast() returns the most recent opening bracket, the only one this closing bracket is allowed to close. It goes into openBracket.
Compare. The expected closing bracket is closingBrackets[openBracket]. If the current bracket differs from it, return false.
Leftovers. After the loop, stack.isEmpty() tells whether every opening bracket got closed. Return that value directly.

The solution in Kotlin

class Solution {
    fun isValid(input: String): Boolean {
        val closingBrackets = mapOf(
            '(' to ')',
            '{' to '}',
            '[' to ']'
        )
        val stack = ArrayDeque<Char>()

        for (bracket in input) {
            if (closingBrackets.containsKey(bracket)) {
                stack.addLast(bracket)
            } else {
                if (stack.isEmpty()) {
                    return false
                }
                val openBracket = stack.removeLast()
                if (bracket != closingBrackets[openBracket]) {
                    return false
                }
            }
        }

        return stack.isEmpty()
    }
}

Kotlin details worth knowing:

'(' with single quotes is a Char; "(" with double quotes is a String. The map and the stack both use Char, and iterating over a String gives Chars.
a to b creates a Pair. mapOf(...) returns a read-only Map<Char, Char>, which is all this code needs because the pairs never change.
ArrayDeque is Kotlin's own class and needs no import. addLast pushes and removeLast() pops at the same end.
closingBrackets[openBracket] has the type Char?, because a map lookup gives null for a missing key. Comparing a Char with a Char? using != is allowed, and null is simply never equal to a real character. For this input the key is always present, because only opening brackets are pushed.
removeLast() on an empty ArrayDeque throws NoSuchElementException. The isEmpty() check before it is what prevents that.

Complexity

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

Space: O(n). The stack grows with the number of unclosed opening brackets, up to n for a string such as "(((((".

Edge cases and common mistakes

Only a closing bracket. For ")" the stack is empty when the closing bracket arrives, and the function returns false. Without the empty check, removeLast() would throw.
Unclosed brackets. For "((" the loop ends without a mismatch, but the stack still holds two items. The final stack.isEmpty() catches this; returning true at the end would be wrong.
Right types, wrong order. For "([)]" the ) pops [, which does not match, so the answer is false.
Odd length. A string of odd length can never be valid, because brackets come in pairs. The stack discovers this on its own, but you could return false early as a shortcut.
Counting instead of stacking. A counter per bracket type accepts "([)]", since it ignores order. The stack is what enforces the order.

Testing

"()", "()[]{}" and "{[]}" return true.
"(]", "([)]", ")" and "((" return false.

Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free