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

    private void helper(List<List<Integer>> result, int[] nums, int pos) {
        if (pos == nums.length) {
            List<Integer> permutation = new ArrayList<>();
            addNumToList(permutation, nums);
            result.add(permutation);
            return;
        }
        for (int i = pos; i < nums.length; i++) {
            swap(nums, pos, i);
            helper(result, nums, pos + 1);
            swap(nums, pos, i);
        }
    }

    private void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    private void addNumToList(List<Integer> list, int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            list.add(nums[i]);
        }
    }
}

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Map<Integer, Set<List<Integer>>> combinations = new HashMap<>();
        combinations.put(0, new HashSet<>());
        combinations.get(0).add(new ArrayList<>());
        helper(combinations, candidates, target);
        Set<List<Integer>> resultSet = combinations.get(target);
        return resultSet == null ? new ArrayList<>() : new ArrayList<>(resultSet);

    }

    // helper会给combinations这个map带来变化. 如果凑不成某个target, 那么该target和null就会组成pair存入map中
    // 如果target小于0, 那么map中将不会存储.
    private void helper(Map<Integer, Set<List<Integer>>> combinations, int[] candidates, int target) {
        if (target < 0)
            return;
        if (combinations.containsKey(target))
            return;
        Set<List<Integer>> combination = new HashSet<>();
        combinations.put(target, combination);
        for (int candidate : candidates) {
            helper(combinations, candidates, target - candidate);
            if (combinations.getOrDefault(target - candidate, null) != null) {
                Set<List<Integer>> s = combinations.get(target - candidate);
                for (List<Integer> comb : s) {
                    List<Integer> newComb = new ArrayList<>(comb);
                    newComb.add(candidate);
                    Collections.sort(newComb);
                    combination.add(newComb);
                }
            }
        }
        if (combination.size() == 0)
            combinations.put(target, null);
        return;
    }
}

class Solution {
    public int search(int[] nums, int target) {
        Integer result = helper(nums, 0, nums.length - 1, target);
        return result == null ? -1 : result;
    }

    private Integer helper(int[] nums, int low, int up, int target) {
        if (low > up)
            return null;
        int middle = low + (up - low) / 2;
        if (nums[middle] == target)
            return middle;
        else if (nums[middle] > nums[low]) {
            Integer result = binarySearch(nums, low, middle - 1, target);
            return result == null ? helper(nums, middle + 1, up, target) : result;
        } else {
            Integer result = binarySearch(nums, middle + 1, up, target);
            return result == null ? helper(nums, low, middle - 1, target) : result;
        }
    }

    private Integer binarySearch(int[] nums, int low, int up, int target) {
        int left = low, right = up;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (nums[middle] == target)
                return middle;
            else if (nums[middle] < target)
                left = middle + 1;
            else
                right = middle - 1;
        }
        return null;
    }
}

class Solution {
    private static Map<Integer, char[]> numCharset = new HashMap<>();
    static {
        numCharset.put(2, new char[] { 'a', 'b', 'c' });
        numCharset.put(3, new char[] { 'd', 'e', 'f' });
        numCharset.put(4, new char[] { 'g', 'h', 'i' });
        numCharset.put(5, new char[] { 'j', 'k', 'l' });
        numCharset.put(6, new char[] { 'm', 'n', 'o' });
        numCharset.put(7, new char[] { 'p', 'q', 'r', 's' });
        numCharset.put(8, new char[] { 't', 'u', 'v' });
        numCharset.put(9, new char[] { 'w', 'x', 'y', 'z' });
    }

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0)
            return result;
        helper(result, "", digits, 0);
        return result;
    }

    private void helper(List<String> result, String current, String digits, int pos) {
        if (pos == digits.length()) {
            result.add(current);
            return;
        }
        int currentDigit = digits.charAt(pos) - '0';
        char[] availableChars = numCharset.get(currentDigit);
        for (char availableChar : availableChars) {
            String newString = current + availableChar;
            helper(result, newString, digits, pos + 1);
        }
    }
}

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

