Valid Parentheses - Amazon Interview Question & Solution

Valid Parentheses

Amazon

String

Stack

Imagine you are building the part of a code editor that flags unbalanced brackets. You receive a string s made up only of the characters ( ) [ ] { } and must decide whether it is balanced.

A string is balanced when:

every opening bracket is closed by a bracket of the same kind,
brackets close in the reverse order they were opened (the most recent opener closes first), and
no closing bracket appears without a matching opener before it.

Examples:

Input: s = "{[()]}"   Output: true
Input: s = "([)]"     Output: false  (the ")" arrives while "[" is still open)
Input: s = "(("       Output: false  (two openers are never closed)

Solution Walkthrough

This is a classic problem that can be elegantly solved using a stack data structure.

Initialize an empty stack.
Create a map to store the relationship between closing and opening brackets, e.g., { ')': '(', '}': '{', ']': '[' }.
Iterate through each character of the input string s.
- If the character is an opening bracket ((, {, [), push it onto the stack.
- If the character is a closing bracket (), }, ]), check the stack. If the stack is empty or if the top element of the stack is not the corresponding opening bracket, the string is invalid. If it matches, pop the stack.
After the loop, if the stack is empty, it means all brackets were correctly matched and closed, so the string is valid. If the stack is not empty, it means there are unclosed opening brackets, so the string is invalid.

The time complexity is O(n) because we process each character once. The space complexity is O(n) in the worst case (a string of all opening brackets).

function isValid(s) {
    const stack = [];
    const map = {
        ')': '(',
        '}': '{',
        ']': '['
    };

    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        if (map[char]) { // It's a closing bracket
            const topElement = stack.length === 0 ? '#' : stack.pop();
            if (topElement !== map[char]) {
                return false;
            }
        } else { // It's an opening bracket
            stack.push(char);
        }
    }

    return stack.length === 0;
}

Related Algorithms

Stack →