LeetCode 201-300

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        if (left == 0) {
            return 0;
        }

        int count = 0;
        while (left != right) {
            left >>>= 1;
            right >>>= 1;
            count++;
        }
        
        return left <<= count;
    }
}

class Solution {
    public boolean isHappy(int n) {
        int result = 0, current = 0;
        while (result != 1) {

            // calculate current result
            while (n != 0) {
                current = n % 10;
                n /= 10;
                result += current * current;
            }

            // result cannot be 1 or 4, otherwise fall into loop
            if (result > 1 && result != 4) {
                n = result;
                result = 0;
            } else {
                break;
            }
        }
        
        return result == 1;
    }
}

/**
 * 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 removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }

        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode prev = dummyHead, cur = head;
        while (cur != null) {
            // when current element's value is val, skip
            if (cur.val == val) {
                prev.next = cur.next;
            } else {
                prev = prev.next;
            } 

            // always move forward cur
            cur = cur.next;
        }
        
        return dummyHead.next;
    }
}

class Solution {
    public int countPrimes(int n) {
        if (n < 3) {
            return 0;
        }

        boolean[] prime = new boolean[n];
        Arrays.fill(prime, true);
        
        // assume all odd numbers are prime number
        int result = n / 2;

        for (int i = 3; i * i < n; i += 2) {
            // skip a composite number
            if (!prime[i]) {
                continue;
            }

            // multiples of composite numbers are skipped
            for (int j = i * i; j < n; j += 2 * i) {
                // this multiple of i has not been excluded
                if (prime[j]) {
                    result--;
                    prime[j] = false;
                }
            }     
        }
        
        return result;
    }
}

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();

        char[] sMap = new char[256];
        char[] tMap = new char[256];

        for (int i = 0; i < sChars.length; i++) {
            char a = sChars[i], b = tChars[i];

            // not yet mapped
            if (sMap[a] == 0 && tMap[b] == 0) {
                sMap[a] = b;
                tMap[b] = a;
            } else if (sMap[a] != b || tMap[b] != a) {
                return false;
            }
        }
        
        return true;
    }
}

/**
 * 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 reverseList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;

            prev = head;
            head = next;
        }
        
        return prev;
    }
}

/**
 * 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 reverseList(ListNode head) {
        return reverse(head, null);
    }

    private ListNode reverse(ListNode head, ListNode prev) {
        if (head == null) {
            return prev;
        }

        ListNode next = head.next;
        head.next = prev;
        return reverse(next, head);
    }
}

class Solution {
    boolean isCycle = false;
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {

        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // add all subsequent courses for each course
        for (int[] prerequisite : prerequisites)
            graph.get( prerequisite[1] ).add( prerequisite[0] );  

        int[] courseStatus = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (courseStatus[i] == 0) {
                dfs(courseStatus, i, graph);
            }
        }
        
        return !isCycle;
    }    

    // 0 unvisited, 1 visiting, 2 visited
    private void dfs(int[] courseStatus, int node, List<List<Integer>> graph) {
        courseStatus[node] = 1;

        for (int next : graph.get(node)) {
            if (courseStatus[next] == 0) {
                dfs(courseStatus, next, graph);
            }
            
            if (courseStatus[next] == 1) {
                isCycle = true;
            }
        }
        
        courseStatus[node] = 2; 
    }
}

class Trie {

    class TrieNode {
        public TrieNode() {}
        boolean isEnd = false;
        TrieNode[] children = new TrieNode[26];
    }
    
    private TrieNode root = new TrieNode();
    
    /** Initialize your data structure here. */
    public Trie() {}
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            if (cur.children[c - 'a'] == null) {
                cur.children[c - 'a'] = new TrieNode();
            }
            cur = cur.children[c - 'a'];
        }
        
        cur.isEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            if (cur.children[c - 'a'] == null) {
                return false;
            }
            cur = cur.children[c - 'a'];
        }

        // must exactly match, so the word in trie should also end
        return cur.isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for (char c : prefix.toCharArray()) {
            if (cur.children[c - 'a'] == null) {
                return false;
            }
            cur = cur.children[c - 'a'];
        }

        return true;
    }
}

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int sum = 0, left = 0, right = 0;
        
        // By default, the minimum length is Max integer
        int result = Integer.MAX_VALUE;

        while (right < nums.length) {
            sum += nums[right];
            right++;

            // delete as many nums[left] as possible
            while (sum >= s) {
                result = Math.min(result, right - left);
                sum -= nums[left];
                left++;
            }
        }
        
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

