Fix the Bracket Validator

isValid(s) returns true if every bracket in s ((), [], {}) is closed by the same type of bracket in the right order.

The stack-based code below rejects mismatched brackets correctly, but QA found inputs it accepts that are clearly invalid. Find the bug and fix it.

Example 1

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

Example 2

Input: s = "(("
Output: false
Explanation: The buggy version returns true.

The buggy code

function isValid(s) {
  const pairs = { ")": "(", "]": "[", "}": "{" };
  const stack = [];
  for (const c of s) {
    if (c in pairs) {
      if (stack.pop() !== pairs[c]) return false;
    } else {
      stack.push(c);
    }
  }
  return true;
}

function isValid(s: string): boolean {
  const pairs: Record<string, string> = { ")": "(", "]": "[", "}": "{" };
  const stack: string[] = [];
  for (const c of s) {
    if (c in pairs) {
      if (stack.pop() !== pairs[c]) return false;
    } else {
      stack.push(c);
    }
  }
  return true;
}

def is_valid(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []
    for c in s:
        if c in pairs:
            if not stack or stack.pop() != pairs[c]:
                return False
        else:
            stack.append(c)
    return True

<?php

function isValid(string $s): bool
{
    $pairs = [')' => '(', ']' => '[', '}' => '{'];
    $stack = [];
    foreach (str_split($s) as $c) {
        if (isset($pairs[$c])) {
            if (array_pop($stack) !== $pairs[$c]) {
                return false;
            }
        } else {
            $stack[] = $c;
        }
    }
    return true;
}

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (pairs.containsKey(c)) {
                if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
            } else {
                stack.push(c);
            }
        }
        return true;
    }
}

Solution and explanation

Show the bug and the fix

Time O(n) · Space O(n)

The bug: the function returns true after the loop without checking whether any opening brackets are still waiting on the stack. Unclosed brackets ("((", "(()") are accepted.

The fix: a string is valid only if the stack is empty at the end: return stack.length === 0.

Fixed version

function isValid(s) {
  const pairs = { ")": "(", "]": "[", "}": "{" };
  const stack = [];
  for (const c of s) {
    if (c in pairs) {
      if (stack.pop() !== pairs[c]) return false;
    } else {
      stack.push(c);
    }
  }
  return stack.length === 0; // every opener must have been closed
}

function isValid(s: string): boolean {
  const pairs: Record<string, string> = { ")": "(", "]": "[", "}": "{" };
  const stack: string[] = [];
  for (const c of s) {
    if (c in pairs) {
      if (stack.pop() !== pairs[c]) return false;
    } else {
      stack.push(c);
    }
  }
  return stack.length === 0; // every opener must have been closed
}

def is_valid(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []
    for c in s:
        if c in pairs:
            if not stack or stack.pop() != pairs[c]:
                return False
        else:
            stack.append(c)
    return not stack  # every opener must have been closed

<?php

function isValid(string $s): bool
{
    $pairs = [')' => '(', ']' => '[', '}' => '{'];
    $stack = [];
    foreach (str_split($s) as $c) {
        if (isset($pairs[$c])) {
            if (array_pop($stack) !== $pairs[$c]) {
                return false;
            }
        } else {
            $stack[] = $c;
        }
    }
    return $stack === []; // every opener must have been closed
}

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (pairs.containsKey(c)) {
                if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty(); // every opener must have been closed
    }
}

Common mistakes

Popping from an empty stack on a leading closer ("]"): make sure that path returns false rather than throwing.

Example 1

Example 2

The buggy code

Hints

Find and fix the bug

Solution and explanation

Fixed version

Common mistakes

Example 1

Example 2

The buggy code

Hints

Find and fix the bug

Solution and explanation

Fixed version

Common mistakes

More Code Clinic: Find the Bug problems