class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<List<Double>> levelSum = new ArrayList<>();
        helper(root, 0, levelSum);
        List<Double> ans = new ArrayList<>();
        for (int i = 0; i < levelSum.size(); i++) {
            ans.add(levelSum.get(i).get(0) / levelSum.get(i).get(1));
        }
        return ans;
    }

    private void helper(TreeNode node, int level, List<List<Double>> levelSum) {
        if (node == null) {
            return;
        }
        if (level == levelSum.size()) {
            levelSum.add(new ArrayList<>(Arrays.asList((double) node.val, (double) 1)));
        } else {
            List<Double> levelList = levelSum.get(level);
            levelList.set(0, levelList.get(0) + node.val);
            levelList.set(1, levelList.get(1) + 1);
        }
        helper(node.left, level + 1, levelSum);
        helper(node.right, level + 1, levelSum);
    }
}

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int leftBound = nums.length;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            boolean isPopped = false;
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                isPopped = true;
                stack.pop();
            }
            if (isPopped) {
                int currLeftBound = stack.isEmpty() ? 0 : stack.peek() + 1;
                leftBound = Math.min(leftBound, currLeftBound);
            }
            stack.push(i);
        }
        if (leftBound == nums.length) {
            return 0;
        }

        int rightBound = -1;
        stack = new Stack<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            boolean isPopped = false;
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                isPopped = true;
                stack.pop();
            }
            if (isPopped) {
                int currRightBound = stack.isEmpty() ? nums.length - 1 : stack.peek() - 1;
                rightBound = Math.max(rightBound, currRightBound);
            }
            stack.push(i);
        }
        return rightBound - leftBound + 1;
    }
}

class Solution {
    // Next permutation?
    public int nextGreaterElement(int n) {
        String numString = String.valueOf(n);
        char[] numCharArray = numString.toCharArray();
        int pos = -1;
        for (int i = numCharArray.length - 1; i > 0; i--) {
            if (numCharArray[i] > numCharArray[i - 1]) {
                pos = i - 1;
                break;
            }
        }
        if (pos == -1) {
            return -1;
        }
        int newPos = -1;
        for (int i = numCharArray.length - 1; i >= 0; i--) {
            if (numCharArray[i] > numCharArray[pos]) {
                newPos = i;
                break;
            }
        }
        swap(numCharArray, pos, newPos);
        reverse(numCharArray, pos + 1, numCharArray.length - 1);
        int ans = 0;
        for (int i = 0; i < numCharArray.length; i++) {
            if (ans > Integer.MAX_VALUE / 10
                    || (ans == Integer.MAX_VALUE / 10 && numCharArray[i] - '0' > Integer.MAX_VALUE % 10)) {
                return -1;
            }
            ans = ans * 10 + numCharArray[i] - '0';
        }
        return ans;
    }

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

    private void reverse(char[] numCharArray, int left, int right) {
        while (left < right) {
            swap(numCharArray, left, right);
            left += 1;
            right -= 1;
        }
    }
}

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] ans = new int[nums.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                ans[stack.pop()] = nums[i];
            }
            stack.push(i);
        }
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                ans[stack.pop()] = nums[i];
            }
        }
        while (!stack.isEmpty()) {
            ans[stack.pop()] = -1;
        }
        return ans;
    }
}

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] nextGreaterArr = new int[nums2.length];
        Arrays.fill(nextGreaterArr, -1);
        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> numIdxMap = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) {
            while (!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {
                nextGreaterArr[stack.pop()] = nums2[i];
            }
            stack.push(i);
            numIdxMap.put(nums2[i], i);
        }
        int[] ans = new int[nums1.length];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = nextGreaterArr[numIdxMap.get(nums1[i])];
        }
        return ans;
    }
}

class Solution {
    int ans;

    public int findTargetSumWays(int[] nums, int target) {
        helper(nums, 0, 0, target);
        return ans;
    }

    private void helper(int[] nums, int pos, int currSum, int target) {
        if (pos == nums.length) {
            if (currSum == target) {
                ans += 1;
            }
            return;
        }
        helper(nums, pos + 1, currSum + nums[pos], target);
        helper(nums, pos + 1, currSum - nums[pos], target);
    }
}

class Solution {
    public String frequencySort(String s) {
        int[] charFreq = new int[128];
        int charMaxFreq = 0;
        for (int i = 0; i < s.length(); i++) {
            charFreq[s.charAt(i)] += 1;
            charMaxFreq = Math.max(charMaxFreq, charFreq[s.charAt(i)]);
        }
        List<List<Character>> buckets = new ArrayList<>();
        for (int i = 0; i <= charMaxFreq; i++) {
            buckets.add(new ArrayList<>());
        }
        for (int i = 0; i < charFreq.length; i++) {
            if (charFreq[i] == 0) {
                continue;
            }
            buckets.get(charFreq[i]).add((char) i);
        }
        StringBuilder ans = new StringBuilder();
        for (int i = buckets.size() - 1; i >= 0; i--) {
            for (Character c : buckets.get(i)) {
                for (int j = 0; j < i; j++) {
                    ans.append(c);
                }
            }
        }
        return ans.toString();
    }
}

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int currNum = Math.abs(nums[i]);
            int targetIdx = currNum - 1;
            nums[targetIdx] = -Math.abs(nums[targetIdx]);
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                ans.add(i + 1);
            }
        }
        return ans;
    }
}

class Solution {
    public int compress(char[] chars) {
        int pos = 0;
        int docPtr = 0;
        while (pos < chars.length) {
            char currChar = chars[pos];
            int length = 1;
            pos += 1;
            while (pos < chars.length && chars[pos] == chars[pos - 1]) {
                length += 1;
                pos += 1;
            }
            chars[docPtr++] = currChar;
            if (length != 1) {
                for (char digit : String.valueOf(length).toCharArray()) {
                    chars[docPtr++] = digit;
                }
            }
        }
        return docPtr;
    }
}