Stack: Practice Problems with Solutions

var isValid = function(s) {
    const stack = [];
    const matches = { ')': '(', '}': '{', ']': '[' };

    for (const c of s) {
        if (matches[c]) {
            // A closer must match the most recent unclosed
            // opener, which is the stack top.
            if (stack.pop() !== matches[c]) return false;
        } else {
            stack.push(c);
        }
    }

    // Openers left on the stack were never closed.
    return stack.length === 0;
};

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        matches = {")": "(", "}": "{", "]": "["}

        for c in s:
            if c in matches:
                # The top of the stack is the most recent
                # unclosed opener. It must pair with c.
                if not stack or stack.pop() != matches[c]:
                    return False
            else:
                stack.append(c)

        return not stack

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                // A closer with nothing on the stack is
                // invalid, and so is a mismatched top.
                if (stack.isEmpty()) return false;
                char open = stack.pop();
                if (c == ')' && open != '(') return false;
                if (c == '}' && open != '{') return false;
                if (c == ']' && open != '[') return false;
            }
        }

        return stack.isEmpty();
    }
}

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;

        for (char c : s) {
            if (c == '(' || c == '{' || c == '[') {
                st.push(c);
            } else {
                if (st.empty()) return false;
                char open = st.top();
                st.pop();
                if (c == ')' && open != '(') return false;
                if (c == '}' && open != '{') return false;
                if (c == ']' && open != '[') return false;
            }
        }

        return st.empty();
    }
};

func isValid(s string) bool {
    stack := []rune{}
    matches := map[rune]rune{')': '(', '}': '{', ']': '['}

    for _, c := range s {
        if open, ok := matches[c]; ok {
            // Pop the most recent unclosed opener and
            // compare it with the closer at hand.
            if len(stack) == 0 || stack[len(stack)-1] != open {
                return false
            }
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, c)
        }
    }

    return len(stack) == 0
}

def is_valid(s)
    stack = []
    matches = { ')' => '(', '}' => '{', ']' => '[' }

    s.each_char do |c|
        if matches.key?(c)
            return false if stack.empty? || stack.pop != matches[c]
        else
            stack.push(c)
        end
    end

    stack.empty?
end

var backspaceCompare = function(s, t) {
    const build = (str) => {
        const stack = [];
        for (const char of str) {
            if (char === '#') {
                // A backspace removes the most recent
                // character, which is the stack top.
                stack.pop();
            } else {
                stack.push(char);
            }
        }
        return stack.join('');
    };
    return build(s) === build(t);
};

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def build(string: str) -> str:
            stack = []
            for char in string:
                if char == "#":
                    # Pop only when a character exists.
                    # A backspace on an empty stack is a no-op.
                    if stack:
                        stack.pop()
                else:
                    stack.append(char)
            return "".join(stack)

        return build(s) == build(t)

class Solution {
    public boolean backspaceCompare(String s, String t) {
        return build(s).equals(build(t));
    }

    private String build(String str) {
        Stack<Character> stack = new Stack<>();
        for (char c : str.toCharArray()) {
            if (c != '#') {
                stack.push(c);
            } else if (!stack.isEmpty()) {
                // A backspace only removes when there is
                // a character above it to remove.
                stack.pop();
            }
        }
        return String.valueOf(stack);
    }
}

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        auto build = [](string str) {
            string stack = "";
            for (char c : str) {
                if (c != '#') {
                    stack.push_back(c);
                } else if (!stack.empty()) {
                    // A backspace on an empty result is
                    // a no-op, so guard before popping.
                    stack.pop_back();
                }
            }
            return stack;
        };
        return build(s) == build(t);
    }
};

func backspaceCompare(s string, t string) bool {
    build := func(str string) string {
        var stack []rune
        for _, char := range str {
            if char == '#' {
                // A backspace removes the most recent
                // character. Empty stack means no-op.
                if len(stack) > 0 {
                    stack = stack[:len(stack)-1]
                }
            } else {
                stack = append(stack, char)
            }
        }
        return string(stack)
    }
    return build(s) == build(t)
}

def backspace_compare(s, t)
    build = ->(str) do
        stack = []
        str.each_char do |c|
            if c == '#'
                stack.pop
            else
                stack.push(c)
            end
        end
        stack.join
    end
    build.call(s) == build.call(t)
end

