Coding Interview Questions | Valid Parentheses

December 14th, 2023

Introduction:

This summary will talk about my solution to the valid parentheses problem as seen on leetcode here.

Solution:

function isValid(s: string): boolean {
  const openCloseParensMap = new Map([
    ["(", ")"],
    ["[", "]"],
    ["{", "}"],
  ]);
  const parenStack = [];

  for (let sIdx = 0; sIdx < s.length; sIdx++) {
    const currentChar = s[sIdx];
    const isOpenParen = openCloseParensMap.has(currentChar);

    if (isOpenParen) {
      parenStack.push(currentChar);
      continue;
    }

    const lastOpenParen = parenStack.pop();
    // No open parens exist in string,
    // a close paren alone is invalid
    if (!lastOpenParen) {
      return false;
    }

    if (openCloseParensMap.get(lastOpenParen) !== currentChar) {
      return false;
    }
  }

  return parenStack.length === 0;
}

Summary:

The isValid function above determines the validity of a string containing parentheses by utilizing a stack-based approach. It iterates through each character in the input string, maintaining a stack to track open parentheses. When an open parenthesis is encountered, it is pushed onto the stack. Upon encountering a close parenthesis, the corresponding open parenthesis is popped from the stack, and the validity is checked.

The function returns false if a close parenthesis is found without a matching open parenthesis or if there is a mismatch between open and close parentheses. The function ensures correctness by verifying that the stack is empty at the end of the iteration. The use of a map facilitates easy lookup for the corresponding close parenthesis. A goal of this function was to execute in one-pass, which was done and ensures a solution with a linear time complexity.