class Solution {
    boolean isCycle = false;
    int[] result;
    int resultIndex;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        result = new int[numCourses];
        resultIndex = numCourses - 1; // start from the last course

        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // add all subsequent courses for each course
        for (int[] prerequisite : prerequisites) {
            graph.get( prerequisite[1] ).add( prerequisite[0] );
        } 

        int[] courseStatus = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (courseStatus[i] == 0) {
                dfs(courseStatus, i, graph);
            }
        }
        
        return isCycle ? new int[]{} : result;
    }

    // 0 unvisited, 1 visiting, 2 visited
    private void dfs(int[] courseStatus, int node, List<List<Integer>> graph) {
        courseStatus[node] = 1;

        for (int next : graph.get(node)) {
            if (courseStatus[next] == 0) {
                dfs(courseStatus, next, graph);
            }
            
            if (courseStatus[next] == 1) {
                isCycle = true;
            }
        }
        
        courseStatus[node] = 2;
        
        result[resultIndex] = node;
        resultIndex--;
    }
}

class WordDictionary {

    public class TrieNode {
        public TrieNode() {}
        TrieNode[] children = new TrieNode[26];
        boolean isEnd = false;

        public boolean match(String word, int index) {
            if (index == word.length()) {
                return isEnd;
            }

            // check all not-null children
            if (word.charAt(index) == '.') {
                for (int i = 0 ; i < 26; i++) {
                    if (children[i] != null && children[i].match(word, index + 1)) {
                        return true;
                    }
                }

                return false;
            } else {
                return children[word.charAt(index) - 'a'] != null && children[word.charAt(index) - 'a'].match(word, index + 1);
            }
        }
    }
    
    private TrieNode root = new TrieNode();

    /** Initialize your data structure here. */
    public WordDictionary() {}

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            if (cur.children[c - 'a'] == null) {
                cur.children[c - 'a'] = new TrieNode();
            }
            
            cur = cur.children[c - 'a'];
        }
        
        cur.isEnd = true;
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        return root.match(word, 0);
    }
}

class Solution {
    public class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word;
    }

    public TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        
        for (String word : words) {
            TrieNode cur = root;
            for (char c : word.toCharArray()) {
                if (cur.children[c - 'a'] == null) {
                    cur.children[c - 'a'] = new TrieNode();
                }
                cur = cur.children[c - 'a'];
            }

            // only set cur.word when finishing inserting a word
            cur.word = word;
        }
        
        return root;
    }

    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        TrieNode root = buildTrie(words);
        
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, root, result);
            }
        }
                
        return result;
    }

    public void dfs(char[][] board, int i, int j, TrieNode cur, List<String> result) {
        char c = board[i][j];
        if (c == '#' || cur.children[c - 'a'] == null) {
            return;
        }
        cur = cur.children[c - 'a'];

        // end of current word
        if (cur.word != null) {
            result.add(cur.word);
            
            // avoid repeat searching
            cur.word = null;
        }

        // temporarily mark visited character
        board[i][j] = '#'; 
        
        // try four adjacent grids
        if (i > 0) {
            dfs(board, i - 1, j, cur, result);
        } 
        if (j > 0) {
            dfs(board, i, j - 1, cur, result);
        }
        if (i < board.length - 1) {
            dfs(board, i + 1, j, cur, result);
        } 
        if (j < board[0].length - 1) {
            dfs(board, i, j + 1, cur, result); 
        }
        
        board[i][j] = c;
    }
}

