LeetCode 301-400

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> result = new ArrayList<>();
        helper(result, s, 0, 0, '(', ')');
        return result;
    }

    private void helper(List<String> result, String s, int iStart, int jStart, char openPar, char closePar) {
        int openNum = 0, closeNum = 0;

        for (int i = iStart; i < s.length(); i++) {
            if (s.charAt(i) == openPar) {
                openNum++;
            }
            if (s.charAt(i) == closePar) {
                closeNum++;
            }

            // more closePar, so they need to be deleted
            if (closeNum > openNum) {
                for (int j = jStart; j <= i; j++) {
                    // encounter first ) and delete, then use substring to recursively check two strings at each side
                    if (s.charAt(j) == closePar && (j == jStart || s.charAt(j-1) != closePar)) {
                        helper(result, s.substring(0, j) + s.substring(j+1), i, j, openPar, closePar);
                    }
                }
                        
                return;
            }
        }

        // reverse the string and recheck
        String reversed = new StringBuilder(s).reverse().toString();
        
        // must check both '(' and ')'
        if (openPar == '(') {
            helper(result, reversed, 0, 0, ')', '(');
        } else {
            // current sting is valid, add to result
            result.add(reversed);
        }
    }
}

class Solution {
    public int minArea(char[][] image, int x, int y) {
        if (image == null || image.length == 0 || image[0].length == 0) {
            return 0;
        }

        int up = checkUp(image, x);
        int down = checkDown(image, x);
        int left = checkLeft(image, y);
        int right = checkRight(image, y);

        return (down - up + 1) * (right - left + 1);
    }

    private int checkUp(char[][] image, int x) {
        int lo = 0, hi = x;
        
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (rowContainsOne(image, mid)) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        
        return lo;
    }

    private int checkDown(char[][] image, int x) {
        int lo = x, hi = image.length - 1;
        
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (rowContainsOne(image, mid)) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        
        return hi;
    }

    private int checkLeft(char[][] image, int y) {
        int left = 0, right = y;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (colContainsOne(image, mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }

    private int checkRight(char[][] image, int y) {
        int left = y, right = image[0].length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (colContainsOne(image, mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return right;
    }

    private boolean rowContainsOne(char[][] image, int r) {
        for (int j = 0; j < image[0].length; j++) {
            if (image[r][j] == '1') {
                return true;
            }
        }
             
        return false;
    }

    private boolean colContainsOne(char[][] image, int c) {
        for (int i = 0; i < image.length; i++) {
            if (image[i][c] == '1') {
                return true;
            }
        }
             
        return false;
    }
}

class NumArray {

    private int[] sums;

    public NumArray(int[] nums) {
        sums = new int[nums.length];

        if (nums.length > 0) {
            sums[0] = nums[0];

            for (int i = 1; i < nums.length; i++) {
                sums[i] = sums[i - 1] + nums[i];
            }
        }
    }

    public int sumRange(int i, int j) {
        return i == 0 ? sums[j] : sums[j] - sums[i - 1];
    }
}

class NumMatrix {

    private int[][] dp;
    
    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        int row = matrix.length, col = matrix[0].length;
        dp = new int[row+1][col+1];

        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i-1][j-1];
            }
        }    
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2+1][col2+1] - dp[row2+1][col1] - dp[row1][col2+1] + dp[row1][col1];
    }
}

