Stack

https://medium.com/@gregsh9.5/monotonic-queue-notes-980a019d5793 https://medium.com/algorithms-and-leetcode/monotonic-queue-explained-with-leetcode-problems-7db7c530c1d6

71. Simplify Path

Add Strings to stack, pop if meet "..".

    public String simplifyPath(String path) {
        String[] strs = path.split("/");
        Stack<String> stack = new Stack<>();
        for (int i = 1; i < strs.length; i++) {
            if (strs[i].equals("..") && !stack.isEmpty()) {
                stack.pop();
            } else if (!strs[i].equals(".") 
                       && !strs[i].equals("..") 
                       && !strs[i].equals("")) {
                stack.add(strs[i]);
            }
        }
        StringBuilder sb = new StringBuilder("/");
        for (String s : stack) {
            sb.append(s).append("/");
        }
        return sb.length() != 1 
                ? sb.deleteCharAt(sb.length() - 1).toString() 
                : sb.toString();
    }

Next Greater Element

Find the next greater element in array, if no such element, return -1.

Pointer move from end to beginning, use a stack to store all element, but pop values which are smaller than the current value, this way we can keep a non-increasing sequence.

T: O(n) S: O(n)

public int[] nextGreaterElement(int[] nums) {
    Stack<Integer> stack = new Stack<>();
    int[] res = new int[nums.length];
    for (int i = nums.length - 1; i >= 0; i--) {
        while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
            stack.pop();
        }
        res[i] = stack.isEmpty() ? -1 : nums[stack.peek()];
        stack.add(i);
    }
    return res;
}

155. Min Stack

Before add new element. Add the previous min to the stack.

Java

int min = Integer.MAX_VALUE;
Stack<Integer> stack;
/** initialize your data structure here. */
public MinStack() {
    stack = new Stack<>();
}

public void push(int x) {
    if (x <= min) {
        stack.add(min);
        min = x;
    }
    stack.add(x);
}

public void pop() {
    int pop = stack.pop();
    if (pop == min) {
        min = stack.pop();
    }
}

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

public int getMin() {
    return min;
}

Python

Link

232. Implement Queue using Stacks

Use two stacks to flip to get queue.

def __init__(self):
    self.s1 = []
    self.s2 = []

def push(self, x: int) -> None:
    self.s1.append(x)

def pop(self) -> int:
    if self.empty():
        return None
    if not self.s2:
        while self.s1:
            self.s2.append(self.s1.pop())
    return self.s2.pop()
    

def peek(self) -> int:
    if self.empty():
        return None
    if not self.s2:
        while self.s1:
            self.s2.append(self.s1.pop())
    return self.s2[-1]

def empty(self) -> bool:
    return not self.s1 and not self.s2

150. Evaluate Reverse Polish Notation

Loop over the token strings and add to a stack if it is a number. Alternatively run operation if it is an operator.

    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String t : tokens) {
            if ((t.equals("+") || t.equals("/") || t.equals("*") || t.equals("-"))  && !stack.isEmpty()) {
                int a = stack.pop();
                int b = stack.pop();
                if (t.equals("+")) {
                    stack.push(a + b);
                } else if (t.equals("-")) {
                    stack.push(b - a);
                } else if (t.equals("/")) {
                    stack.push(b / a);
                } else if (t.equals("*")) {
                    stack.push(a * b);
                }
            } else {
                stack.add(Integer.valueOf(t));
            }
        }
        return stack.pop();
    }

394. Decode String

Use two stacks, one to store result and the other one store numbers.

• meet "[", add to stack and reset current elements

• meet "]", pop from stack and aggregate results

    public String decodeString(String s) {
        Stack<String> stack = new Stack<>();
        Stack<Integer> nstack = new Stack<>();
        String res = "";
        int num = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (Character.isLetter(c)) {
                res += c;
            } else if (c == '[') {
                stack.add(res);
                nstack.add(num);
                num = 0;
                res = "";
            } else if (c == ']' && !stack.isEmpty() && !nstack.isEmpty()) {
                StringBuilder sb = new StringBuilder(stack.pop());
                int n = nstack.pop();
                for (int k = 0; k < n; k++) {
                    sb.append(res);
                }
                res = sb.toString();
            }
        }
        return res;
    }

