Leetcode Solution #6

1. Min Stack

The Problem

Start by reading the description of the problem,

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.

• void push(int val) pushes the element val onto the stack.

• void pop() removes the element on the top of the stack.

• int top() gets the top element of the stack.

• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

It is a leetcode medium question but very easy to attempt.

Refer the example for better understanding,

Approach

Our approach for this question is going to be pretty straightforward, we don't need to do anything special in this question we will just apply our basic knowledge of stack and complete the given functions.

Solution

We have implemented the solution in following ways:

1. Initialise two stacks s1 and min, s1 will store all values and min stack will have the minimum value.

2. MinStack will be empty as it will not do anything specific here.

3. In push function, push the value in main stack(s1), check if min stack is empty or value is less than or equal to current minimum value. If condition is true, it means value is new minimum, so it should be added to min stack.

4. For pop function ensure that s1 is not empty, check if top value of s1 is equal to top value of min. If so, means that we have to pop top value of min stack.

5. Pop top value from s1.

6. For top function, return top value of s1 stack.

7. For getMin function, return top value of min stack.

2. Evaluate Reverse Polish Notation

The Problem

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

• The valid operators are '+', '-', '*', and '/'.

• Each operand may be an integer or another expression.

• The division between two integers always truncates toward zero.

• There will not be any division by zero.

• The input represents a valid arithmetic expression in a reverse
  polish notation.

• The answer and all the intermediate calculations can be
  represented in a 32-bit integer.

This question is also very basic and is rated medium on leetcode, It is very basic question we just have to evaluate postfix notation.

Refer the examples given below for better understanding

Approaches

1. Iterate over all characters one by one.

2. If character is operand push it in the stack.

3. If character is operator pop two elements from start and perform operation.

Solution

We have achieved this solution by following ways:

1. Initialise a stack to store the result.

2. Iterate over the tokens vector.

3. Check if first character of token is digit, then check if it has atleast 2 characters and negative and second character must be digit.

4. If any of above is true convert string to int and push it in stack.

5. Else if the character is an operator, There are two operands at top of stack value 1 and value 2.

6. Since token is an operator now based on operator check the case and push the value.

7. The final result is at top of the stack.

I hope the solutions I have provided are understandable and explanations are easy to understand.

Thank You

You can connect with me on Linkedin