class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        result[0] = 1;
        for (int i = 1; i < result.length; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }
        int rightProduct = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            rightProduct = rightProduct * nums[i + 1];
            result[i] = rightProduct * result[i];
        }
        return result;
    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> routeOne = new ArrayList<>();
        List<TreeNode> routeTwo = new ArrayList<>();
        helper(routeOne, root, p);
        helper(routeTwo, root, q);
        int ptrOne = 0, ptrTwo = 0;
        TreeNode result;
        while (ptrOne < routeOne.size() && ptrTwo < routeTwo.size() && routeOne.get(ptrOne) == routeTwo.get(ptrTwo)) {
            ptrOne += 1;
            ptrTwo += 1;
        }
        if (ptrOne == routeOne.size()) {
            result = routeOne.get(ptrOne - 1);
        } else {
            result = routeTwo.get(ptrTwo - 1);
        }
        return result;
    }

    public boolean helper(List<TreeNode> route, TreeNode node, TreeNode target) {
        if (node == target) {
            route.add(node);
            return true;
        }

        route.add(node);
        boolean found = false;

        if (node.left != null)
            found = helper(route, node.left, target);

        if (found)
            return true;

        if (node.right != null)
            found = helper(route, node.right, target);

        if (found)
            return true;

        route.remove(route.size() - 1);
        return false;
    }
}

class MyQueue {
    private Stack<Integer> input = new Stack<>();
    private Stack<Integer> output = new Stack<>();

    public MyQueue() {

    }

    public void push(int x) {
        input.push(x);
    }

    public int pop() {
        loadOutput();
        return output.pop();
    }

    public int peek() {
        loadOutput();
        return output.peek();
    }

    public boolean empty() {
        return input.isEmpty() && output.isEmpty();
    }

    private void loadOutput() {
        if (output.isEmpty()) {
            while (!input.isEmpty()) {
                output.push(input.pop());
            }
        }
    }
}

class Solution {
    static private class Info {
        int result;
        int num;

        Info(int num, int result) {
            this.num = num;
            this.result = result;
        }
    }

    public int kthSmallest(TreeNode root, int k) {
        Info info = new Info(0, -1);
        helper(root, k, info);
        return info.result;
    }

    private void helper(TreeNode node, int k, Info info) {
        if (node.left != null) {
            helper(node.left, k, info);
        }
        if (info.num == k)
            return;
        info.num += 1;
        if (info.num == k) {
            info.result = node.val;
            return;
        }
        if (node.right != null)
            helper(node.right, k, info);

    }
}

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums.length == 1) {
            result.add(nums[0]);
            return result;
        }
        int potentialOne = Integer.MAX_VALUE;
        int counterOne = 0;
        int potentialTwo = Integer.MAX_VALUE;
        int counterTwo = 0;
        for (int i = 0; i < nums.length; i++) {
            if (counterOne >= 0 && potentialOne == nums[i]) {
                counterOne += 1;
                continue;
            } else if (counterTwo >= 0 && potentialTwo == nums[i]) {
                counterTwo += 1;
                continue;
            }
            if (counterOne == 0) {
                potentialOne = nums[i];
                counterOne += 1;
            } else if (counterTwo == 0) {
                potentialTwo = nums[i];
                counterTwo += 1;
            } else {
                counterOne -= 1;
                counterTwo -= 1;
            }
        }
        counterOne = 0;
        counterTwo = 0;
        for (int num : nums) {
            if (num == potentialOne)
                counterOne += 1;
            if (num == potentialTwo)
                counterTwo += 1;
        }

        if (counterOne > nums.length / 3) {
            result.add(potentialOne);
        }
        if (counterTwo > nums.length / 3) {
            result.add(potentialTwo);
        }
        return result;
    }
}

class Trie {
    private TrieNode root;
    private char endSymbol;

    // Every character is a node in the trie.
    // A node has a field denoting which character it represents
    // and knows all the children nodes it has in O(1) time.
    static class TrieNode {
        char currentChar = ' ';
        Map<Character, TrieNode> children = new HashMap<>();
    }

    public Trie() {
        root = new TrieNode();
        endSymbol = '*';
    }