class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> result = new ArrayList<Integer>();
        int[] parent = new int[m*n + 1], rank = new int[m*n + 1];
        int numIslands = 0;

        for (int i = 0; i < positions.length; i++) {
            int x = positions[i][0];
            int y = positions[i][1];
            int offset = x*n + y+1;

            // duplicate position detected
            // all positions have parent 0 initially, in case the parent is not 0 we must have encountered the position before)
            if (parent[offset] != 0) {
                result.add(numIslands);
                continue;
            }

            parent[offset] = offset;
            numIslands++;

            if (x > 0 && parent[offset-n] != 0 && union(parent, rank, offset, offset-n)) {
                // check the grid on top of current grid
                numIslands--;
            }
            if (x < m-1 && parent[offset+n] != 0 && union(parent, rank, offset, offset+n)) {
                // check the grid below current grid
                numIslands--;
            }
            if (y > 0 && parent[offset-1] != 0 && union(parent, rank, offset, offset-1)) {
                // check the grid to the left of the current grid
                numIslands--;
            }
            if (y < n-1 && parent[offset+1] != 0 && union(parent, rank, offset, offset+1)) {
                // check the grid to the right of the current grid
                numIslands--;
            }
            result.add(numIslands);
        }
        
        return result;
    }

    // find root
    private int find(int[] parent, int x) {
        if (parent[x] == x) {
            return x;
        }
        return find(parent, parent[x]);
    }

    private boolean union(int[] parent, int[] rank, int x, int y) {
        int xparent = find(parent, x);
        int yparent = find(parent, y);

        // not belong to same island
        if (xparent == yparent) {
            return false;
        }

        if (rank[xparent] == rank[yparent]) {
            // same rank, sacrifice x and increment y's rank
            parent[xparent] = yparent;
            rank[yparent]++;
        } else if (rank[xparent] < rank[yparent]) {
            // higher rank is parent
            parent[xparent] = yparent;
        } else {
            parent[yparent] = xparent;
        }
        
        return true;
    }
}

class Solution {
    public boolean isAdditiveNumber(String num) {
        if (num == null || num.length() < 3) {
            return false;
        }

        int n = num.length();
        for (int i = 1; i <= n; i++) {
            // get first number
            String first = num.substring(0, i);

            // first number cannot start with 0
            if (first.startsWith("0") && first.length() > 1) {
                break;
            }

            // get second number
            for (int j = i + 1; j <= n; j++) {
                String second = num.substring(i, j);

                // second number cannot start with 0
                if (second.startsWith("0") && second.length() > 1) {
                    break;
                }


                String remain = num.substring(j);
                if (remain.length() == 0) {
                    break;
                }

                // skip impossible case, where the third number is less than previous one
                int maxLen = Math.max(first.length(), second.length());
                if (maxLen > remain.length()) {
                    break;
                }

                long firstNumber = Long.parseLong(first);
                long secondNumber = Long.parseLong(second);

                // deduct all following numbers and compare with string
                while (remain.length() != 0) {
                    long thirdNumber = firstNumber + secondNumber;
                    String third = String.valueOf(thirdNumber);
                    if (remain.startsWith(third)) {
                        firstNumber = secondNumber;
                        secondNumber = thirdNumber;
                        remain = remain.substring(third.length());
                    } else {
                        break;
                    }
                }

                // there should be no character left when finish
                if (remain.length() == 0) {
                    return true;
                } else {
                    continue;
                }
            }
        }
        
        return false;
    }
}

class NumArray {

    private int[] tree;
    private int n;

    public NumArray(int[] nums) {
        n = nums.length;

        tree = new int[2 * n];
        for (int i = n; i < n << 1; i++) {
            tree[i] = nums[i - n];
        }

        for (int i = n - 1; i > 0; i--) {
            tree[i] = tree[i << 1] + tree[i << 1 | 1];
        }
    }

    void update(int i, int val) {
        for (tree[i += n] = val; i > 0; i >>= 1) {
            tree[i >> 1] = tree[i] + tree[i ^ 1];
        }
    }

    public int sumRange(int i, int j) {
        int result = 0;
        for (i += n, j += n; i <= j; i >>= 1, j >>= 1) {
            if ((i & 1) == 1) {
                result += tree[i];
                i++;
            }
            if ((j & 1) == 0) {
                result += tree[j];
                j--;
            }
        }
        
        return result;
    }
}

class NumMatrix {

    private int[][] matrix;
    private int[][] lSumMatrix; // the sum of all previous columns