class Solution {
    public int myAtoi(String s) {
        if (s.length() == 0)
            return 0;
        int pos = 0;

        // Remove leading space.
        while (pos < s.length() && s.charAt(pos) == ' ')
            pos += 1;
        if (pos == s.length())
            return 0;

        // Check the sign.
        boolean isPositive;
        if (Character.isDigit(s.charAt(pos)) || s.charAt(pos) == '+') {
            isPositive = true;
            pos = s.charAt(pos) == '+' ? pos + 1 : pos;
        } else if (s.charAt(pos) == '-') {
            isPositive = false;
            pos += 1;
        } else {
            return 0;
        }
        if (pos == s.length())
            return 0;

        // Remove leading 0s.
        while (pos < s.length() && s.charAt(pos) == '0')
            pos += 1;
        if (pos == s.length())
            return 0;

        // Get all digits.
        int[] digitRecorder = new int[s.length() - pos];
        int digPos = 0;
        while (pos < s.length() && Character.isDigit(s.charAt(pos))) {
            digitRecorder[digPos++] = s.charAt(pos++) - '0';
        }

        // Get the final result
        if (digPos > 11)
            return isPositive ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        long result = 0;
        long power = 1;
        for (int i = digPos - 1; i >= 0; i--) {
            result += digitRecorder[i] * power;
            if ((isPositive && result > Integer.MAX_VALUE) ||
                    (!isPositive && result > Integer.MAX_VALUE + 1L)) {
                return isPositive ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            power *= 10;
        }
        return isPositive ? (int) result : -(int) result;
    }
}

// 记录每一种出现的字符最后出现的位置.  
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int start = 0, ans = 0;
        Map<Character, Integer> visited = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            if (visited.containsKey(s.charAt(i)) && visited.get(s.charAt(i)) >= start) {
                start = visited.get(s.charAt(i)) + 1;
            }
            ans = Math.max(ans, i - start + 1);
            visited.put(s.charAt(i), i);
        }
        return ans;
    }
}

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        if (image[sr][sc] == color)
            return image;
        helper(image, sr, sc, image[sr][sc], color);
        image[sr][sc] = color;
        return image;
    }

    public void helper(int[][] image, int row, int col, int color, int newColor) {
        if (!isOutOfBound(image, row - 1, col) && image[row - 1][col] == color) {
            image[row - 1][col] = newColor;
            helper(image, row - 1, col, color, newColor);
        }
        if (!isOutOfBound(image, row + 1, col) && image[row + 1][col] == color) {
            image[row + 1][col] = newColor;
            helper(image, row + 1, col, color, newColor);
        }
        if (!isOutOfBound(image, row, col - 1) && image[row][col - 1] == color) {
            image[row][col - 1] = newColor;
            helper(image, row, col - 1, color, newColor);
        }
        if (!isOutOfBound(image, row, col + 1) && image[row][col + 1] == color) {
            image[row][col + 1] = newColor;
            helper(image, row, col + 1, color, newColor);
        }
    }

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

class Solution {
    public int search(int[] nums, int target) {
        return helper(0, nums.length - 1, nums, target);
    }

    public int helper(int start, int end, int[] nums, int target) {
        if (start > end)
            return -1;
        int middleIdx = (start + end) / 2;
        if (target > nums[middleIdx]) {
            return helper(middleIdx + 1, end, nums, target);
        } else if (target < nums[middleIdx]) {
            return helper(start, middleIdx - 1, nums, target);
        } else {
            return middleIdx;
        }
    }
}

public class Solution {
    int max = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return max;
    }

    // Given a node, it will update the global varibale max if
    // there is larger diameter in this tree and return the max
    // height of this tree.
    private int maxDepth(TreeNode root) {
        if (root == null)
            return 0;

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        max = Math.max(max, left + right);

        return Math.max(left, right) + 1;
    }
}