var evalRPN = function(tokens) {
    const stack = [];
    const ops = {
        '+': (a, b) => a + b,
        '-': (a, b) => a - b,
        '*': (a, b) => a * b,
        // Integer division must truncate toward zero,
        // so Math.trunc beats Math.floor here.
        '/': (a, b) => Math.trunc(a / b)
    };

    for (const token of tokens) {
        if (ops[token]) {
            // The first pop is the right operand because
            // it sits above the left one on the stack.
            const b = stack.pop();
            const a = stack.pop();
            stack.push(ops[token](a, b));
        } else {
            stack.push(Number(token));
        }
    }

    return stack[0];
};

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []

        for t in tokens:
            if t not in "+-*/":
                stack.append(int(t))
            else:
                # r is the top of the stack, so it is the
                # right operand. l is the left operand.
                r, l = stack.pop(), stack.pop()
                if t == "+":
                    stack.append(l + r)
                elif t == "-":
                    stack.append(l - r)
                elif t == "*":
                    stack.append(l * r)
                else:
                    # int() truncates toward zero, which
                    # matches the division requirement.
                    stack.append(int(l / r))

        return stack.pop()

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();

        for (String t : tokens) {
            if ("+-*/".contains(t)) {
                // First pop is the right operand, second is left.
                int r = stack.pop();
                int l = stack.pop();
                if (t.equals("+")) stack.push(l + r);
                else if (t.equals("-")) stack.push(l - r);
                else if (t.equals("*")) stack.push(l * r);
                // Java integer division truncates toward zero.
                else stack.push(l / r);
            } else {
                stack.push(Integer.parseInt(t));
            }
        }

        return stack.pop();
    }
}

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;

        for (string& t : tokens) {
            if (t == "+" || t == "-" || t == "*" || t == "/") {
                // First pop is the right operand, second is left,
                // because the left operand was pushed earlier.
                int r = st.top(); st.pop();
                int l = st.top(); st.pop();
                if (t == "+") st.push(l + r);
                else if (t == "-") st.push(l - r);
                else if (t == "*") st.push(l * r);
                // C++ integer division truncates toward zero.
                else st.push(l / r);
            } else {
                st.push(stoi(t));
            }
        }

        return st.top();
    }
};

import "strconv"

func evalRPN(tokens []string) int {
    stack := []int{}

    for _, t := range tokens {
        if val, err := strconv.Atoi(t); err == nil {
            stack = append(stack, val)
        } else {
            // The last element is the right operand because
            // it was pushed most recently.
            r := stack[len(stack)-1]
            l := stack[len(stack)-2]
            stack = stack[:len(stack)-2]

            var res int
            switch t {
            case "+":
                res = l + r
            case "-":
                res = l - r
            case "*":
                res = l * r
            case "/":
                res = l / r // Go truncates toward zero
            }
            stack = append(stack, res)
        }
    }

    return stack[0]
}

def eval_rpn(tokens)
    stack = []

    tokens.each do |t|
        case t
        when "+", "-", "*", "/"
            # First pop is the right operand, second is left.
            r = stack.pop
            l = stack.pop
            case t
            when "+" then stack.push(l + r)
            when "-" then stack.push(l - r)
            when "*" then stack.push(l * r)
            # fdiv then to_i truncates toward zero, where
            # Ruby's integer division would floor instead.
            when "/" then stack.push(l.fdiv(r).to_i)
            end
        else
            stack.push(t.to_i)
        end
    end

    stack.pop
end

var dailyTemperatures = function(temperatures) {
    const res = new Array(temperatures.length).fill(0);
    const stack = []; // indices of days still waiting

    for (let i = 0; i < temperatures.length; i++) {
        // Today is warmer than the waiting days on top.
        // Their next warmer day is today.
        while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
            const idx = stack.pop();
            res[idx] = i - idx;
        }
        stack.push(i);
    }
    return res;
};

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = [0] * len(temperatures)
        stack = []  # indices of days still waiting

        for i, t in enumerate(temperatures):
            # Today ends the wait for every cooler day
            # stacked on top. Their answer is today.
            while stack and t > temperatures[stack[-1]]:
                idx = stack.pop()
                res[idx] = i - idx
            stack.append(i)

        return res

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < temperatures.length; i++) {
            // Today is warmer than the waiting days, so
            // each one gets its distance to today.
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int idx = stack.pop();
                res[idx] = i - idx;
            }
            stack.push(i);
        }
        return res;
    }
}

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> res(temperatures.size(), 0);
        stack<int> st;

        for (int i = 0; i < temperatures.size(); i++) {
            // Every cooler day waiting on the stack finds
            // its next warmer day at the current index.
            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
                int idx = st.top();
                st.pop();
                res[idx] = i - idx;
            }
            st.push(i);
        }
        return res;
    }
};

