# Posts tagged as “stack”

Given the `root` of a binary tree, return the inorder traversal of its nodes’ values.

Example 1:

```Input: root = [1,null,2,3]
Output: [1,3,2]
```

Example 2:

```Input: root = []
Output: []
```

Example 3:

```Input: root = [1]
Output: [1]
```

Example 4:

```Input: root = [1,2]
Output: [2,1]
```

Example 5:

```Input: root = [1,null,2]
Output: [1,2]
```

Constraints:

• The number of nodes in the tree is in the range `[0, 100]`.
• `-100 <= Node.val <= 100`

Idea:

Iterating method using Stack

Solution:

``````/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
let stack = [];
let res = [];

while(root !== null || stack.length !== 0) {
while(root !== null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
res.push(root.val);
root = root.right;
}
return res;
}``````

Given a string `s`, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

Example 1:

```Input: s = "bcabc"
Output: "abc"
```

Example 2:

```Input: s = "cbacdcbc"
Output: "acdb"
```

Constraints:

• `1 <= s.length <= 104`
• `s` consists of lowercase English letters.

Idea:

Hash + Stack

Solution:

``````/**
* @param {string} s
* @return {string}
*/
var removeDuplicateLetters = function(s) {
let chars = s.split('');
// record the index of last occurrence for each character
let lastIndex = new Map();
for (let i = 0; i < chars.length; i++) {
lastIndex.set(chars[i], i);
}
let stack = [];
let used = new Map();
for (let i = 0; i < chars.length; i++) {
// if the current character has been used, skip it
if (used.has(chars[i]) && used.get(chars[i])) continue;

// if the current character is smaller than stack[stack.length - 1]
// and the last index of stack[stack.length - 1] is larger than i, it means we can use it later,
// so we pop it out and mark used as false
while (stack.length !== 0 && chars[i] < stack[stack.length - 1] && lastIndex.get(stack[stack.length - 1]) > i)
used.set(stack.pop(), false);

stack.push(chars[i]);
used.set(chars[i], true);
}
let ans = [];
while (stack.length !== 0) ans.push(stack.pop());
return ans.reverse().join('');
};``````

Given a string `s` representing an expression, implement a basic calculator to evaluate it.

Example 1:

```Input: s = "1 + 1"
Output: 2
```

Example 2:

```Input: s = " 2-1 + 2 "
Output: 3
```

Example 3:

```Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23
```

Constraints:

• `1 <= s.length <= 3 * 105`
• `s` consists of digits, `'+'``'-'``'('``')'`, and `' '`.
• `s` represents a valid expression.

Solution:

``````/**
* @param {string} s
* @return {number}
*/
var calculate = function(s) {
let len = s.length;
if (len === 0) return 0;
let stack = [];
let res = 0;
let sign = 1;

// remove space
s.replace(" ", "");
for (let i = 0; i < len; i++) {
let n = s.charAt(i);
if (!isNaN(parseInt(n))) {
let cur = parseInt(n);
while (i + 1 < len && !isNaN(parseInt(s.charAt(i + 1)))) {
cur = cur * 10 + parseInt(s.charAt(i + 1));
i++;
}
res += cur * sign;
} else if (n === '-') {
sign = -1;
} else if (n === '+') {
sign = 1;
} else if (n === '(') {
stack.push(res);
res = 0;
stack.push(sign);
sign = 1;
} else if (n === ')') {
res = res * stack.pop() + stack.pop();
}
}

return res;
};``````

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(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.

Example 1:

```Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]```

Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2

Constraints:

• `-231 <= val <= 231 - 1`
• Methods `pop``top` and `getMin` operations will always be called on non-empty stacks.
• At most `3 * 104` calls will be made to `push``pop``top`, and `getMin`.

Idea:

Use two stacks to solve this problem

Solution:

``````/**
* initialize your data structure here.
*/
var MinStack = function() {
this.min = [];
this.stack = [];
};

/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
this.stack.push(x);
let min = this.getMin();
if (min === undefined || min >= x) {
this.min.push(x);
}
};

/**
* @return {void}
*/
MinStack.prototype.pop = function() {
let val = this.stack.pop();
let min = this.getMin();
if (val === min) this.min.pop();
};

/**
* @return {number}
*/
MinStack.prototype.top = function() {
return this.stack[this.stack.length - 1];
};

/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
return this.min[this.min.length - 1];
};

/**
* Your MinStack object will be instantiated and called as such:
* var obj = new MinStack()
* obj.push(x)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.getMin()
*/``````

Given a string containing just the characters `'('` and `')'`, find the length of the longest valid (well-formed) parentheses substring.

Example 1:

```Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
```

Example 2:

```Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
```

Example 3:

```Input: s = ""
Output: 0
```

Constraints:

• `0 <= s.length <= 3 * 104`
• `s[i]` is `'('`, or `')'`.

Solution:

``````/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function(s) {
let stack = [];
// track the start position
let start = 0;
let ans = 0;

for (let i = 0; i < s.length; i++) {
// open parenthese '(' push that index of '('
if (s[i] === '(') {
stack.push(i);
} else {
// if stack empty => invalid, start from i + 1
if (stack.length === 0) {
start = i + 1;
} else {
stack.pop();
// empty stack: calculate [start...i]
// or Not empty stack calculate [index of '('...i]
// store the max length
ans = Math.max(ans, stack.length === 0 ? i - start + 1 : i - stack[stack.length - 1]);
}
}
}
return ans;
};``````

Given a string `s` containing just the characters `'('``')'``'{'``'}'``'['` and `']'`, determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Example 1:

```Input: s = "()"
Output: true
```

Example 2:

```Input: s = "()[]{}"
Output: true
```

Example 3:

```Input: s = "(]"
Output: false
```

Example 4:

```Input: s = "([)]"
Output: false
```

Example 5:

```Input: s = "{[]}"
Output: true
```

Constraints:

• `1 <= s.length <= 104`
• `s` consists of parentheses only `'()[]{}'`.

Idea:

Stack

Solution:

``````/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
let stack = [];
let open = {'(' : ')', '{' : '}', '[' : ']'};
let close = {')':true, '}':true, ']': true};

for (let char of s) {
if (open[char]) {
stack.push(char);
} else if (close[char]) {
if (open[stack.pop()] !== char) return false;
}
}

return stack.length === 0;
};``````