739. Daily Temperatures

Same as the problem above. Answer is the distance between peek value and current index.

T: O(n) S: O(n)

Java

    public int[] dailyTemperatures(int[] T) {
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[T.length];
        for (int i = T.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && T[stack.peek()] <= T[i]) {
                stack.pop();
            }
            res[i] = stack.isEmpty() ? 0 : stack.peek() - i;
            stack.add(i);
        }
        return res;
    }

Python

496. Next Greater Element I

Refer to as Next Greater Element.

T: O(n) S: O(n)

Java

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer, Integer> map = new HashMap<>();
    Stack<Integer> stack = new Stack<>();
    for (int i = nums2.length - 1; i >= 0; i--) {
        while (!stack.isEmpty() && nums2[stack.peek()] <= nums2[i]) {
            stack.pop();
        }
        if (!stack.isEmpty()) {
            map.put(nums2[i], nums2[stack.peek()]);
        }
        stack.add(i);
    }
    int[] res = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        if (map.get(nums1[i]) != null) {
            res[i] = map.get(nums1[i]);
        } else {
            res[i] = -1;
        }
    }
    return res;
}

Python

503. Next Greater Element II

Since it is a circular array, one way is looping over the array twice, and maintain the stack and result array. While looping, mod i by n (i % n) as it points to the position on the current array.

    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[n];
        for (int i = n * 2 - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i % n]) {
                stack.pop();
            }
            res[i % n] = stack.isEmpty() ? -1 : nums[stack.peek() % n];
            stack.add(i % n);
        }
        return res;
    }

556. Next Greater Element III

1. If all digits sorted in descending order, then output is always “Not Possible”. For example, 4321.

2. If all digits are sorted in ascending order, then we need to swap last two digits. For example, 1234.

3. For other cases, we need to process the number from rightmost side (why? because we need to find the smallest of all greater numbers)

Algorithm:

1. Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. For example, if the input number is “534976”, we stop at 4 because 4 is smaller than next digit 9. If we do not find such a digit, then output is “Not Possible”.

2. Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’. For “534976″, the right side of 4 contains “976”. The smallest digit greater than 4 is 6.

3. Swap the above found two digits, we get 536974 in above example.

    public int nextGreaterElement(int n) {
        char[] nums = String.valueOf(n).toCharArray();
        
        // 1. 
        int i = nums.length - 1;
        for (; i > 0; i--) {
            if (nums[i - 1] < nums[i]) break;
        }
        if (i == 0) return -1;
        
        // 2
        int x = nums[i - 1], j = i + 1, smallest = i;
        while (j < nums.length) {
            if (nums[j] > x && nums[smallest] >= nums[j]) smallest = j;
            j++;
        }
        // 3 
        char temp = nums[smallest];
        nums[smallest] = nums[i - 1];
        nums[i - 1] = temp;
        Arrays.sort(nums, i , nums.length);
        long val = Long.parseLong(new String(nums));
        return (val <= Integer.MAX_VALUE) ? (int)val : -1;
    }

735. Asteroid Collision

Use stack to add element when it is positive. Otherwise, keep popping the previous one when it is smaller than opposite of current, for eg. [2, 3, -10].

When current and previous are exactly opposite, such as [8, -8], only pop. When the previous is negative, continue push current, eg [-2, -1]

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

31. Next Permutation

Same as 556 above:

1. find the first increase element i from the right

2. find the first element larger than i from the right

3. swap i and j, reverse from i + 1 to end.

    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) j--;
            swap(nums, i, j);
        }
        reverse(nums, i + 1, nums.length - 1);
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    private void reverse(int[] nums, int i, int j) {
        while (i < j) {
            swap(nums, i++, j--);
        }
    }

581. Shortest Unsorted Continuous Subarray

Solution1: Sort and find the start and end of the difference: O(nlogn)

public int findUnsortedSubarray(int[] nums) {
    int[] snums = nums.clone();
    Arrays.sort(nums);
    int start = nums.length, end = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != snums[i]) {
            start = Math.min(start, i);
            end = Math.max(end, i);
        }
    }
    if (end - start >= 0) {
        return end - start + 1;
    }
    return 0;
}

