My journey in competitive programming

Today's Learning: Balanced Parentheses and Min Stack

Hey, guys!

Today, I concentrated on two very important problems that really helped me understand stacks and parentheses better. Here's what I was working on:

Check for Balanced Parentheses

I began with the question of whether the parentheses of a string are balanced. A string is balanced when all the open parentheses correspond to well-matched closed ones and the order is right. For example,, {[()]}, and ([]) are all balanced, but ([)] and ((())) are not.

I used the stack abstract data type to solve this. The idea here is to push every opening parenthesis onto the stack and then check for every closing parenthesis whether it matches with the most recent opening parenthesis that can be popped from the stack. If at the end, the stack is empty then it means the parentheses were balanced otherwise they weren't. This problem helped me much better understand stacks and how expressions could be processed in this efficient manner.

Implement Min Stack

Next, I wrote code to implement a Min Stack. A min stack is a stack supporting standard stack operations-push, pop, top, and offering a function to get the minimum element in constant time. So, the challenge was that to implement the stack, I must keep track of the minimum element while making standard stack operations.

I solved this using two stacks: one for the actual stack operations and the other maintaining the minimum elements. At every push, I check the element being pushed against the current minimum; if less than or equal to the current minimum, I also push it onto the min stack. On pop elements, I pop from the min stack also if it matches the current minimum.

I hope my experience is helpful.