    public NumMatrix(int[][] matrix) {
        this.matrix = matrix;
        int len = matrix.length;
        if (len > 0) {
            lSumMatrix = new int[len][matrix[0].length]; 
            for (int i = 0; i < lSumMatrix.length; i++) {
                lSumMatrix[i][0] = matrix[i][0];
                for (int j = 1; j < lSumMatrix[i].length; j++) {
                    lSumMatrix[i][j] = lSumMatrix[i][j-1] + matrix[i][j];
                }
            }
        }
    }
    
    public void update(int row, int col, int val) {
        int difference = val - matrix[row][col];
        matrix[row][col] = val;

        // update all following columns
        for (int j = col; j < lSumMatrix[row].length; j++) {
            lSumMatrix[row][j] += difference;
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;

        // 2D version range sum - immutable
        for (int i = row1; i <= row2; i++) {
            sum += (lSumMatrix[i][col2] - (col1 > 0 ? lSumMatrix[i][col1-1] : 0));
        } 
            
        return sum;
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }

        // buy: max profit end with 'buy' action up to current day
        // sell: max profit end with 'sell' action up to current day
        // prevBuy, prevSell: max profit up to previous day
        int buy = Integer.MIN_VALUE, prevBuy = 0;
        int sell = 0, prevSell = 0;

        for (int price : prices) {
            prevBuy = buy;
            
            // use prevSell but not sell, since we cannot buy stock in 2 continuous days
            buy = Math.max(prevSell - price, prevBuy);

            prevSell = sell;
            sell = Math.max(prevBuy + price, prevSell);
        }
        
        return sell;
    }
}

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> leaves = new ArrayList<>();

        // 0 or 1 node tree
        if (n == 0) {
            return leaves;
        } else if (n == 1) { 
            leaves.add(0);
            return leaves;
        }

        List<Integer>[] lists = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            lists[i] = new ArrayList<>();
        }

        for (int[] e : edges) {
            int v1 = e[0], v2 = e[1];
            lists[v1].add(v2);
            lists[v2].add(v1);
        }

        // all nodes with only 1 edge must be a valid root
        for (int i = 0; i < n; i++) {
            if (lists[i].size() == 1) {
                leaves.add(i);
            }
        }

        int count = n;
        while (count > 2) {
            count -= leaves.size();
            List<Integer> newLeaves = new ArrayList<>();
            
            for (Integer leaf : leaves) {
                for (Integer toRemove : lists[leaf]) {
                    lists[toRemove].remove(Integer.valueOf(leaf));

                    // check whether become new leaf
                    if (lists[toRemove].size() == 1) {
                        newLeaves.add(toRemove);
                    }
                }
            }
            
            leaves = newLeaves;
        }
        
        return leaves;
    }
}

class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int newRow = A.length, ACol = A[0].length, newCol = B[0].length;
        int[][] result = new int[newRow][newCol];

        for (int i = 0; i < newRow; i++) {
            for (int j = 0; j < ACol; j++) {
                // sparse matrix
                if (A[i][j] != 0) {
                    for (int k = 0; k < newCol; k++) {
                        result[i][k] += A[i][j] * B[j][k];
                    }
                }
            }
        }
        
        return result;
    }
}

