Problem 1: Asteroid Collection

Link to the problem: https://leetcode.com/problems/asteroid-collision/description/

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int a : asteroids) {
            if(a > 0){
                stack.push(a);
            }else{
                while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < -a)
                    stack.pop();
                if (stack.isEmpty() || stack.peek() < 0) stack.push(a);
                if (stack.peek() == -a) stack.pop();
            }
        }
        int[] res = new int[stack.size()];
        int i = stack.size() - 1;
        while(!stack.isEmpty()) res[i--] = stack.pop();
        return res;   
    }
}

---

Problem 2: Trapping Rain Water

Link to the problem: https://leetcode.com/problems/trapping-rain-water/

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        int currMax = 0;
        for(int i=0; i<n; i++){
            leftMax[i] = currMax;
            currMax = currMax>height[i]?currMax:height[i];
        }
        currMax = 0;
        for(int i=n-1; i>=0; i--){
            rightMax[i] = currMax;
            currMax = currMax>height[i]?currMax:height[i];
        }
        int res = 0;
        for(int i=0; i<n; i++){
            int num = Math.min(rightMax[i], leftMax[i])-height[i];
            if(num>0)
                res+=num;
        }
        return res;
    }
}

---

Problem 3: Basic Calculator

Link to the problem: https://leetcode.com/problems/basic-calculator/

class Solution {
    public int calculate(String s) {
        int length = s.length();
        int sign = 1;
        int ans = 0;
        int currNo = 0;
        Stack<Integer> stack = new Stack<>();

        for(int i = 0; i < length; i++) {
            if(Character.isDigit(s.charAt(i))) {
                currNo = s.charAt(i) - '0';
                while(i + 1 < length && Character.isDigit(s.charAt(i + 1))) {
                    currNo = currNo * 10 + s.charAt(i + 1) - '0';
                    i++;
                }
                currNo = currNo * sign;
                ans += currNo;
                currNo = 0;
                sign = 1;
            }else if(s.charAt(i) == '+') {
                sign = 1;
            }else if(s.charAt(i) == '-') {
                sign = -1;
            }else if(s.charAt(i) == '(') {
                stack.push(ans);
                stack.push(sign);
                ans = 0;
                sign = 1;
            }else if(s.charAt(i) == ')') {
                int prevSign = stack.pop();
                ans = prevSign * ans;
                int precAns = stack.pop();
                ans = precAns + ans;
            }
        }
        return ans;
    }
}

---

Problem 4: longest Valid Parentheses

Link to the problem: https://leetcode.com/problems/longest-valid-parentheses/

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int max_len = 0;

        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(') stack.push(i);
            else{
                stack.pop();
                if(stack.isEmpty()) stack.push(i);
                else max_len = Math.max(max_len, i - stack.peek());
            }
        }
        return max_len;
    }
}

---

Problem 5: Maximum Frequency Stack

Link to the problem: https://leetcode.com/problems/maximum-frequency-stack/

class FreqStack {
    HashMap<Integer, Integer> fmap;
    List<Stack<Integer>> stack;

    public FreqStack() {
        fmap = new HashMap();
        stack = new ArrayList();
        stack.add(new Stack());
    }

    public void push(int x) {
        int freq = fmap.getOrDefault(x, 0) + 1;
        fmap.put(x, freq);
        if (freq == stack.size()) stack.add(new Stack());
        stack.get(freq).add(x);
    }

    public int pop() {
        Stack<Integer> top = stack.get(stack.size()-1);
        int x = top.pop();
        if (top.size() == 0) stack.remove(stack.size()-1);
        fmap.put(x, fmap.get(x) - 1);
        return x;
    }
}

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack obj = new FreqStack();
 * obj.push(val);
 * int param_2 = obj.pop();
 */

---