Solution1: Use Monotonic stack to find the smallest start index where it violates the increasing trend. Also find the largest end where it violates the decreasing trend from the back. O(n)

public int findUnsortedSubarray(int[] nums) {
    Stack<Integer> stack = new Stack<>();
    int start = nums.length, end = 0;
    for (int i = 0; i < nums.length; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
            start = Math.min(start, stack.pop());
        }
        stack.add(i);
    }
    stack.clear();
    for (int i = nums.length - 1; i >= 0; i--) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            end = Math.max(end, stack.pop());
        }
        stack.add(i);
    }
    if (end - start <= 0) return 0;
    return end - start + 1;
}

239. Sliding Window Maximum

Maintain a deque while going through Keep only the indexes of elements from the current sliding window. Remove indexes of all elements smaller than the current one, since they will not be the maximum ones.

public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new LinkedList<>();
    // initiate a result array with size n - k + 1
    int[] res = new int[nums.length - k + 1]; 
    for (int i = 0; i < nums.length; i++) {
        // pop First when your first index element exceeds window
        while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
            deque.pollFirst();
        }    
        // keep popping from last when your last element is smaller or equals current num, 
        // which means all element in the deque is larger than current
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
            deque.pollLast();
        }
        // add current number from last
        deque.addLast(i);
        // add to result when window size reach k
        if (i >= k - 1) {
            // everything in deque are large elements. The first is always the max since the deque is monotonic.
            res[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return res;
}

Find all minimum values of sub-matrices size k

given an n x m matrix and a value k, find minimum values for all sub-matrixes of size k

example: given this matrix:

	[
        [-1, 5, 4, 1, -3],
        [4,  3, 1, 1, 6],
        [2, -2, 5, 3, 1],
        [8,  5, 1, 9, -4],
        [12, 3, 5, 8, 1]
    ]

and a k of 3

result:

[
	[-2, -2, -3],
	[-2, -2, -4],
	[-2, -2, -4]
]

First for each column calculate the minimum for each sliding window(vertical direction) of k

Then for each pair of row having col width k, run sliding window (horizontal direction) of k on col data from 1.

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Similar as the question above. It needs to calculate the difference of an interval. Two deque is needed to get the min and max of the interval. The last element is always the largest or smallest. That:

• In min deque, when the last element is larger than current element, poll last

• in max deque, when the last element is smaller than current element, poll last

• when the element reach to the current element, pop first

As well as maintain the longest interval.

public int longestSubarray(int[] nums, int limit) {
    Deque<Integer> minD = new LinkedList<>();
    Deque<Integer> maxD = new LinkedList<>();
    int res = Integer.MIN_VALUE;
    int i = 0, j;
    for (j = 0; j < nums.length; j++) {
        while (!minD.isEmpty() && nums[j] < minD.peekLast()) {
            minD.pollLast();
        }
        while (!maxD.isEmpty() && nums[j] > maxD.peekLast()) {
            maxD.pollLast();
        }
        minD.add(nums[j]);
        maxD.add(nums[j]);
        if (Math.abs(minD.peek() - maxD.peek()) > limit) {
            if (minD.peek() == nums[i]) minD.poll();
            if (maxD.peek() == nums[i]) maxD.poll();
            i++;
        }
    }
    return j - i;
}

84. Largest Rectangle in Histogram

Maintain an increasing monotonic stack. Add a -1 to the stack for easier calculation. When encounter a decreasing element, pop the stack and calculate the max before current element. At the end, clear all elements in the stack and calculate the left over areas.

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    int max = 0;
    for (int i = 0; i < n; i++) {
        while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
            max = Math.max(max,
                           heights[stack.pop()] * (i - stack.peek() - 1));
        }
        stack.add(i);
    }
    while (stack.peek() != -1) {
        max = Math.max(max,
                       heights[stack.pop()] * (n - stack.peek() - 1));
    }
    return max;
}

901. Online Stock Span

Use a stack and only keep the elements larger than the new element, as well as aggregate the counts less or equals to the new element.