class Solution {
    public int maxCoins(int[] iNums) {
        if (iNums == null || iNums.length == 0) {
            return 0;
        }
        int n = iNums.length;

        // a new array, with iNums[-1] and iNums[n]
        int[] copy = new int[n+2];
        copy[0] = copy[n+1] = 1;
        for (int i = 0; i < n; i++) {
            copy[i+1] = iNums[i];
        }

        // dp[i][j] means the max coins collected from iNums[i] to iNums[j]
        int[][] dp = new int[n + 2][n + 2];

        // define the subproblem size
        for (int l = 1; l <= n; l++) {
            // We solve iNums[i] to iNums[i + l - 1]
            for (int i = 1; i + l - 1<= n; i++) {
                int j = i + l - 1;

                int best = 0;

                // three parts of coins
                // 1. burst ballons from index i to k - 1, i.e. copy[i: k - 1], max coins for this part is dp[i][k - 1]
                // 2. burst ballons from index k + 1 to j, i.e. copy[i: k - 1], max coins for this part is dp[k + 1][j]
                // 3. only copy[k] is left, the coins we can get is copy[i - 1] * copy[k] * copy[j + 1]
                for (int k = i; k <= j; k++) {
                    best = Math.max(best, dp[i][k - 1] + copy[i - 1] * copy[k] * copy[j + 1] + dp[k + 1][j]);
                }
                    
                dp[i][j] = best;
            }
        }

        return dp[1][n]; 
    }
}

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] ugly = new int[n + 1];
        ugly[0] = 1;

        int[] pointer = new int[primes.length];

        for (int i = 1; i < n; i++) {
            int min = Integer.MAX_VALUE;
            int minIndex = 0;

            // try all primes as factor
            for (int j = 0; j < primes.length; j++) {
                if (ugly[pointer[j]] * primes[j] < min) {
                    min = ugly[pointer[j]] * primes[j];
                    minIndex = j;
                } else if (ugly[pointer[j]] * primes[j] == min) {
                    pointer[j]++;
                }
            }

            // choose the smallest one as next ugly number
            ugly[i] = min;
            pointer[minIndex]++;
        }
        
        return ugly[n-1];
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) {
            return result;
        }

        // holding each level and values for that level
        Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();

        // each node in queue corresponds with each integer in levels
        ArrayDeque<TreeNode> queue = new ArrayDeque<TreeNode>();
        LinkedList<Integer> levels = new LinkedList<Integer>();
        queue.offer(root);
        levels.offer(0);

        // tracking min and max level for all nodes
        int minLevel = 0, maxLevel = 0;

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            int l = levels.poll(); // level of current node

            minLevel = Math.min(minLevel, l);
            maxLevel = Math.max(maxLevel, l);

            // for current level, add each node's value
            if (!map.containsKey(l)) {
                map.put(l, new ArrayList<>());
            }
            map.get(l).add(node.val);

            // add left and right children
            if (node.left != null) {
                queue.offer(node.left);
                levels.offer(l - 1);
            }
            if (node.right != null) {
                queue.offer(node.right);
                levels.offer(l + 1);
            }
        }

        // migrate each level's data to result
        for (int i = minLevel; i <= maxLevel; i++) {
            result.add(map.get(i));
        }

        return result; 
    }
}

class Item {
    int val;
    int index;
    
    public Item(int val, int index) {
        this.val = val;
        this.index = index;
    }
}

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        // stores each num and its index
        Item items[] = new Item[nums.length];
        for (int i = 0; i < nums.length; i++) {
            items[i] = new Item(nums[i], i);
        }
            
        // use mergesort to update count
        int count[] = new int[nums.length];
        mergesort(items, 0, items.length-1, count);
        
        // convert int[] to List
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < count.length; i++) {
            result.add(count[i]);
        }

        return result;
    }
    
    private void mergesort(Item items[], int low, int high, int count[]) {
        if (low >= high) {
            return;
        }
        
        int mid = low + (high - low) / 2;
        mergesort(items, low, mid, count);
        mergesort(items, mid+1, high, count);
        merge(items, low, mid, mid+1, high, count);
    }
    
    private void merge(Item[] items, int lowStart, int lowEnd, int highStart, int highEnd, int count[]) {
        int len = highEnd - lowStart + 1;
        Item[] sortedArr = new Item[len];
        
        int lowPtr = lowStart;
        int highPtr = highStart;
        int index = 0;
        int rightCount = 0;
        
        while (lowPtr <= lowEnd && highPtr <= highEnd) {
            if (items[highPtr].val < items[lowPtr].val) {
                rightCount++; 
                sortedArr[index] = items[highPtr];
                index++;
                highPtr++;
            } else {
                count[items[lowPtr].index] += rightCount;
                sortedArr[index] = items[lowPtr];
                index++;
                lowPtr++;
            }
            
        }
        
        // only one of the loop will be executed
        while (lowPtr <= lowEnd) {
            count[items[lowPtr].index] += rightCount;
            sortedArr[index] = items[lowPtr];
            index++;
            lowPtr++;
        }
        while (highPtr <= highEnd) {
            sortedArr[index] = items[highPtr];
            index++;
            highPtr++;
        }
        
        System.arraycopy(sortedArr, 0, items, lowStart, len);
    }
}

