class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            ans ^= nums[i];
        }
        return ans;
    }
}

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int pos = 0;
        while (pos < gas.length) {
            int currTank = 0;
            int newPos = 0;
            for (int i = 0; i < gas.length; i++) {
                int currentPos = pos + i;
                if (currentPos >= gas.length)
                    currentPos %= gas.length;
                if (currTank < 0) {
                    newPos = currentPos;
                    break;
                }
                currTank = currTank + gas[currentPos] - cost[currentPos];
            }
            if (currTank >= 0)
                return pos;
            if (newPos <= pos)
                break;
            pos = newPos;
            currTank = 0;
        }
        return -1;
    }
}

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        Set<Integer> set = new HashSet<>();
        for (int i : nums)
            set.add(i);
        int ans = 0;
        for (int num : nums) {
            int left = num - 1;
            int right = num + 1;
            while (set.remove(left))
                left--;
            while (set.remove(right))
                right++;
            ans = Math.max(ans, right - left - 1);
            if (set.isEmpty())
                return ans;// save time if there are items in nums, but no item in hashset.
        }
        return ans;
    }
}

class Solution {
    static class Node {
        int low, up;
        TreeNode node;

        Node(int low, int up, TreeNode node) {
            this.low = low;
            this.up = up;
            this.node = node;
        }
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = new TreeNode();
        Stack<Node> stack = new Stack<>();
        stack.push(new Node(0, nums.length - 1, root));
        while (!stack.isEmpty()) {
            Node currNode = stack.pop();
            int middle = currNode.low + (currNode.up - currNode.low) / 2;
            currNode.node.val = nums[middle];
            if (currNode.low <= middle - 1) {
                currNode.node.left = new TreeNode();
                stack.push(new Node(currNode.low, middle - 1, currNode.node.left));
            }

            if (currNode.up >= middle + 1) {
                currNode.node.right = new TreeNode();
                stack.push(new Node(middle + 1, currNode.up, currNode.node.right));
            }
        }
        return root;
    }
}

class Solution {
    private int pos;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        pos = postorder.length - 1;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return helper(map, 0, inorder.length - 1, postorder);
    }

    private TreeNode helper(Map<Integer, Integer> map, int iStart, int iEnd, int[] postorder) {
        if (iStart > iEnd)
            return null;
        TreeNode newNode = new TreeNode(postorder[pos]);
        int rootIdx = map.get(postorder[pos]);
        pos -= 1;
        newNode.right = helper(map, rootIdx + 1, iEnd, postorder);
        newNode.left = helper(map, iStart, rootIdx - 1, postorder);
        return newNode;
    }
}

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return helper(root.left, root.right);
    }

    private boolean helper(TreeNode p, TreeNode q) {
        if (p == null || q == null)
            return p == q;
        return p.val == q.val && helper(p.left, q.right) && helper(p.right, q.left);
    }
}

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null || q == null)
            return p == q;
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> currentSet = new ArrayList<>();
        helper(currentSet, ans, nums, 0);
        return ans;
    }

    private void helper(List<Integer> currentSet, List<List<Integer>> ans, int[] nums, int pos) {
        if (pos == nums.length) {
            ans.add(new ArrayList<>(currentSet));
            return;
        }
        currentSet.add(nums[pos]);
        helper(currentSet, ans, nums, pos + 1);
        currentSet.remove(currentSet.size() - 1);

        helper(currentSet, ans, nums, pos + 1);
    }

}

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length())
            return "";
        Map<Character, Integer> charCount = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            charCount.put(t.charAt(i), charCount.getOrDefault(t.charAt(i), 0) + 1);
        }
        int left = 0, right = 0, count = 0, minLeft = 0, minRight = 0, min = Integer.MAX_VALUE;

        while (right < s.length()) {
            // Move right pointer.
            while (right < s.length()) {
                if (charCount.containsKey(s.charAt(right))) {
                    charCount.put(s.charAt(right), charCount.get(s.charAt(right)) - 1);
                    if (charCount.get(s.charAt(right)) >= 0) {
                        count += 1;
                    }
                }
                if (count == t.length())
                    break;
                right += 1;
            }

            // Test if out of bound.
            if (right == s.length())
                break;

            // Move left pointer until not all chars in t are included in the window.
            // left <= right可要可不要.
            while (count == t.length() && left <= right) {
                if (charCount.containsKey(s.charAt(left))) {
                    charCount.put(s.charAt(left), charCount.get(s.charAt(left)) + 1);
                    if (charCount.get(s.charAt(left)) > 0) {
                        count -= 1;
                    }
                }
                left += 1;
            }

            // Check the length.
            if (right - (left - 1) + 1 < min) {
                minLeft = left - 1;
                minRight = right + 1;
                min = right - (left - 1) + 1;
            }

            right += 1;
        }
        return min != Integer.MAX_VALUE ? s.substring(minLeft, minRight) : "";
    }
}