class Solution {
    private int helper(int[] nums, int low, int high) {
    
        // prev2: max profit without current number's prior number
        // prev: max profit between (1. without current number 2. prev2 + current number)
        int prev2 = 0, prev = 0;

        for (int i = low; i <= high; i++) {
            int temp = prev;
            prev = Math.max(prev, prev2 + nums[i]);
            prev2 = temp;
        }

        return prev;
    }

    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        } else if (nums.length == 1) {
            return nums[0];
        }
        
        return Math.max(helper(nums, 0, nums.length - 2), helper(nums, 1, nums.length - 1));
    }
}

class Solution {
    public String shortestPalindrome(String s) {
        if (s.length() == 0 || s.length() == 1) {
            return s;
        }

        // try to divide the string into two parts, using head
        int head = 0;
        for (int tail = s.length() - 1; tail >= 0; tail--) {
            if (s.charAt(head) == s.charAt(tail)) {
                head++;
            }
        }
             
        // already a palindrome
        if (head == s.length()) {
            return s;
        }

        String suffix = s.substring(head);
        return new StringBuilder(suffix).reverse().toString() + shortestPalindrome(s.substring(0, head)) + suffix;
    }
}

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        // kth largest is equal to (nums.length - k)th smallest
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }

    // quick select: kth smallest
    public int quickSelect(int[] nums, int begin, int end, int k) {
        if (begin == end) {
            return nums[begin];
        }
        if (begin > end) {
            return Integer.MAX_VALUE;
        }

        int pivot = nums[begin + (end - begin) / 2];
        int left = begin;
        int right = end;

        while (left <= right) {
            while (left <= right && nums[left] < pivot) {
                left++;
            }
            while (left <= right && nums[right] > pivot) {
                right--;
            }

            if (left <= right) {
                swap(nums, left, right);
                left++;
                right--;
            }
        }

        if (right >= k && right >= begin) {
            return quickSelect(nums, begin, right, k);
        } else if (left <= k && left <= end) {
            return quickSelect(nums, left, end, k);
        } else {
            return nums[k];
        }
    } 

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

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List< List<Integer> > result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), k, n, 1);
        return result;
    }

    private void backtrack(List< List<Integer> > result, List<Integer> temp, int k, int n, int start) {
        if (temp.size() == k && n == 0) {
            result.add(new ArrayList<>(temp));
            return;
        }

        for (int i = start; i <= 9; i++) {
            temp.add(i);

            // need k numbers; remain sum is n - i; starting index is i + 1
            backtrack(result, temp, k, n - i, i + 1);
            temp.remove(temp.size() - 1);
        }
    }
}

class Solution {
    public boolean containsDuplicate(int[] nums) {
        if (nums.length <= 1) {
            return false;
        }
      
        Set<Integer> set = new HashSet<Integer>();
        for (Integer num : nums) {
            if (!set.add(num)) {
                return true;
            }
        }
        
        return false;
    }
}

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> result = new ArrayList();

        List<int[]> height = new ArrayList();
        for (int[] b : buildings) {
            height.add(new int[]{b[0], -b[2]});
            height.add(new int[]{b[1], b[2]});
        }

        // first sort by x coordinate, then sort by height
        Collections.sort(height, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);

        // <height, num>
        TreeMap<Integer, Integer> bst = new TreeMap();
        bst.put(0, 1);
        int prev = 0;

        for (int[] h : height) {
            
            if (h[1] < 0) {
                // a new building is incoming
                bst.put(-h[1], bst.getOrDefault(-h[1], 0) + 1);
            } else if (bst.get(h[1]) == 1) {
                // current highest building reaches end, should output second highest building later
                bst.remove(h[1]);
            } else {
                bst.put(h[1], bst.get(h[1]) - 1);
            }

            // output highest new building
            int cur = bst.lastKey();
            if (cur != prev) {
                result.add(new ArrayList(Arrays.asList(h[0], cur)));
                prev = cur;
            }
        }

        return result;
    }
}

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            // if not present, new entry, else the old entry will be updated
            Integer idx = map.put(nums[i], i);
            
            if (idx != null && Math.abs(idx - i) <= k) {
                return true;
            }
        }
        
        return false;
    }
}

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length < 2) {
            return false;
        }

        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            long num = (long)nums[i];

            // get upper bound and lower bound of current num
            // find if there is any element in this range
            Long floor = set.floor(num), ceiling = set.ceiling(num);
            if ((floor != null && num - floor <= t) || (ceiling != null && ceiling - num <= t)) {
                return true;
            }

            // add current num to set
            set.add(num);
            
            // delete k-th number backward
            if (i >= k) {
                set.remove((long)nums[i - k]); 
            }
        }
        
        return false;
    }
}