class Solution {
    public String removeDuplicateLetters(String s) {
        StringBuilder sb = new StringBuilder();
        int[] count = new int[26];
        boolean[] used = new boolean[26];

        char[] chr = s.toCharArray();

        // count how many times each character is used
        for (char c : chr) {
            count[c - 'a']++;
        }

        for (char c : chr) {
            // update count and see how many using times are left
            count[c - 'a']--;

            // this character is used in the result, skip
            if (used[c - 'a']) {
                continue;
            }

            // a new smaller character & there is still last character left, delete it
            // wait for the deleted character to be added later
            while (sb.length() > 0 && sb.charAt(sb.length() - 1) > c && count[sb.charAt(sb.length() - 1) - 'a'] > 0) {
                used[sb.charAt(sb.length() - 1) - 'a'] = false;
                sb.deleteCharAt(sb.length() - 1);
            }

            sb.append(c);
            used[c - 'a'] = true;
        }

        return sb.toString();
    }
}

class Solution {
    private int[][] dirs = new int[][]{ {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
        
    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int row = grid.length, col = grid[0].length;

        // a building which cannot be reached
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1 && !helper(grid, i, j, row, col)) {
                    return -1;
                }
            }
        }

        // select from all empty lands
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] < 0) {
                    result = Math.min(result, -grid[i][j]);
                }
            }
        }
        
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    private boolean helper(int[][] grid, int x, int y, int row, int col) {
        boolean[][] visited = new boolean[row][col];
        visited[x][y] = true;
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{x, y, 1});

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int[] p = queue.poll();
                
                for (int[] dir : dirs) {
                    int nx = p[0] + dir[0];
                    int ny = p[1] + dir[1];
                    if (nx < 0 || nx >= row || ny < 0 || ny >= col || visited[nx][ny]) {
                        continue;
                    }

                    visited[nx][ny] = true;

                    // for all empty lands, use BFS to increment distance
                    if (grid[nx][ny] <= 0) {
                        grid[nx][ny] -= p[2];
                        queue.offer(new int[]{nx, ny, p[2] + 1});
                    }
                }
            }
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (!visited[i][j]) {
                    // a building which cannot be reached
                    if (grid[i][j] == 1) {
                        return false;
                    }

                    // unused empty land
                    if (grid[i][j] <= 0) {
                        grid[i][j] = 3;
                    }
                }
            }
        }

        return true;
    }
}

class Solution {
    public int maxProduct(String[] words) {
        int[] arr = new int[words.length];

        // transform word into bits combination
        for (int i = 0; i < words.length; i++) {
            String cur = words[i];
            for (int j = 0; j < cur.length(); j++) {
                arr[i] |= 1 << (cur.charAt(j) - 'a');
            }
        }

        int maxLen = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                // different words
                if ((arr[i] & arr[j]) == 0) {
                    maxLen = Math.max(maxLen, words[i].length() * words[j].length());
                }
                    
            }
        }

        return maxLen;
    }
}

class Solution {
    public int bulbSwitch(int n) {
        return (int)Math.sqrt(n);
    }
}

class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> result = new ArrayList<>();
        backtrack(result, word, new StringBuilder(), 0, 0);
        return result;
    }

    // i for index, k for abbreviation
    private void backtrack(List<String> result, String word, StringBuilder sb, int i, int k) {
        int len = sb.length();
        if (i == word.length()) {
            if (k != 0) {
                sb.append(k);
            }
            result.add(sb.toString());
        } else {
            backtrack(result, word, sb, i+1, k+1);

            // generate an abbr
            if (k != 0) {
                sb.append(k);
            }
            sb.append(word.charAt(i));

            // start a new abbr from next character
            backtrack(result, word, sb, i+1, 0);
        }

        sb.setLength(len);
    }
}