    public void insert(String word) {
        insertSubStringFrom(0, word);
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            if (!node.children.containsKey(word.charAt(i)))
                return false;
            node = node.children.get(word.charAt(i));
        }
        return node.children.containsKey(endSymbol);
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (int i = 0; i < prefix.length(); i++) {
            if (!node.children.containsKey(prefix.charAt(i)))
                return false;
            node = node.children.get(prefix.charAt(i));
        }
        return true;
    }

    public void insertSubStringFrom(int pos, String str) {
        TrieNode node = root;
        for (int i = pos; i < str.length(); i++) {
            if (!node.children.containsKey(str.charAt(i))) {
                node.children.put(str.charAt(i), new TrieNode());
            }
            node = node.children.get(str.charAt(i));
        }
        node.children.put(endSymbol, null);
    }
}

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int[] prerequisite : prerequisites) {
            if (!map.containsKey(prerequisite[1])) {
                map.put(prerequisite[1], new ArrayList<>(Arrays.asList(0, prerequisite[0])));
            } else {
                map.get(prerequisite[1]).add(prerequisite[0]);
            }
            if (!map.containsKey(prerequisite[0])) {
                map.put(prerequisite[0], new ArrayList<>(Arrays.asList(1)));
            } else {
                List<Integer> info = map.get(prerequisite[0]);
                info.set(0, info.get(0) + 1);
            }
        }
        Queue<Integer> nodependencyCourses = new LinkedList<>();
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            List<Integer> info = entry.getValue();
            if (info.get(0) == 0)
                nodependencyCourses.offer(entry.getKey());
        }

        while (!nodependencyCourses.isEmpty()) {
            int courseNum = nodependencyCourses.poll();
            List<Integer> list = map.get(courseNum);
            for (int i = 1; i < list.size(); i++) {
                List<Integer> targetList = map.get(list.get(i));
                targetList.set(0, targetList.get(0) - 1);
                if (targetList.get(0) == 0) {
                    nodependencyCourses.offer(list.get(i));
                }
            }
            map.remove(courseNum);
        }
        return map.isEmpty();
    }
}

class Solution {
    public int numIslands(char[][] grid) {
        Queue<int[]> q = new LinkedList<>();
        int ans = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    grid[i][j] = '0';
                    q.offer(new int[] { i, j });
                    clearIsland(i, j, grid, q);
                    ans += 1;
                }
            }
        }
        return ans;
    }

    private void clearIsland(int row, int col, char[][] grid, Queue<int[]> q) {
        int[][] directions = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
        while (!q.isEmpty()) {
            int[] pos = q.poll();
            for (int[] direction : directions) {
                int neighborRow = pos[0] + direction[0];
                int neighborCol = pos[1] + direction[1];
                if (!isOutOfBound(grid, neighborRow, neighborCol)
                        && grid[neighborRow][neighborCol] == '1') {
                    grid[neighborRow][neighborCol] = '0';
                    q.offer(new int[] { neighborRow, neighborCol });
                }
            }
        }
    }

    private boolean isOutOfBound(char[][] grid, int row, int col) {
        return row < 0 || row >= grid.length || col < 0 || col >= grid[0].length;
    }
}

class Solution {
    public int majorityElement(int[] nums) {
        int major = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (count == 0) {
                major = nums[i];
                count += 1;
            } else if (nums[i] == major) {
                count += 1;
            } else {
                count -= 1;
            }
        }
        return major;
    }
}

class MinStack {

    private Stack<Integer> stack = new Stack<>();
    private Stack<int[]> minStack = new Stack<>();

    public MinStack() {

    }

    public void push(int val) {
        stack.push(val);

        if (minStack.isEmpty() || val < minStack.peek()[0]) {
            minStack.add(new int[] { val, 1 });
        } else if (val == minStack.peek()[0]) {
            minStack.peek()[1] += 1;
        }
    }

    public void pop() {
        if (!stack.isEmpty()) {
            int num = stack.pop();
            if (num == minStack.peek()[0]) {
                minStack.peek()[1] -= 1;
            }
            if (minStack.peek()[1] == 0) {
                minStack.pop();
            }
        }
    }

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

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