class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if (token.equals("+")) {
                int numTwo = stack.pop(), numOne = stack.pop();
                stack.push(numOne + numTwo);
            } else if (token.equals("-")) {
                int numTwo = stack.pop(), numOne = stack.pop();
                stack.push(numOne - numTwo);
            } else if (token.equals("*")) {
                int numTwo = stack.pop(), numOne = stack.pop();
                stack.push(numOne * numTwo);
            } else if (token.equals("/")) {
                int numTwo = stack.pop(), numOne = stack.pop();
                stack.push(numOne / numTwo);
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
}

class Solution {
    public int singleNumber(int[] nums) {
        int seenOnce = 0, seenTwice = 0;
        for (int num : nums) {
            seenOnce = ~seenTwice & (num ^ seenOnce);
            seenTwice = ~seenOnce & (num ^ seenTwice);
        }
        return seenOnce;
    }
}

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null)
            return null;
        Queue<Node> unfinished = new LinkedList<>();
        Map<Node, Node> cloned = new HashMap<>();
        Node newNode = new Node(node.val);
        unfinished.offer(node);
        cloned.put(node, newNode);
        while (!unfinished.isEmpty()) {
            Node oldNode = unfinished.poll();
            ArrayList<Node> newList = new ArrayList<>();
            cloned.get(oldNode).neighbors = newList;
            for (Node neighbor : oldNode.neighbors) {
                if (cloned.containsKey(neighbor)) {
                    newList.add(cloned.get(neighbor));
                } else {
                    Node newNeighbor = new Node(neighbor.val);
                    newList.add(newNeighbor);
                    cloned.put(neighbor, newNeighbor);
                    unfinished.offer(neighbor);
                }
            }
        }
        return newNode;
    }
}

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null)
            return new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        helper(ans, new ArrayList<>(), root, 0, targetSum);
        return ans;
    }

    private void helper(List<List<Integer>> ans, List<Integer> currentNodes, TreeNode node, int currSum, int target) {
        if (node == null)
            return;
        currSum += node.val;
        currentNodes.add(node.val);
        if (node.left == null && node.right == null && currSum == target) {
            ans.add(new ArrayList<>(currentNodes));
        }
        helper(ans, currentNodes, node.left, currSum, target);
        helper(ans, currentNodes, node.right, currSum, target);
        currentNodes.remove(currentNodes.size() - 1);
    }
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;
        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int length = q.size();
            ArrayList<Integer> currentLevel = new ArrayList<>();
            for (int i = 0; i < length; i++) {
                TreeNode node = q.poll();
                currentLevel.add(node.val);
                if (node.left != null)
                    q.offer(node.left);
                if (node.right != null)
                    q.offer(node.right);
            }
            res.add(currentLevel);
        }
        return res;
    }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(null, null, root);
    }

    public boolean helper(Integer low, Integer up, TreeNode node) {
        if (node == null)
            return true;
        if ((low != null && node.val <= low) || (up != null && node.val >= up))
            return false;
        return helper(low, node.val, node.left) && helper(node.val, up, node.right);
    }
}

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int ptr = nums1.length - 1;
        int ptrOne = m - 1, ptrTwo = n - 1;
        while (ptrOne >= 0 && ptrTwo >= 0) {
            nums1[ptr] = Math.max(nums1[ptrOne], nums2[ptrTwo]);
            if (nums1[ptrOne] >= nums2[ptrTwo])
                ptrOne -= 1;
            else
                ptrTwo -= 1;
            ptr -= 1;
        }
        if (ptrOne < 0) {
            while (ptr >= 0)
                nums1[ptr--] = nums2[ptrTwo--];
        }
    }
}

class Solution {
    public String addBinary(String a, String b) {
        char[] result = new char[Math.max(a.length(), b.length()) + 1];
        result[result.length - 1] = 'a';
        int ptrOne = a.length() - 1;
        int ptrTwo = b.length() - 1;
        int ptrThree = 0;
        int carry = 0;
        while (ptrOne >= 0 || ptrTwo >= 0) {
            char first = ptrOne < 0 ? '0' : a.charAt(ptrOne);
            char second = ptrTwo < 0 ? '0' : b.charAt(ptrTwo);

            if (first == '1' && second == '1') {
                if (carry == 0) {
                    result[ptrThree] = '0';
                } else {
                    result[ptrThree] = '1';
                }
                carry = 1;
            } else if (first == '0' && second == '0') {
                if (carry == 0) {
                    result[ptrThree] = '0';
                } else {
                    result[ptrThree] = '1';
                }
                carry = 0;
            } else {
                if (carry == 0) {
                    result[ptrThree] = '1';
                    carry = 0;
                } else {
                    result[ptrThree] = '0';
                    carry = 1;
                }
            }
            ptrOne -= 1;
            ptrTwo -= 1;
            ptrThree += 1;
        }
        StringBuilder s = new StringBuilder();
        if (carry == 1) {
            result[result.length - 1] = '1';
        }
        int startPoint = result.length - 1;
        if (result[result.length - 1] == 'a') {
            startPoint -= 1;
        }
        for (int i = startPoint; i >= 0; i--) {
            s.append(result[i]);
        }

        return s.toString();

    }
}

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int start = newInterval[0];
        int end = newInterval[1];
        int idx = 0;
        while (idx < intervals.length && intervals[idx][1] < start) {
            result.add(intervals[idx++]);
        }

        while (idx < intervals.length && intervals[idx][0] <= end) {
            start = Math.min(start, intervals[idx][0]);
            end = Math.max(end, intervals[idx][1]);
            idx += 1;
        }
        result.add(new int[] { start, end });

        while (idx < intervals.length && intervals[idx][0] > end) {
            result.add(intervals[idx++]);
        }
        return listToArray(result);
    }

    private int[][] listToArray(List<int[]> list) {
        int[][] array = new int[list.size()][2];
        for (int i = 0; i < array.length; i++) {
            array[i] = list.get(i);
        }
        return array;
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> mergedIntervals = new ArrayList<>();
        mergedIntervals.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int currentIntervalEnd = intervals[i][1];
            int currentIntervalStart = intervals[i][0];
            int[] lastMergedInterval = mergedIntervals.get(mergedIntervals.size() - 1);
            if (currentIntervalStart <= lastMergedInterval[1]) {
                lastMergedInterval[1] = Math.max(lastMergedInterval[1], currentIntervalEnd);
            } else {
                mergedIntervals.add(intervals[i]);
            }
        }
        return mergedIntervals.toArray(new int[mergedIntervals.size()][]);
    }
}