class StockSpanner {
    Stack<int[]> stack;
    public StockSpanner() {
        stack = new Stack<>();
    }
    
    public int next(int price) {
        int count = 1;
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            count += stack.pop()[1];
        }
        stack.add(new int[]{price, count});
        return count;
    }
}

227. Basic Calculator II

Use a stack to store previous numbers. Use an operator character to store the last operator. When meet new operator or reach the last digit, perform the operation, aggregate results at last.

Java

public int calculate(String s) {
    Stack<Integer> stack = new Stack<>();
    int num = 0;
    char operator = '+';
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c >= '0' && c <= '9') {
            num = num * 10 + (c - '0');
        } 
        if ("+-/*".indexOf(c) != -1 || i == s.length() - 1) {
            if (operator == '+') {
                stack.add(num);
            } else if (operator == '-') {
                stack.add(num * -1);
            } else if (operator == '*') {
                stack.add(stack.pop() * num);
            } else if (operator == '/') {
                stack.add(stack.pop() / num);
            }
            num = 0;
            operator = c;
        }
    }
    int res = 0;
    while (!stack.isEmpty()) res += stack.pop();
    return res;
}

Python

224. Basic Calculator

    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        int num = 0, res = 0, sign = 1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                num = num * 10 + (c - '0');
            } else if (c == '+') {
                res += sign * num;
                sign = 1;
                num = 0;
            } else if (c == '-') {
                res += sign * num;
                sign = -1;
                num = 0;
            } else if (c == '(') {
                stack.add(res);
                stack.add(sign);
                res = 0;
                sign = 1;
            } else if (c == ')' && stack.size() > 1) {
                res += sign * num;
                num = 0;
                res *= stack.pop();
                res += stack.pop();
            }
        }
        res += sign * num;
        return res;
    }

772. Basic Calculator III

    public int calculate(String s) {
        Queue<Character> q = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c != ' ') {
                q.offer(c);
            }
        }

        q.offer(' '); // placeholder
        return helper(q);
    }

    private int helper(Queue<Character> q) {
        int val = 0;
        int prev = 0, res = 0;
        char prevOp = '+';

        while (!q.isEmpty()) {
            char c = q.poll();

            if (c >= '0' && c <= '9') {
                val = val * 10 + c - '0';
            } else if (c == '(') {
                val = helper(q);
            } else {
                switch (prevOp) { // Note: prevOp, not current c
                    case '+':
                        res += prev;
                        prev = val;
                        break;
                    case '-':
                        res += prev;
                        prev = -val;
                        break;
                    case '*':
                        prev *= val;
                        break;
                    case '/':
                        prev /= val;
                        break;
                }

                if (c == ')') break;

                val = 0;
                prevOp = c;
            }
        }

        return res + prev;
    }

726. Number of Atoms

Store map: element : count to stack. When meeting brackets, deal with the maps in stack. Otherwise, store elements and their count to map.

public String countOfAtoms(String s) {
    Stack<Map<String, Integer>> stack = new Stack<>();
    Map<String, Integer> map = new HashMap<>();
    int i = 0, n = s.length();
    while (i < n) {
        char c = s.charAt(i);
        i++;
        if (c == '(') {
            stack.push(map);
            map = new HashMap<>();
        } else if (c == ')') {
            int val = 0;
            while (i < n && Character.isDigit(s.charAt(i))) {
                val = val * 10 + (s.charAt(i++) - '0');
            }
            if (val == 0) val = 1;
            if (!stack.isEmpty()) {
                Map<String, Integer> temp = map;
                map = stack.pop();
                for (String key : temp.keySet()) {
                    map.put(key, map.getOrDefault(key, 0) + temp.get(key) * val);
                }
            }
        } else {
            int start = i - 1;
            while (i < n && Character.isLowerCase(s.charAt(i))) {
                i++;
            }
            String curt = s.substring(start, i);
            int val = 0;
            while (i < n && Character.isDigit(s.charAt(i))) {
                val = val * 10 + (s.charAt(i++) - '0');
            }
            if (val == 0) val = 1;
            map.put(curt, map.getOrDefault(curt, 0) + val);
        }
    }
    StringBuilder sb = new StringBuilder();
    List<String> list= new ArrayList<>(map.keySet());
    Collections.sort(list);
    for(String key: list){
        sb.append(key);
        if(map.get(key)>1) sb.append(map.get(key));
    }
    return sb.toString();
}