class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int row = matrix.length, col = matrix[0].length;
        int[][] dp = new int[row + 1][col + 1];
        int result = 0;

        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                if (matrix[i-1][j-1] == '1') {
                    // minimum of up, left, upper left grids
                    dp[i][j] = Math.min(Math.min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1]) + 1;
                    result = Math.max(dp[i][j], result);
                }
            }
        }
             
        return result * result;
    }
}

/**
 * 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 countNodes(TreeNode root) {
        int leftDepth = getLeftDepth(root);
        int rightDepth = getRightDepth(root);

        if (leftDepth == rightDepth) {
            return (1 << leftDepth) - 1;
        }
        
        return 1 + countNodes(root.left) + countNodes(root.right);
    }

    private int getLeftDepth(TreeNode node) {
        int depth = 0;
        while (node != null) {
            node = node.left;
            depth++;
        }
        return depth;
    }

    private int getRightDepth(TreeNode node) {
        int depth = 0;
        while (node != null) {
            node = node.right;
            depth++;
        }
        return depth;
    }
}

class Solution {
    public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        if (bx1 > ax2 || bx2 < ax1) {
            return (ax2 - ax1) * (ay2 - ay1) + (bx2 - bx1) * (by2 - by1);
        }

        int left = Math.max(ax1, bx1);
        int right = Math.min(ax2, bx2);
        int bottom = Math.max(ay1, by1);
        int top = Math.min(ay2, by2);

        int overlap = 0;
        if (right > left && top > bottom) {
            overlap = (right - left) * (top - bottom);
        }

        return (ax2 - ax1) * (ay2 - ay1) + (bx2 - bx1) * (by2 - by1) - overlap;
    }
}

class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        Stack<Integer> stack = new Stack<Integer>();
        int result = 0, sign = 1, num = 0;

        stack.push(sign);
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c >= '0' && c <= '9') {
                num = num * 10 + c - '0';
            } else if (c == '+' || c == '-') {
                result += sign * num;
                sign = stack.peek() * (c == '+' ? 1 : -1);
                num = 0;
            } else if (c == '(') {
                stack.push(sign);
            } else if (c == ')') {
                stack.pop();
            }
        }

        result += sign * num;
        return result;
    }
}

class MyStack {

    private Queue<Integer> queue = new ArrayDeque<>();
    
    /** Initialize your data structure here. */
    public MyStack() {}

    /** Push element x onto stack. */
    public void push(int x) {
        queue.offer(x);
        for (int i = 1; i < queue.size(); i++) {
            queue.offer(queue.poll());
        }
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();
    }

    /** Get the top element. */
    public int top() {
        return queue.peek();
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}

