class Solution {
    public int minimumCardPickup(int[] cards) {
        Map<Integer, Integer> lastOccur = new HashMap<>();
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < cards.length; i++) {
            if (lastOccur.containsKey(cards[i])) {
                ans = Math.min(ans, i - lastOccur.get(cards[i]) + 1);
            }
            lastOccur.put(cards[i], i);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

class Solution {
    public int[] findBuildings(int[] heights) {
        boolean[] buildings = new boolean[heights.length];
        Arrays.fill(buildings, true);
        Deque<Integer> stack = new ArrayDeque<>();
        int count = buildings.length;
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[i] >= heights[stack.peek()]) {
                buildings[stack.pop()] = false;
                count -= 1;
            }
            stack.push(i);
        }
        int[] ans = new int[count];
        for (int i = 0, j = 0; i < buildings.length; i++) {
            if (buildings[i]) {
                ans[j] = i;
                j += 1;
            }
        }
        return ans;
    }
}

class Solution {
    private int modulo = 1000000007;

    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        List<int[]> engineers = new ArrayList<>();
        for (int i = 0; i < speed.length; i++) {
            engineers.add(new int[] { efficiency[i], speed[i] });
        }
        Collections.sort(engineers, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        long ans = 0;
        for (int i = 0; i < n; i++) {
            if (i > 0 && engineers.get(i)[0] == engineers.get(i - 1)[0])
                continue;
            PriorityQueue<int[]> candidates = new PriorityQueue<>((a, b) -> a[1] - b[1]);
            for (int j = i + 1; j < n; j++) {
                candidates.offer(engineers.get(j));
                if (candidates.size() == k) {
                    candidates.poll();
                }
            }
            long speedSum = engineers.get(i)[1];
            while (!candidates.isEmpty()) {
                speedSum += candidates.poll()[1];
            }
            long currPerfor = speedSum * engineers.get(i)[0];
            ans = Math.max(ans, currPerfor);
        }
        return (int) (ans % modulo);
    }
}

class Solution {
    private int[][] directions = new int[][] { { -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 }, { 1, 0 }, { 1, 1 },
            { 0, 1 }, { -1, 1 } };

    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] == 1) {
            return -1;
        }
        if (grid.length == 1) {
            return 1;
        }
        int n = grid.length;
        boolean[][] visited = new boolean[n][n];
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[] { 0, 0 });
        visited[0][0] = true;
        int steps = 1;
        while (!q.isEmpty()) {
            for (int i = q.size(); i > 0; i--) {
                int[] currPos = q.poll();
                for (int[] direction : directions) {
                    int newRow = currPos[0] + direction[0];
                    int newCol = currPos[1] + direction[1];
                    if (!isOutOfBound(n, newRow, newCol) && grid[newRow][newCol] == 0 && !visited[newRow][newCol]) {
                        if (newRow == n - 1 && newCol == n - 1) {
                            return steps + 1;
                        }
                        q.offer(new int[] { newRow, newCol });
                        visited[newRow][newCol] = true;
                    }
                }
            }
            steps += 1;
        }
        return -1;
    }

    private boolean isOutOfBound(int n, int row, int col) {
        return row < 0 || row >= n || col < 0 || col >= n;
    }
}

class Solution {
    Integer[] memo;

    public int mincostTickets(int[] days, int[] costs) {
        memo = new Integer[days.length];
        return backtrack(days, costs, 0);
    }