class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int len1 = nums1.length, len2 = nums2.length;
        int[] result = new int[k];
        
        for (int i = Math.max(0, k - len2); i <= k && i <= len1; i++) {
            int[] candidate = merge(maxArray(nums1, i), maxArray(nums2, k - i), k);
            if (greater(candidate, 0, result, 0)) {
                result = candidate;
            }
        }
        return result;
    }

    // use mergesort to get a candidate array
    private int[] merge(int[] nums1, int[] nums2, int k) {
        int[] result = new int[k];
        for (int i = 0, j = 0, r = 0; r < k; r++) {
            result[r] = greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
        }
        return result;
    }

    // nums1 is 'greater than' nums2, if nums1 is longer or nums1[i] > nums2[j]
    private boolean greater(int[] nums1, int i, int[] nums2, int j) {
        while (i < nums1.length && j < nums2.length && nums1[i] == nums2[j]) {
            i++;
            j++;
        }
        return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]);
    }

    // get the max array within k length
    private int[] maxArray(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[k];
        for (int i = 0, j = 0; i < n; i++) {
            while (n - i + j > k && j > 0 && result[j - 1] < nums[i]) {
                j--;
            }
            if (j < k) {
                result[j] = nums[i];
                j++;
            }
        }
        
        return result;
    }
}

class Solution {
    public int coinChange(int[] coins, int amount) {
        int dp[] = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        
        return dp[amount] <= amount ? dp[amount] : -1;
    }
}

class Solution {
    public int countComponents(int n, int[][] edges) {
        int[] roots = new int[n];
        for (int i = 0; i < n; i++) {
            roots[i] = i; 
        }

        for (int[] e : edges) {
            int root1 = find(roots, e[0]);
            int root2 = find(roots, e[1]);

            // two vertex of this edge is a connected component
            if (root1 != root2) {    
                // union
                roots[root1] = root2;
                
                // numbers of cc decrement by 1
                n--;
            }
        }
        
        return n;
    }

    public int find(int[] roots, int id) {
        while (roots[id] != id) {
            // optional: path compression
            roots[id] = roots[roots[id]];
            
            id = roots[id];
        }
        
        return id;
    }
}

class Solution {
    public void wiggleSort(int[] nums) {
        int[] bucket = new int[5001];
        for (int num : nums) {
            bucket[num]++;
        }
        
        int index = 5000;
        
        // fill odd index
        for (int i = 1; i < nums.length; i += 2) {
            while (bucket[index] == 0) {
                index--;
            }
            nums[i] = index;
            bucket[index]--;
        }
        
        // fill even index
        for (int i = 0; i < nums.length; i += 2) {
            while (bucket[index] == 0) {
                index--;
            }
            nums[i] = index;
            bucket[index]--;
        }
    }
}

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>(); // <sum, index>
        map.put(0, -1);

        // every sum result
        for (int i = 1; i < nums.length; i++) {
            nums[i] += nums[i - 1];
        }

        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            // a new sum, add to map
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], i);
            }

            // find from previous sum key
            if (map.containsKey(nums[i] - k)) {
                result = Math.max(result, i - map.get(nums[i] - k));
            }
        }
        
        return result;
    }
}

class Solution {
    public boolean isPowerOfThree(int n) {
        return (n > 0 && 1162261467 % n == 0);
    }
}

class Solution {
    private int count = 0;
    private int lower;
    private int upper;

    public int countRangeSum(int[] nums, int lower, int upper) {
        this.lower = lower;
        this.upper = upper;

        long[] sum = new long[nums.length + 1];
        long[] temp = new long[nums.length + 1];
        sum[0] = 0;

        for (int i = 1; i <= nums.length; i++) {
            sum[i] = sum[i - 1] + (long) nums[i - 1];
        }

        mergesort(sum, 0, sum.length - 1, temp);
        return count;
    }

    private void mergesort(long[] sum, int start, int end, long[] temp) {
        if (start >= end) {
            return;
        }

        int mid = start + (end - start) / 2;
        mergesort(sum, start, mid, temp);
        mergesort(sum, mid + 1, end, temp);

        merge(sum, start, mid, end, temp);
    }