func dailyTemperatures(temperatures []int) []int {
    res := make([]int, len(temperatures))
    stack := []int{}

    for i, t := range temperatures {
        // Today resolves the wait of every cooler day
        // sitting above the stack.
        for len(stack) > 0 && t > temperatures[stack[len(stack)-1]] {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            res[idx] = i - idx
        }
        stack = append(stack, i)
    }
    return res
}

def daily_temperatures(temperatures)
    res = Array.new(temperatures.length, 0)
    stack = [] # indices of days still waiting

    temperatures.each_with_index do |t, i|
        while !stack.empty? && t > temperatures[stack.last]
            idx = stack.pop
            res[idx] = i - idx
        end
        stack.push(i)
    end
    res
end

class MinStack {
    constructor() {
        this.stack = [];
        this.minStack = [];
    }

    push(val) {
        this.stack.push(val);
        // minStack only records new minimums, so its top is
        // always the minimum of the whole stack.
        if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
            this.minStack.push(val);
        }
    }

    pop() {
        const val = this.stack.pop();
        // If the popped value was the current minimum, the
        // next entry down in minStack is the new minimum.
        if (val === this.minStack[this.minStack.length - 1]) {
            this.minStack.pop();
        }
    }

    top() {
        return this.stack[this.stack.length - 1];
    }

    getMin() {
        return this.minStack[this.minStack.length - 1];
    }
}

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        # Only release the minimum when the value being
        # removed actually was the minimum.
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def get_min(self) -> int:
        return self.min_stack[-1]

class MinStack {
    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        if (stack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

class MinStack {
private:
    stack<int> s;
    stack<int> min_s;

public:
    void push(int val) {
        s.push(val);
        if (min_s.empty() || val <= min_s.top()) {
            min_s.push(val);
        }
    }

    void pop() {
        if (s.top() == min_s.top()) {
            min_s.pop();
        }
        s.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return min_s.top();
    }
};

type MinStack struct {
    stack    []int
    minStack []int
}

func Constructor() MinStack {
    return MinStack{}
}

func (this *MinStack) Push(val int) {
    this.stack = append(this.stack, val)
    if len(this.minStack) == 0 || val <= this.minStack[len(this.minStack)-1] {
        this.minStack = append(this.minStack, val)
    }
}

func (this *MinStack) Pop() {
    val := this.stack[len(this.stack)-1]
    this.stack = this.stack[:len(this.stack)-1]
    if val == this.minStack[len(this.minStack)-1] {
        this.minStack = this.minStack[:len(this.minStack)-1]
    }
}

func (this *MinStack) Top() int {
    return this.stack[len(this.stack)-1]
}

func (this *MinStack) GetMin() int {
    return this.minStack[len(this.minStack)-1]
}

class MinStack
    def initialize
        @stack = []
        @min_stack = []
    end

    def push(val)
        @stack.push(val)
        if @min_stack.empty? || val <= @min_stack.last
            @min_stack.push(val)
        end
    end

    def pop
        val = @stack.pop
        @min_stack.pop if val == @min_stack.last
    end

    def top
        @stack.last
    end

    def get_min
        @min_stack.last
    end
end

var largestRectangleArea = function(heights) {
    let maxArea = 0;
    const stack = [-1]; // anchor index below the first bar

    for (let i = 0; i < heights.length; i++) {
        // A shorter bar closes the rectangle of every taller
        // bar above it. The width runs from the new bar to
        // the next bar still on the stack.
        while (stack[stack.length - 1] !== -1 && heights[i] <= heights[stack[stack.length - 1]]) {
            const h = heights[stack.pop()];
            const w = i - stack[stack.length - 1] - 1;
            maxArea = Math.max(maxArea, h * w);
        }
        stack.push(i);
    }

    // Bars still on the stack run to the end of the array.
    while (stack[stack.length - 1] !== -1) {
        const h = heights[stack.pop()];
        const w = heights.length - stack[stack.length - 1] - 1;
        maxArea = Math.max(maxArea, h * w);
    }
    return maxArea;
};

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = [-1]  # anchor index below the first bar
        max_area = 0

        for i in range(len(heights)):
            # A shorter bar closes the rectangles of taller
            # bars on the stack. Their width is the distance
            # between the new bar and the next bar below.
            while stack[-1] != -1 and heights[i] <= heights[stack[-1]]:
                h = heights[stack.pop()]
                w = i - stack[-1] - 1
                max_area = max(max_area, h * w)
            stack.append(i)

        # Bars left on the stack extend to the array end.
        while stack[-1] != -1:
            h = heights[stack.pop()]
            w = len(heights) - stack[-1] - 1
            max_area = max(max_area, h * w)

        return max_area

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1); // anchor index below the first bar
        int maxArea = 0;

