class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> levels = new LinkedList<>();
        dfs(root, 0, levels);
        return levels;
    }

    private void dfs(TreeNode node, int level, LinkedList<List<Integer>> levels) {
        if (node == null) {
            return;
        }
        if (levels.size() == level) {
            levels.addFirst(new ArrayList<>());
        }
        levels.get(levels.size() - 1 - level).add(node.val);
        dfs(node.left, level + 1, levels);
        dfs(node.right, level + 1, levels);
    }
}

class Solution {
    public int maxLength(int[] ribbons, int k) {
        int left = 1, right = (int) 1e5, ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (isCuttable(ribbons, mid, k)) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }

    private boolean isCuttable(int[] ribbons, int length, int k) {
        int count = 0;
        for (int ribbon : ribbons) {
            count += ribbon / length;
        }
        return count >= k;
    }
}

class Solution {
    public int[] sumEvenAfterQueries(int[] nums, int[][] queries) {
        int sum = 0;
        for (int num : nums) {
            if (num % 2 == 0)
                sum += num;
        }
        int[] ans = new int[queries.length];
        int index = 0;
        for (int[] query : queries) {
            int currNum = nums[query[1]];
            if (currNum % 2 == 0) {
                sum -= currNum;
            }
            currNum += query[0];
            if (currNum % 2 == 0) {
                sum += currNum;
            }
            nums[query[1]] = currNum;
            ans[index] = sum;
            index += 1;
        }
        return ans;
    }
}

class Solution {
    public int maximumSwap(int num) {
        char[] numArray = String.valueOf(num).toCharArray();
        int[] greatestRight = new int[numArray.length];
        int max = -1, maxIdx = -1;
        for (int i = numArray.length - 1; i >= 0; i--) {
            if (numArray[i] - '0' > max) {
                max = numArray[i] - '0';
                maxIdx = i;
                greatestRight[i] = i;
            } else {
                greatestRight[i] = maxIdx;
            }
        }
        for (int i = 0; i < numArray.length; i++) {
            if (numArray[i] - '0' < numArray[greatestRight[i]] - '0') {
                swap(numArray, i, greatestRight[i]);
                return Integer.parseInt(new String(numArray));
            }
        }
        return num;
    }

