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.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

React native drawer — custom one

React Native Boilerplate

Remote File Operations using JSch

Shipping npm modules with SQLite

Why and how we are doing E2E Tests

Each view can generate many different pages depending on how their configuration files are set.

ES6 — Object vs. Map for storing key value pairs

Hello Cypress!!

Anatomy of JavaScript Fetch

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Valentin Placido

Valentin Placido

More from Medium

First Team Project at Masai School(Gift_Cart Website Clone by using HTML, CSS, and JavaScript).

JavaScript, Version Controlling and NoSQL

.JS dys-function-ality

THE CLONED WEBSITE: Cloning Period of Pepperfry.com