        for (int i = 0; i < heights.length; i++) {
            // The new bar becomes the right boundary of every
            // taller bar above it on the stack.
            while (stack.peek() != -1 && heights[i] <= heights[stack.peek()]) {
                int h = heights[stack.pop()];
                int w = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, h * w);
            }
            stack.push(i);
        }

        // Bars still on the stack extend to the array end.
        while (stack.peek() != -1) {
            int h = heights[stack.pop()];
            int w = heights.length - stack.peek() - 1;
            maxArea = Math.max(maxArea, h * w);
        }
        return maxArea;
    }
}

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> s;
        s.push(-1); // anchor index below the first bar
        int max_area = 0;

        for (int i = 0; i < heights.size(); i++) {
            // A shorter bar closes the rectangles of taller
            // bars above it, with the new bar as the right
            // boundary and the stack top below as the left.
            while (s.top() != -1 && heights[i] <= heights[s.top()]) {
                int h = heights[s.top()];
                s.pop();
                int w = i - s.top() - 1;
                max_area = max(max_area, h * w);
            }
            s.push(i);
        }

        // Remaining bars run to the end of the array.
        while (s.top() != -1) {
            int h = heights[s.top()];
            s.pop();
            int w = heights.size() - s.top() - 1;
            max_area = max(max_area, h * w);
        }
        return max_area;
    }
};

func largestRectangleArea(heights []int) int {
    stack := []int{-1} // anchor index below the first bar
    maxArea := 0

    for i, h := range heights {
        // The new bar closes the rectangle of every taller
        // bar above it. Width spans from the new bar back
        // to the next bar still on the stack.
        for stack[len(stack)-1] != -1 && h <= heights[stack[len(stack)-1]] {
            height := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]
            width := i - stack[len(stack)-1] - 1
            if height*width > maxArea {
                maxArea = height * width
            }
        }
        stack = append(stack, i)
    }

    // Bars still on the stack extend to the array end.
    for stack[len(stack)-1] != -1 {
        height := heights[stack[len(stack)-1]]
        stack = stack[:len(stack)-1]
        width := len(heights) - stack[len(stack)-1] - 1
        if height*width > maxArea {
            maxArea = height * width
        }
    }
    return maxArea
}

def largest_rectangle_area(heights)
    stack = [-1] # anchor index below the first bar
    max_area = 0

    heights.each_with_index do |h, i|
        while stack.last != -1 && h <= heights[stack.last]
            height = heights[stack.pop]
            width = i - stack.last - 1
            max_area = [max_area, height * width].max
        end
        stack.push(i)
    end

    while stack.last != -1
        height = heights[stack.pop]
        width = heights.length - stack.last - 1
        max_area = [max_area, height * width].max
    end
    max_area
end

var trap = function(height) {
    let water = 0;
    const stack = [];

    for (let i = 0; i < height.length; i++) {
        // The current bar closes pits above the stack top.
        // Each pop is one horizontal layer of water.
        while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
            const top = stack.pop();
            // No left wall means no pit, so nothing to trap.
            if (stack.length === 0) break;
            const distance = i - stack[stack.length - 1] - 1;
            const boundedHeight = Math.min(height[i], height[stack[stack.length - 1]]) - height[top];
            water += distance * boundedHeight;
        }
        stack.push(i);
    }
    return water;
};

class Solution:
    def trap(self, height: List[int]) -> int:
        water = 0
        stack = []

        for i, h in enumerate(height):
            # A taller current bar closes the pit sitting on
            # top of the stack, one layer at a time.
            while stack and h > height[stack[-1]]:
                top = stack.pop()
                # Without a left wall there is no pit.
                if not stack:
                    break
                distance = i - stack[-1] - 1
                bounded_height = min(h, height[stack[-1]]) - height[top]
                water += distance * bounded_height
            stack.append(i)

        return water

class Solution {
    public int trap(int[] height) {
        int water = 0;
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < height.length; i++) {
            // The current bar closes pits above the stack top,
            // and each pop traps one horizontal layer.
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                // No left wall means no pit to trap water.
                if (stack.isEmpty()) break;
                int distance = i - stack.peek() - 1;
                int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[top];
                water += distance * boundedHeight;
            }
            stack.push(i);
        }
        return water;
    }
}