/**
 * 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 TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode left = root.left, right = root.right;
        root.left = invertTree(right);
        root.right = invertTree(left);
        return root;
    }
}

class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        Stack<Integer> stack = new Stack<>();
        
        // ensure that the last number can be pushed into the stack
        s += '+';
        
        // operand
        int num = 0; 
        
        // operator
        char op = '+';

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if (c >= '0' && c <= '9') {
                num = num * 10 + c - '0';
                continue;
            }
            
            if (c == ' ') {
                continue;
            }
            
            if (op == '+') {
                stack.push(num);
            }
            if (op == '-') {
                stack.push(-num);
            }
            if (op == '*') {
                stack.push(stack.pop() * num);
            }
            if (op == '/') {
                stack.push(stack.pop() / num);
            }

            op = c;
            num = 0;
        }
        
        int result = 0;
        while (!stack.isEmpty()) {
            result += stack.pop();
        }
        
        return result;
    }
}

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> result = new LinkedList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        
        if (nums.length == 1) {
            result.add(nums[0] + "");
            return result;
        }

        for (int i = 0; i < nums.length; i++) {
            int temp = nums[i];

            // continuous pages
            while (i + 1 < nums.length && (nums[i+1] - nums[i] == 1)) {
                i++;
            }

            if (temp != nums[i]) {
                result.add(temp + "->" + nums[i]);
            } else {
                result.add(temp + "");
            }
        }
        
        return result;
    }
}

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int count1 = 0, count2 = 0;
        Integer candidate1 = null, candidate2 = null;
        for (int num : nums) {
            if (candidate1 != null && candidate1 == num) {
                count1++;
            } else if (candidate2 != null && candidate2 == num) {
                count2++;
            } else if (count1 == 0) {
                // candidate1 has been updated
                candidate1 = num;
                count1++;
            } else if (count2 == 0) {
                // candidate2 has been updated
                candidate2 = num;
                count2++;
            } else {
                // reduce the portion of candidate1 and candidate2
                count1--;
                count2--;
            }
        }

        count1 = 0;
        count2 = 0;
        for (int num : nums) {
            if (candidate1 != null && candidate1 == num) {
                count1++;
            }
            if (candidate2 != null && candidate2 == num) {
                count2++;
            }
        }

        List<Integer> result = new ArrayList<>();
        if (count1 > nums.length/3) {
            result.add(candidate1);
        }
        if (count2 > nums.length/3) {
            result.add(candidate2);
        }
        
        return result;
    }
}

/**
 * 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 {
    private int count = 0;
    private boolean resultModified = false;
    private int result = Integer.MIN_VALUE;

    public int kthSmallest(TreeNode root, int k) {
        helper(root, k);
        return result;
    }

    private void helper(TreeNode node, int k) {
        if (node == null || resultModified) {
            return;
        }

        helper(node.left, k);
        
        count++;
        if (count == k) {
            result = node.val;
            resultModified = true;
            return;
        }
        
        helper(node.right, k);
    }
}

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

class MyQueue {

    Stack<Integer> in;
    Stack<Integer> out;

    /** Initialize your data structure here. */
    public MyQueue() {
        in = new Stack<Integer>();
        out = new Stack<Integer>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        in.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        peek();
        return out.pop();
    }

    /** Get the front element. */
    public int peek() {
        // if out is empty, pop top element of in and push it into out
        if (out.isEmpty()) {
            while (!in.isEmpty()) out.push(in.pop());
        }
            
        return out.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}

class MyQueue {

    Object lock;
    Stack<Integer> in;
    Stack<Integer> out;

    /** Initialize your data structure here. */
    public MyQueue() {
        lock = new Object();
        in = new Stack<Integer>();
        out = new Stack<Integer>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        // must get lock to run the code inside synchronized
        synchronized(lock) {
            in.push(x);
        }
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        peek();
        return out.pop();
    }