    private void merge(long[] sum, int start, int mid, int end, long[] temp) {
        int right = mid + 1;
        int index = start;
        int low = mid + 1, high = mid + 1;

        for (int left = start; left <= mid; left++) {
            // too small or too large 
            while (low <= end && sum[low] - sum[left] < lower) {
                low++;
            }
            while (high <= end && sum[high] - sum[left] <= upper) {
                high++;
            }

            // complete merge sort
            while (right <= end && sum[right] < sum[left]) {
                temp[index] = sum[right];
                index++;
                right++;
            }
            temp[index] = sum[left];
            index++;
            count += high - low;
        }
        while (right <= end) {
            temp[index] = sum[right];
                index++;
                right++;
        }

        // use cache to override sum
        for (int i = start; i <= end; i++) {
            sum[i] = temp[i];
        }
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head != null) {
            ListNode odd = head, even = head.next, evenHead = even; 

            while (even != null && even.next != null) {
                // link all odd elements
                odd.next = odd.next.next;
                odd = odd.next;

                // link all even elements
                even.next = even.next.next;
                even = even.next;
            }
            
            // even elements are placed behind odd elements
            odd.next = evenHead; 
        }
        
        return head;
    }
}

class Solution {
    private int result = 0;
    
    // store each grid's possible maximum number
    private int[][] maxGrid;

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int m = matrix.length, n = matrix[0].length;
        maxGrid = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                helper(matrix, i, j, Integer.MIN_VALUE);
            }
        }

        return result;
    }

    public int helper(int[][] matrix, int i, int j, int last) {
        if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length) {
            return 0;
        }

        // skip non-increasing case
        if (matrix[i][j] <= last) {
            return 0;
        }

        // fetch result from previous calculation
        if (maxGrid[i][j] != 0) {
            return maxGrid[i][j];
        }

        // four direcions 
        int v1 = helper(matrix, i-1, j, matrix[i][j]);
        int v2 = helper(matrix, i+1, j, matrix[i][j]);
        int v3 = helper(matrix, i, j-1, matrix[i][j]);
        int v4 = helper(matrix, i, j+1, matrix[i][j]);

        // choose the maximum result and update the maxGrid array
        int max = 1 + Math.max(v1, Math.max(v2, Math.max(v3, v4)));
        result = Math.max(result, max);
        maxGrid[i][j] = max;

        return max;
    }
}

class Solution {
    public int minPatches(int[] nums, int n) {
        long miss = 1;
        int result = 0, i = 0;

        while (miss <= n) {
            if (i < nums.length && nums[i] <= miss) {
                miss += nums[i];
                i++;
            } else {
                miss += miss;
                result++;
            }
        }
        
        return result;
    }
}

class Solution {
    public boolean isValidSerialization(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        int result = dfs(s, 0);

        // whether finish whole string's examination
        return result == s.length() - 1;
    }

    private int dfs(String s, int idx) {
        // cannot move forward, stop at current index
        if (idx >= s.length() || s.charAt(idx) == '#') {
            return idx;
        }

        // visit current node
        while (idx < s.length() && s.charAt(idx) != ',') {
            idx++;
        }

        // +1 to skip ','
        idx++;

        // visit left tree
        int l = dfs(s, idx);

        // right tree, finish
        return dfs(s, l + 2);
    }
}

class Solution {
    private Map<String, PriorityQueue<String>> flights;
    private LinkedList<String> path;

    public List<String> findItinerary(List<List<String>> tickets) {
        flights = new HashMap<>();
        path = new LinkedList<>();

        // for each departure place, maintain a priority queue of arrival places
        // by default, the string priority queue will be sorted in lexical order
        for (List<String> ticket : tickets) {
            flights.putIfAbsent(ticket.get(0), new PriorityQueue<>());
            flights.get(ticket.get(0)).add(ticket.get(1));
        }

        // always start from JFK
        dfs("JFK");
        return path;
    }

