Press "Enter" to skip to content

Posts published in “Stack”

94. Binary Tree Inorder Traversal (javascript)

By stone on April 4, 2021

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;
}

LeetCode 316. Remove Duplicate Letters (javascript)

By stone on March 28, 2021

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('');
};

LeetCode 224. Basic Calculator (javascript)

By stone on March 28, 2021

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;
};

LeetCode 155. Min Stack (javascript)

By stone on March 28, 2021

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()
 */

LeetCode 32. Longest Valid Parentheses (javascript)

By stone on March 28, 2021

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;
};

LeetCode 20. Valid Parentheses (javascript)

By stone on March 28, 2021

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;
};