    /** Get the front element. */
    public int peek() {
        // if out is empty, pop top element of in and push it into out
        if (out.isEmpty()) {
            synchronized(lock) {
                while (!in.isEmpty()) out.push(in.pop());
            }
        }
        return out.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}

class Solution {
    public int countDigitOne(int n) {
        int result = 0;
        for (long k = 1; k <= n; k *= 10) {
            long r = n / k, m = n % k;
            result += (r + 8) / 10 * k + (r % 10 == 1 ? m + 1 : 0);
        }
        return result;
    }
}

/**
 * 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 boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // odd length
        if (fast != null) {
            slow = slow.next;
        }

        // reverse second half of the list
        slow = reverse(slow);
        fast = head;

        // compare two halves
        while (slow != null) {
            if (slow.val != fast.val) {
                return false;
            }
            
            slow = slow.next;
            fast = fast.next;
        }
        
        return true;
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;

            prev = head;
            head = next;
        }
        return prev;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // root.val is not between p.val and q.val
        while ((root.val - p.val) * (root.val - q.val) > 0) {
            root = p.val < root.val ? root.left : root.right;
        }
            
        return root;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }

        // whether can we find p or q in left & right subtrees
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // wrong path
        if (left == null && right == null) {
            return null;
        }
        
        // current node is LCA
        if (left != null && right != null) {
            return root; 
        }
        
        // null in one subtree, find in the other
        return left == null ? right : left;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] result = new int[len];
        result[0] = 1;

        // product of left part
        for (int i = 1; i < len; i++) {
            result[i] = result[i-1] * nums[i-1]; 
        }

        // product of right part
        int right = 1;
        for (int i = len - 1; i >= 0; i--) {
            result[i] *= right;
            right *= nums[i];
        }
        
        return result;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || nums.length < k) {
            return new int[] {};
        }

        int len = nums.length;
        int[] result = new int[len - k + 1];
        LinkedList<Integer> list = new LinkedList<>();

        for (int i = 0; i < len; i++) {
            // remove first element
            if (!list.isEmpty() && list.peek() < i - k + 1) {
                list.poll();
            }

            // remove unnecessary indices
            while (!list.isEmpty() && nums[i] >= nums[list.peekLast()]) {
                list.pollLast();
            }

            // new result
            list.offer(i);
            if (i - k + 1 >= 0) {
                result[i - k + 1] = nums[list.peek()];
            }
        }
        
        return result;
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int row = 0, col = matrix[0].length - 1;

        // start from the upper right
        while (col >= 0 && row < matrix.length) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] < target) {
                row++;
            } else {
                col--;
            }
        }
        
        return false;
    }
}

class Solution {
    // <current input string, all possible results>
    private Map<String, List<Integer>> map = new HashMap<>();

    public List<Integer> diffWaysToCompute(String input) {
        // check history
        List<Integer> result = map.get(input);
        if (result != null) {
            return result;
        }
        result = new ArrayList<>();

        // only one digit left, put current result to map
        if (isDigit(input)) {
            result.add(Integer.parseInt(input));
            map.put(input, result);
            return result;
        }

        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                List<Integer> left = diffWaysToCompute(input.substring(0,i));
                List<Integer> right = diffWaysToCompute(input.substring(i+1));

                for (Integer il : left) {
                    for (Integer ir : right) {
                        if (c == '+') {
                            result.add(il + ir);
                        } else if (c == '-') {
                            result.add(il - ir);
                        } else if (c == '*') {
                            result.add(il * ir);
                        }
                    }
                }
            }
        }
        
        map.put(input, result);
        return result;
    }

    private boolean isDigit(String s) {
        for (Character c : s.toCharArray()) {
            if (c < '0' || c > '9') {
                return false;
            }
        }
             
        return true;
    }
}

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] map = new int[256];

        // how many times each characters occur in s
        for (char c : s.toCharArray()) {
            map[c]++;
        }

        // check whether match occurrence in t
        for (char c : t.toCharArray()) {
            map[c]--;
            if (map[c] < 0) {
                return false;
            } 
        }

        return true;
    }
}

class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        int result = Integer.MAX_VALUE;
        int index1 = -1, index2 = -1;

        for (int i = 0; i < words.length; i++) {
            // always update indices
            if (words[i].equals(word1)) {
                index1 = i;
            } else if (words[i].equals(word2)) {
                index2 = i;
            } else {
                continue;
            }

            if (index1 >= 0 && index2 >= 0) {
                result = Math.min(result, Math.abs(index1 - index2));
            }
        }
        
        return result;
    }
}

class WordDistance {

    // for each word, store its occurrence index
    HashMap<String, List<Integer>> map;

    public WordDistance(String[] words) {
        map = new HashMap();
        for (int i = 0; i < words.length; i++) {
            String currentWord = words[i];
            if (!map.containsKey(currentWord)) {
                map.put(currentWord, new ArrayList<>());
            }
            map.get(currentWord).add(i);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> list1 = map.get(word1), list2 = map.get(word2);
        int result = Integer.MAX_VALUE;

        int p1 = 0, p2 = 0;
        while (p1 < list1.size() && p2 < list2.size()) {
            int index1 = list1.get(p1), index2 = list2.get(p2);

            // make two pointers as close as possible
            // shift the smaller index to its maximum value
            if (index1 > index2) {
                p2++; 
            } else {
                p1++;
            }

            result = Math.min(result, Math.abs(index1 - index2));
        }
        return result;
    }
}

class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        int result = Integer.MAX_VALUE;
        int index1 = -1, index2 = -1;
        boolean isEqual = word1.equals(word2);

        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                index1 = i;
            } else if (words[i].equals(word2)) {
                index2 = i;
            } else {
                continue;
            }

            if (index1 >= 0 && index2 >= 0) {
                result = Math.min(result, Math.abs(index1 - index2));
            }

            // if word1 and word2 are equal, their indices should be set equally before next loop
            if (isEqual) {
                index2 = index1;
            }
        }
        return result;
    }
}

class Solution {
    public boolean isStrobogrammatic(String num) {
        char[] check = new char[10];
        // strobogrammatic number
        check[1] = '1';
        check[6] = '9';
        check[0] = '0';
        check[9] = '6';
        check[8] = '8';

        int low = 0, high = num.length() - 1;
        while (low <= high) {
            // must form strobogrammatic number pairs
            if (num.charAt(low) != check[num.charAt(high) - '0']) {
                return false;
            }
            
            low++;
            high--;
        }

        return true;
    }
}

class Solution {
    public List<String> findStrobogrammatic(int n) {
        return helper(n, n);
    }

    private List<String> helper(int current, int n) {
        if (current == 0) {
            return new ArrayList<String>(Arrays.asList(""));
        }
        if (current == 1) {
            return new ArrayList<String>(Arrays.asList("0", "1", "8"));
        }

        // reduce current digits count by 2 and add two new digits to head and tail
        List<String> list = helper(current - 2, n);

        List<String> result = new ArrayList<String>();
        for (int i = 0; i < list.size(); i++) {
            String s = list.get(i);
            if (current != n) {
                // 00 cannot be head and tail
                result.add("0" + s + "0");
            }
            result.add("1" + s + "1");
            result.add("6" + s + "9");
            result.add("9" + s + "6");
            result.add("8" + s + "8");
        }
        
        return result;
    }
}

class Solution {
    public int strobogrammaticInRange(String low, String high) {
        int n = low.length();
        while (n <= high.length()) {
            dfs(0, n - 1, new char[n], low, high);
            n++;
        }
        return result;
    }

    private char[][] converts = new char[][]{new char[]{'0' ,'0'}, new char[]{'1' ,'1'},
                                             new char[]{'6' ,'9'}, new char[]{'8' ,'8'}, new char[]{'9' ,'6'}};
    private int result = 0;

    private void dfs(int i, int j, char[] num, String low, String high) {
        if (i > j) {
            if (!isSmallerThan(num, low) && !isLargerThan(num, high)) {
                result++;
            }
            return;
        }

        // try two digits
        for (char[] convert : converts) {
            num[i] = convert[0];
            num[j] = convert[1];
            
            if (i == 0 && num.length > 1 && convert[0] == '0') {
                continue;
            }
            if (i == j && convert[0] != convert[1]) {
                continue;  
            }          
            dfs(i + 1, j - 1, num, low, high);
        }
    }

    private boolean isLargerThan(char[] num, String high) {
        if (num.length < high.length()) {
            return false;
        }
        int i = 0;
        while (i < high.length()) {
            if (num[i] == high.charAt(i)) {
                i++;
                continue;
            }
            
            return num[i] > high.charAt(i);
        }
        
        return false;
    }

    private boolean isSmallerThan(char[] num, String low) {
        if (num.length > low.length()) {
            return false;
        }

        int i = 0;
        while (i < low.length()) {
            if (num[i] == low.charAt(i)) {
                i++;
                continue;
            }
            
            return num[i] < low.charAt(i);
        }
        
        return false;
    }
}