    private int backtrack(int[] days, int[] costs, int pos) {
        if (pos == days.length) {
            return 0;
        }
        if (memo[pos] != null) {
            return memo[pos];
        }
        int minCost = Integer.MAX_VALUE;
        // Buy 1 day pass
        minCost = Math.min(minCost, backtrack(days, costs, pos + 1) + costs[0]);

        // Buy 7 day pass
        minCost = Math.min(minCost, backtrack(days, costs, binarySearch(days, pos + 1, days[pos] + 7)) + costs[1]);

        // Buy 30 day pass
        minCost = Math.min(minCost, backtrack(days, costs, binarySearch(days, pos + 1, days[pos] + 30)) + costs[2]);

        return memo[pos] = minCost;
    }

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

class Solution {
    public List<Integer> diffWaysToCompute(String expression) {
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < expression.length(); i++) {
            if (expression.charAt(i) == '+' || expression.charAt(i) == '-' || expression.charAt(i) == '*') {
                List<Integer> leftExp = diffWaysToCompute(expression.substring(0, i));
                List<Integer> rightExp = diffWaysToCompute(expression.substring(i + 1));
                for (Integer leftEle : leftExp) {
                    for (Integer rightEle : rightExp) {
                        ans.add(compute(leftEle, rightEle, expression.charAt(i)));
                    }
                }
            }
        }
        if (ans.size() == 0) {
            ans.add(Integer.parseInt(expression));
        }
        return ans;
    }

    private int compute(int i, int j, char operand) {
        int ans = 0;
        switch (operand) {
            case '+':
                ans = i + j;
                break;
            case '-':
                ans = i - j;
                break;
            case '*':
                ans = i * j;
                break;
        }
        return ans;
    }
}

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        if (nums.length < 4) {
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums.length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            for (int j = i + 1; j < nums.length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1])
                    continue;
                int left = j + 1, right = nums.length - 1;
                long diff = (long) target - nums[i] - nums[j];
                while (left < right) {
                    int currSum = nums[left] + nums[right];
                    if (currSum < diff) {
                        left += 1;
                    } else if (currSum > diff) {
                        right -= 1;
                    } else {
                        ans.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1])
                            left += 1;
                        while (left < right && nums[right] == nums[right - 1])
                            right -= 1;
                        left += 1;
                        right -= 1;
                    }
                }
            }
        }
        return ans;
    }
}

class Solution {
    public TreeNode[] splitBST(TreeNode root, int target) {
        if (root == null) {
            return new TreeNode[] { null, null };
        }
        TreeNode[] ans;
        if (root.val < target) {
            ans = splitBST(root.right, target);
            root.right = ans[0];
            ans[0] = root;
        } else if (root.val > target) {
            ans = splitBST(root.left, target);
            root.left = ans[1];
            ans[1] = root;
        } else {
            TreeNode right = root.right;
            root.right = null;
            ans[0] = root;
            ans[1] = right;
        }
        return ans;
    }
}

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        TreeNode dummy = new TreeNode(0);
        dfs(root1, root2, dummy, true);
        return dummy.left;
    }

    private void dfs(TreeNode node1, TreeNode node2, TreeNode prev, boolean isLeft) {
        if (node1 == null && node2 == null) {
            return;
        }
        int currVal = node1 != null ? node1.val : 0;
        currVal += node2 != null ? node2.val : 0;
        TreeNode newNode = new TreeNode(currVal);
        if (isLeft) {
            prev.left = newNode;
        } else {
            prev.right = newNode;
        }
        if (node1 != null && node2 != null) {
            dfs(node1.left, node2.left, newNode, true);
            dfs(node1.right, node2.right, newNode, false);
        } else if (node1 != null) {
            dfs(node1.left, null, newNode, true);
            dfs(node1.right, null, newNode, false);
        } else {
            dfs(node2.left, null, newNode, true);
            dfs(node2.right, null, newNode, false);
        }
    }
}

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        Map<String, List<String>> map = new HashMap<>();
        for (String string : strings) {
            String hash = getHash(string);
            map.computeIfAbsent(hash, a -> new ArrayList<>()).add(string);
        }
        List<List<String>> ans = new ArrayList<>(map.values());
        return ans;
    }

    private String getHash(String s) {
        StringBuilder ans = new StringBuilder();
        char[] charArray = s.toCharArray();
        for (int i = 1; i < charArray.length; i++) {
            if (charArray[i] < charArray[i - 1]) {
                ans.append(charArray[i] - charArray[i - 1] + 26).append('*');
            } else {
                ans.append(charArray[i] - charArray[i - 1]).append('*');
            }
        }
        return ans.toString();
    }
}