Understanding Data Structures in JavaScript: Stacks

Photo by Eaters Collective on Unsplash

I recently wrote an article about solving an algorithm problem in JavaScript using queues. Let’s now take a look at a solution involving a stack.

What is a stack? Think of a stack of books (or macaroons :)). Let’s say you have three books: a red, green, and blue book. You would like to organize your books in a tiny cubicle of a bookshelf. You put the red book in the cubicle first, then the green book on top of the red, and then finally the blue book on top of the green book.

Cubicles in a shelf

To unstack these books, it will be easiest to take the topmost book from the stack then continue downwards. If you need to read the red book, you won't be able to grab it out of underneath the other books because your cubicle is very small. You would take the blue book out first, then the green, then the red book. So in contrast to a queue where the first item to be queued is the first item to be dequeued, in a stack the first item to be stacked will be the last item to be removed from the stack. Similarly to queues, in JavaScript, we can use an array to stack (Array.push()) and unstack (Array.pop()) items from a stack. Array.pop() removes the most recently added item from the array.

To see stacks in action, we will take a look at the Minimum Add to Make Parentheses Valid algorithm question. The prompt directly from LeetCode is as follows:

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.

In other words, the input to the solution function will either be a string with any combination of one or both of “(” and “)” or an empty string. If given the following string: “())”, our solution function should return 1. The first left parenthesis can pair off with the right parenthesis that immediately follows it. However, the third parenthesis has no left parenthesis to pair off with, so we need one (left) parenthesis to make the given string valid.

Note that we cannot simply count the number of left and right parentheses to determine our answer. For example, in the string “())(”, there are two left parentheses and two right parentheses. A simple count will lead us to believe that the parentheses string is valid. However, we must pair off the parentheses without moving individual items of the string around. For example, the third parenthesis in this string cannot be moved to the last position in order to be paired off with the fourth parenthesis. Parentheses must be paired in place. So, the correct response to this problem would be 2. We need one parenthesis to pair with the third parenthesis and one for the fourth.

Let’s take a look at another example to understand the solution better. Given the string “())((", let’s find out how many parentheses we have to add to make the string valid. First of all, we need a way to pair off left and right parentheses as they occur. A time-efficient way of doing this will involve looping through the string only once and storing the left parentheses and pairing the stored left parentheses with right parentheses.

As stated in the question prompt, if the given input string is an empty string, the string is valid.

if(S == ""){
        return 0;
    }

Next, we initialize the stack for the left parentheses and a count for any unpaired right parentheses that we come across as we loop through the string.

let leftParens = []
let right = 0;

Then we loop through the given string, storing each left parenthesis and paring off the right parentheses with any left parentheses in the stack.

for(let i = 0; i< S.length; i++){
        if(S[i] == "("){
           leftParens.push(S[i])   
        }
       else if(S[i] == ")"){
           if(leftParens.length > 0){
               leftParens.pop()
           }
           else{
               right++
           }
        }
    }

Going back to our example, “())((“ . I have included a visual to number the parentheses in the string.

Numbering the parentheses in the string

The first parenthesis gets pushed in first. Now leftParens looks like this:

[(]

We then arrive at the second parenthesis and pair it off with the parenthesis in leftParens by unstacking the left parenthesis from leftParens . leftParens will now be an empty array. When we arrive at the third parenthesis, it is a right parenthesis and there are no left parentheses in leftParens to pair it off with. This brings us to the final else block in the code block above. We increase the count of the unpaired right parentheses, so right will be equal to one.

The fourth and fifth parentheses are left parentheses, so we will push them again into leftParens . leftParens will now look like this:

[((]

At the end of the for loop, how do we know how many unpaired parentheses we have? Well, right contains the number of right parentheses that could not be paired and leftParens also contains the left parentheses that have not be paired. So, counting the number of items in leftParens and adding that to the value of right will give us our answer.

leftParens.length + right;

Putting everything together:

var minAddToMakeValid = function(S) {
    if(S == ""){
        return 0;
    }
   let leftParens = []
   let right = 0;
    
    for(let i = 0; i< S.length; i++){
        if(S[i] == "("){
           leftParens.push(S[i])   
        }
       else if(S[i] == ")"){
           if(leftParens.length > 0){
               leftParens.pop()
           }
           else{
               right++
           }
        }
    }
    return leftParens.length + right;
};