    public void dfs(String departure) {
        PriorityQueue<String> arrivals = flights.get(departure);

        // dfs to explore first arrival place
        while (arrivals != null && !arrivals.isEmpty()) {
            dfs(arrivals.poll());
        }

        // reversely add to the result
        path.addFirst(departure);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int largestBSTSubtree(TreeNode root) {
        int[] result = largestBST(root);
        return result[2];
    }

    private int[] largestBST(TreeNode node) {
        if (node == null) {
            return new int[] {Integer.MAX_VALUE, Integer.MIN_VALUE, 0};
        }

        int[] left = largestBST(node.left);
        int[] right = largestBST(node.right);

        // adding current node contributes to a new largest BST
        if (node.val > left[1] && node.val < right[0]) {
            return new int[] { Math.min(node.val, left[0]), Math.max(node.val, right[1]), left[2] + right[2] + 1 };
        }
            
        // otherwise, the largest BST should be either left subtree or right subtree
        return new int[] { Integer.MIN_VALUE, Integer.MAX_VALUE, Math.max(left[2], right[2]) };
    }
}

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int firstSmall = Integer.MAX_VALUE;
        int secondSmall = Integer.MAX_VALUE;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= firstSmall) {
                firstSmall = nums[i];
            } else if (nums[i] <= secondSmall) {
                secondSmall = nums[i];
            } else {
                return true;
            }
        }

        return false;
    }
}

class Solution {
    public boolean isSelfCrossing(int[] x) {
        if (x == null || x.length < 4) {
            return false;
        }

        for (int i = 3; i < x.length; i++) {
            // Fourth line crosses first line and onward
            if (x[i] >= x[i-2] && x[i-1] <= x[i-3]) {
                return true;
            }

            // Fifth line meets first line and onward
            if (i >= 4 && x[i-1] == x[i-3] && x[i] + x[i-4] >= x[i-2]) {
                return true;
            }

            // Sixth line crosses first line and onward
            if (i >= 5 && x[i-2] >=x[i-4] && x[i] >= x[i-2] - x[i-4] && x[i-1] >= x[i-3] - x[i-5] && x[i-1] <= x[i-3]) {
                return true;
            }
        }
        
        return false;
    }
}

class Solution {
    private static class TrieNode {
        TrieNode[] next;
        int index;
        List<Integer> list;

        TrieNode() {
            next = new TrieNode[26];
            index = -1;
            list = new ArrayList<>();
        }
    }

    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = new ArrayList<>();
        TrieNode root = new TrieNode();

        for (int i = 0; i < words.length; i++) {
            addWord(root, words[i], i);
        }
        for (int i = 0; i < words.length; i++) {
            search(words, i, root, result);
        }

        return result;
    }

    // add each word reversely
    private void addWord(TrieNode root, String word, int index) {
        for (int i = word.length() - 1; i >= 0; i--) {
            int j = word.charAt(i) - 'a';

            // add current word as a new node
            if (root.next[j] == null) {
                root.next[j] = new TrieNode();
            }

            if (isPalindrome(word, 0, i)) {
                root.list.add(index);
            }

            root = root.next[j];
        }

        root.list.add(index);
        root.index = index;
    }

    private void search(String[] words, int i, TrieNode root, List<List<Integer>> result) {
        for (int j = 0; j < words[i].length(); j++) {	
            // valid & non-equal index, all characters behind are palindrome
            if (root.index >= 0 && root.index != i && isPalindrome(words[i], j, words[i].length() - 1)) {
                result.add(Arrays.asList(i, root.index));
            }

            // move to next word
            root = root.next[words[i].charAt(j) - 'a'];
            if (root == null) {
                return;
            }
        }

        for (int j : root.list) {
            if (i == j) {
                continue;
            }
            result.add(Arrays.asList(i, j));
        }
    }

    private boolean isPalindrome(String word, int i, int j) {
        while (i < j) {
            if (word.charAt(i++) != word.charAt(j--)) {
                return false;
            }
        }
            
        return true;
    }
}