LeetCode 921. Minimum Add to Make Parentheses Valid — JavaScript Basics

LeetCode has been my go to resource for practicing interview questions or just to learn new methods implement a more efficient solution to a common problem. This post will focus on finding a solution to LeetCode problem 921 titled Minimum Add to Make Parentheses Valid. This problem is under the medium difficulty. The problem is implemented using a stack and iteration with a counter which will be returned at the end of the operation.

The Challenge

Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.

Formally, a parentheses string is valid if and only if:

• It is the empty string, or
• It can be written as AB (A concatenated with B), where A and B are valid strings, or
• It can be written as (A), where A is a valid string.

Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

Example 1:

Input: "())"
Output: 1

Example 2:

Input: "((("
Output: 3

Example 3:

Input: "()"
Output: 0

Example 4:

Input: "()))(("
Output: 4

Note:

1. S.length <= 1000
2. S only consists of '(' and ')' characters.

Implementing The Solution

To solve the challenge we will use a stack and a counter variable to keep track of the number of incomplete parentheses. The logic is as follows:

1. Iterate through each character in the string
2. Check if the character is a closing parentheses, if it is then check if the stack is empty, if it is empty then add 1 to the counter, if the stack is not empty use the pop method to remove the most recent element in the stack.
3. If the character is not a closing parentheses add the opening parentheses to the top of the stack by using the push method.
4. This will close out the for loop and all we have to do is to return the counter but add any remaining characters that were leftover in the stack.

Below is the full implementation of the logic.

var minAddToMakeValid = function(S) {
    let stack = [], count = 0;
    for (let c of S) {
        if (c === ')') {
            if (stack.length === 0) {
                count++;
            } else {
                stack.pop();
            }
        } else {
            stack.push(c);
        }
    }
    return count + stack.length;
};

This implementation passes the tests in LeetCode with a runtime of 92ms and 38.9 MB of memory usage.