Constrained Subsequence Sum

1130. Minimum Cost Tree From Leaf Values

Find the smallest consecutive two values to merge to get min cost. When encounter a number is larger than peek, calculate the product of peek (smaller number) and n or the one before peek. Later cumulate all products.

public int mctFromLeafValues(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    int res = 0;
    Stack<Integer> stack = new Stack<>();
    for (int n : arr) {
        while (!stack.isEmpty() && n >= stack.peek()) {
            int mid = stack.pop();
            if (stack.isEmpty()) {
                res += mid * n;
            } else {
                res += mid * Math.min(stack.peek(), n);
            }
        }
        stack.add(n);
    }
    while (stack.size() >= 2) {
        res += stack.pop() * stack.peek();
    }
    return res;
}

1190. Reverse Substrings Between Each Pair of Parentheses

public String reverseParentheses(String s) {
    if(s.length() == 0) return "";
    
    int begin = 0, end = 0;
    for(int i = 0; i < s.length(); i++){
        if(s.charAt(i) == '(') begin = i;
        if(s.charAt(i) == ')') {
            end = i;
            StringBuilder sb = new StringBuilder(s.substring(begin+1, end));
            return reverseParentheses(s.substring(0, begin) + sb.reverse().toString() + s.substring(end+1));
        }
    }
    return s;
}

1047. Remove All Adjacent Duplicates In String

public String removeDuplicates(String S) {
    Stack<Character> stack = new Stack<>();
    for (char c : S.toCharArray()) {
        if (!stack.isEmpty() 
            && stack.peek() == c) {
            stack.pop();
        } else {
            stack.add(c);
        }
    }
    StringBuilder sb = new StringBuilder();
    for (char c : stack) {
        sb.append(c);
    }
    return sb.toString();
}

1209. Remove All Adjacent Duplicates in String II

Save the consecutive character lengths in a stack. When see the same char, and char length equals to k, remove the substring.

public String removeDuplicates(String s, int k) {
    Stack<Integer> stack = new Stack<>();
    StringBuilder sb = new StringBuilder(s);
    for (int i = 0; i < sb.length(); i++) {
        if (i == 0 || sb.charAt(i) != sb.charAt(i - 1)) { // new char
            stack.push(1);
        } else { // same char
            int incre = stack.pop() + 1;
            if (incre == k) {
                sb.delete(i - k + 1, i + 1);
                i -= k;
            } else {
                stack.add(incre);
            }
        }
    }
    return sb.toString();
}

Sum of Subarray Minimums

Online Stock Span

Score of Parentheses

Next Greater Element II

Next Greater Element I

Largest Rectangle in Histogram

Trapping Rain Water

Max Value of Equation

946. Validate Stack Sequences

Simulate the stack push and pop operations, validate the sequence in popped array and pop in the stack.

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed == null || popped == null || pushed.length != popped.length) {
            return false;
        }
        int j = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            while (!stack.isEmpty() && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
        return j == popped.length;
    }

2334. Subarray With Elements Greater Than Varying Threshold

Use monotonic stack to find the last smaller element to the left and right, hence get a range of all elements greater than current:

public int validSubarraySize(int[] nums, int threshold) {
    int n = nums.length;
    Stack<Integer> stack = new Stack<>();
    int[] nextS = new int[n];
    int[] prevS = new int[n];
    Arrays.fill(nextS, n);
    Arrays.fill(prevS, -1);

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
            nextS[stack.peek()] = i;
            stack.pop();
        }
        stack.add(i);
    }

    stack.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
            prevS[stack.peek()] = i;
            stack.pop();
        }
        stack.add(i);
    }

    for (int i = 0; i < n; i++) {
        int left = prevS[i];
        int right = nextS[i] == -1 ? n : nextS[i];
        int len = right - left - 1;
        if ((long)nums[i] * len > threshold) return len;
    }
    return -1;
}