    private void swap(char[] numArray, int i, int j) {
        char temp = numArray[i];
        numArray[i] = numArray[j];
        numArray[j] = temp;
    }
}

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        Map<Integer, Integer> map = new TreeMap<>();
        for (int[] trip : trips) {
            map.put(trip[1], map.getOrDefault(trip[1], 0) + trip[0]);
            map.put(trip[2], map.getOrDefault(trip[2], 0) - trip[0]);
        }
        int count = 0;
        for (int v : map.values()) {
            count += v;
            if (count > capacity)
                return false;
        }
        return true;
    }
}

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int[] prefixSum = new int[nums.length];
        prefixSum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i];
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < prefixSum.length; i++) {
            if (prefixSum[i] < target)
                continue;
            int offset = prefixSum[i] - target;
            int leftBound = binarySearch(prefixSum, 0, i - 1, offset);
            ans = Math.min(ans, i - leftBound);
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

    private int binarySearch(int[] prefixSum, int left, int right, int target) {
        int ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (prefixSum[mid] <= target) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

class Solution {
    public int minimumKeypresses(String s) {
        int[] charCount = new int[26];
        char[] sArray = s.toCharArray();
        for (char letter : sArray) {
            charCount[letter - 'a'] += 1;
        }
        PriorityQueue<Integer> charCountPQ = new PriorityQueue<>((a, b) -> b - a);
        for (int i = 0; i < 26; i++) {
            if (charCount[i] != 0) {
                charCountPQ.offer(charCount[i]);
            }
        }
        int count = 0, press = 0, ans = 0;
        while (!charCountPQ.isEmpty()) {
            if (count % 9 == 0) {
                press += 1;
            }
            int currFreq = charCountPQ.poll();
            ans += press * currFreq;
            count += 1;
        }
        return ans;
    }
}

class Solution {
    public int[] platesBetweenCandles(String s, int[][] queries) {
        char[] sArray = s.toCharArray();
        int[] prevCandlePos = new int[s.length()];
        int[] nextCandlePos = new int[s.length()];
        int[] candleCount = new int[sArray.length];
        int lastLeftCandle = -1, lastRightCandle = sArray.length, count = 0;
        for (int left = 0, right = sArray.length - 1; left < sArray.length; left++, right--) {
            if (sArray[left] == '*') {
                prevCandlePos[left] = lastLeftCandle;
            } else {
                lastLeftCandle = left;
                prevCandlePos[left] = left;
                count += 1;
                candleCount[left] = count;
            }
            if (sArray[right] == '*') {
                nextCandlePos[right] = lastRightCandle;
            } else {
                lastRightCandle = right;
                nextCandlePos[right] = right;
            }
        }
        int[] ans = new int[queries.length];
        for (int i = 0; i < ans.length; i++) {
            int leftBound = queries[i][0];
            int rightBound = queries[i][1];
            int firstCandle = nextCandlePos[leftBound];
            int lastCandle = prevCandlePos[rightBound];
            if (firstCandle == -1 || lastCandle == -1) {
                ans[i] = 0;
            } else {
                int eleNum = lastCandle - firstCandle - 1;
                if (eleNum > 0) {
                    ans[i] = eleNum - (candleCount[lastCandle] - candleCount[firstCandle] - 1);
                } else {
                    ans[i] = 0;
                }
            }
        }
        return ans;
    }
}

class Solution {
    public int minSwaps(String s) {
        int zeroes = 0, ones = 0;
        char[] sArray = s.toCharArray();
        for (int i = 0; i < sArray.length; i++) {
            if (sArray[i] == '0') {
                zeroes += 1;
            } else {
                ones += 1;
            }
        }
        if (Math.abs(zeroes - ones) > 1)
            return -1;
        if (zeroes > ones)
            return helper(sArray, '0');
        else if (zeroes < ones)
            return helper(sArray, '1');
        else
            return Math.min(helper(sArray, '0'), helper(sArray, '1'));
    }

    private int helper(char[] sArray, char start) {
        int swaps = 0;
        for (int i = 0; i < sArray.length; i++) {
            if (sArray[i] == start && i % 2 != 0) {
                swaps += 1;
            }
        }
        return swaps;
    }
}

/**
 * This is the interface for the expression tree Node.
 * You should not remove it, and you can define some classes to implement it.
 */

abstract class Node {
    public abstract int evaluate();

    // define your fields here
    public int num;
    public String operand;
    public Node left;
    public Node right;
};

/**
 * This is the TreeBuilder class.
 * You can treat it as the driver code that takes the postinfix input
 * and returns the expression tree represnting it as a Node.
 */
class TreeNode extends Node {

    public int evaluate() {
        if (this.operand == null) {
            return this.num;
        }
        int leftTreeVal = this.left.evaluate();
        int rightTreeVal = this.right.evaluate();
        int ans = compute(leftTreeVal, rightTreeVal, this.operand);
        return ans;
    }

    public TreeNode(int num) {
        this.num = num;
    }

    public TreeNode(String operand) {
        this.operand = operand;
    }

    public int compute(int i, int j, String operand) {
        int ans = 0;
        switch (operand) {
            case "+":
                ans = i + j;
                break;
            case "-":
                ans = i - j;
                break;
            case "*":
                ans = i * j;
                break;
            case "/":
                ans = i / j;
                break;
        }
        return ans;
    }
}

class TreeBuilder {
    Node buildTree(String[] postfix) {
        Deque<Node> stack = new ArrayDeque<>();
        for (String s : postfix) {
            if (!isOperand(s)) {
                stack.push(new TreeNode(Integer.parseInt(s)));
            } else {
                Node rightNode = stack.pop();
                Node leftNode = stack.pop();
                Node currNode = new TreeNode(s);
                currNode.left = leftNode;
                currNode.right = rightNode;
                stack.push(currNode);
            }
        }
        return stack.pop();
    }

    public boolean isOperand(String s) {
        return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
    }
};

/**
 * Your TreeBuilder object will be instantiated and called as such:
 * TreeBuilder obj = new TreeBuilder();
 * Node expTree = obj.buildTree(postfix);
 * int ans = expTree.evaluate();
 */