public class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int m = A.length, n = A[0].length, nB = B[0].length;
        int[][] C = new int[m][nB];

        for(int i = 0; i < m; i++) {
            for(int k = 0; k < n; k++) {
                if (A[i][k] != 0) {
                    for (int j = 0; j < nB; j++) {
                        if (B[k][j] != 0) C[i][j] += A[i][k] * B[k][j];
                    }
                }
            }
        }
        return C;
    }
}

public double angleClock(int hour, int minutes) {
        //in case hour is 12, down to actually 0
        hour%=12;
        //distance from 0 to hour clock / total distance for the whole circle.
        double hourPercentage = (hour + minutes/60.0D)/12.0D;
        double minutePercentage = minutes/60.0D;
        double diff = Math.abs(hourPercentage-minutePercentage);
        //min is to find the smaller angle -> 270 will down to 90.
        return 360 * Math.min(diff,1-diff);
    }

class Solution {
    public List<String> crawl(String startUrl, HtmlParser htmlParser) {

        // find hostname
        int index = startUrl.indexOf('/', 7);
        String hostname = (index != -1) ? startUrl.substring(0, index) : startUrl;

        // multi-thread
        Crawler crawler = new Crawler(startUrl, hostname, htmlParser);
        crawler.map = new ConcurrentHashMap<>(); // reset result as static property belongs to class, it will go through all of the test cases
        crawler.result = crawler.map.newKeySet();
        Thread thread = new Thread(crawler);
        thread.start();

        crawler.joinThread(thread); // wait for thread to complete
        return new ArrayList<>(crawler.result);
    }
}

class Crawler implements Runnable {
    String startUrl;
    String hostname;
    HtmlParser htmlParser;
    public static ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
    public static Set<String> result = map.newKeySet();

    public Crawler(String startUrl, String hostname, HtmlParser htmlParser) {
        this.startUrl = startUrl;
        this.hostname = hostname;
        this.htmlParser = htmlParser;
    }

    @Override
    public void run() {
        if (this.startUrl.startsWith(hostname) && !this.result.contains(this.startUrl)) {
            this.result.add(this.startUrl);
            List<Thread> threads = new ArrayList<>();
            for (String s : htmlParser.getUrls(startUrl)) {
			    if(result.contains(s)) continue;
                Crawler crawler = new Crawler(s, hostname, htmlParser);
                Thread thread = new Thread(crawler);
                thread.start();
                threads.add(thread);
            }
            for (Thread t : threads) {
                joinThread(t); // wait for all threads to complete
            }
        }
    }

    public static void joinThread(Thread thread) {
        try {
            thread.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

class Solution {
    public List<String> crawl(String startUrl, HtmlParser htmlParser) {
        String hostname = getHostname(startUrl);

        Set<String> visited = ConcurrentHashMap.newKeySet();
        visited.add(startUrl);

        return crawl(startUrl, htmlParser, hostname, visited)
            .collect(Collectors.toList());
    }

    private Stream<String> crawl(String startUrl, HtmlParser htmlParser, String hostname, Set<String> visited) {
        Stream<String> stream = htmlParser.getUrls(startUrl)
            .parallelStream()
            .filter(url -> isSameHostname(url, hostname))
            .filter(url -> visited.add(url))
            .flatMap(url -> crawl(url, htmlParser, hostname, visited));

        return Stream.concat(Stream.of(startUrl), stream);
    }

    private String getHostname(String url) {
        int idx = url.indexOf('/', 7);
        return (idx != -1) ? url.substring(0, idx) : url;
    }

    private boolean isSameHostname(String url, String hostname) {
        if (!url.startsWith(hostname)) {
            return false;
        }
        return url.length() == hostname.length() || url.charAt(hostname.length()) == '/';
    }
}

class PeekingIterator implements Iterator<Integer> {

    Integer next;
    Iterator<Integer> iterator;

    public PeekingIterator(Iterator<Integer> iterator) {
        // initialize any member here.
        this.iterator = iterator;
        if (this.iterator.hasNext()) {
            this.next = this.iterator.next();
        } else {
            this.next = null;
        }
    }

    // Returns the next element in the iteration without advancing the iterator.
    public Integer peek() {
        return next;
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    @Override
    public Integer next() {
        Integer temp = next;
        if (iterator.hasNext()) {
            this.next = iterator.next();
        } else {
            this.next = null;
        }
        return temp;
    }

    @Override
    public boolean hasNext() {
        return next != null;
    }
}

class Solution {

    public int findPairs(int[] nums, int k) {
        if(k<0)return 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        int count = 0;
        if (k == 0) {
            for (int num : map.keySet()) {
                if (map.get(num) != 1) {
                    count++;
                }
            }
            return count;
        }
        for (int num : map.keySet()) {
            if (map.containsKey(num + k)) {
                count++;
            }
        }
        return count;
    }
}

public class LFUCache {
    
    private int min;

    private final int capacity;
    private final HashMap<Integer, Integer> keyToVal;
    private final HashMap<Integer, Integer> keyToCount;
    private final HashMap<Integer, LinkedHashSet<Integer>> countToLRUKeys;
    
    public LFUCache(int capacity) {
        this.min = -1;
        this.capacity = capacity;
        this.keyToVal = new HashMap<>();
        this.keyToCount = new HashMap<>();
        this.countToLRUKeys = new HashMap<>();
    }
    
    public int get(int key) {
        if (!keyToVal.containsKey(key)) return -1;
        
        int count = keyToCount.get(key);
        countToLRUKeys.get(count).remove(key); // remove key from current count (since we will inc count)
        if (count == min && countToLRUKeys.get(count).size() == 0) min++; // nothing in the current min bucket
        
        putCount(key, count + 1);
        return keyToVal.get(key);
    }
    
    public void put(int key, int value) {
        if (capacity <= 0) return;
        
        if (keyToVal.containsKey(key)) {
            keyToVal.put(key, value); // update key's value
            get(key); // update key's count
            return;
        } 
        
        if (keyToVal.size() >= capacity)
            evict(countToLRUKeys.get(min).iterator().next()); // evict LRU from this min count bucket
        
        min = 1;
        putCount(key, min); // adding new key and count
        keyToVal.put(key, value); // adding new key and value
    }
    
    private void evict(int key) {
        countToLRUKeys.get(min).remove(key);
        keyToVal.remove(key);
    }
    
    private void putCount(int key, int count) {
        keyToCount.put(key, count);
        countToLRUKeys.computeIfAbsent(count, ignore -> new LinkedHashSet<>());
        countToLRUKeys.get(count).add(key);
    }
}

/**
loop over 1->26 so find the max length with:
h:[1,26] and k so that
the length has h unique char and all char repeat at least k times.
*/
class Solution {
    public int longestSubstring(String s, int k) {
        char[] str = s.toCharArray();
        int[] count = new int[26];
        int maxLen = 0;
        int strLen = str.length;
        //count the number of unique character
        int charCount=0;
        for(char c:str){
            if(count[c-'a']++==0){
                charCount++;
            }
        }
        //only need to loop from 1 to charCount since it's the max unique char can reach.
        for (int h = 1; h <= charCount; h++) {
            count = new int[26];
            int i = 0, j = 0, unique = 0, noLessThanK = 0;
            while (j < strLen) {
                if (unique <= h) {
                    int idx = str[j] - 'a';
                    if (count[idx] == 0) {
                        unique++;
                    }
                    count[idx]++;
                    if (count[idx] == k) {
                        noLessThanK++;
                    }
                    j++;
                } else {
                    int idx = str[i] - 'a';
                    if (count[idx] == k) {
                        noLessThanK--;
                    }
                    count[idx]--;
                    if (count[idx] == 0) {
                        unique--;
                    }
                    i++;
                }
                //why j-i instead of j-i+1?
                //because after update and make it valid, i or j will +1.
                //so the actual lenth for valid str is j-i.
                if (h == unique && h == noLessThanK) {
                    maxLen = Math.max(maxLen, j - i);
                }
            }
        }

        return maxLen;
    }
}

class FizzBuzz {
    private int n;
    private int num = 1;

    public FizzBuzz(int n) {
        this.n = n;
    }

    public synchronized void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
        while (num <= n) {
            if (num % 15 == 0) {
                printFizzBuzz.run();
                num++;
                //notifyAll will let the other thread to stop wait and continue;
                notifyAll();
            } else {
                wait();
            }
        }
    }

    public synchronized void fizz(Runnable printFizz) throws InterruptedException {
        while (num <= n) {
            if (num % 3 == 0 && num % 5 != 0) {
                printFizz.run();
                num++;
                notifyAll();
            } else {
                wait();
            }
        }
    }

    public synchronized void buzz(Runnable printBuzz) throws InterruptedException {
        while (num <= n) {
            if (num % 3 != 0 && num % 5 == 0) {
                printBuzz.run();
                num++;
                notifyAll();
            } else {
                wait();
            }
        }
    }

    public synchronized void number(IntConsumer printNumber) throws InterruptedException {
        while (num <= n) {
            if (num % 3 != 0 && num % 5 != 0) {
                printNumber.accept(num);
                num++;
                notifyAll();
            } else {
                wait();
            }
        }
    }
}

import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;
import java.util.function.IntConsumer;

class FizzBuzz {

    private int n;

    CyclicBarrier cyclicBarrier;

    public FizzBuzz(int n) {
        this.n = n;
        cyclicBarrier = new CyclicBarrier(4);
    }

    public  void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
        try {
            for (int i = 1; i <= n; i++) {
                if (i % 15 == 0) {
                    printFizzBuzz.run();
                }
                cyclicBarrier.await();
            }
        } catch (
            BrokenBarrierException e) {
        }
    }

    public  void fizz(Runnable printFizz) throws InterruptedException {
        try {
            for (int i = 1; i <= n; i++) {
                if (i % 3 == 0 && i % 5 != 0) {
                    printFizz.run();
                }
                cyclicBarrier.await();
            }
        } catch (BrokenBarrierException e) {
        }
    }

    public  void buzz(Runnable printBuzz) throws InterruptedException {
        try {
            for (int i = 1; i <= n; i++) {
                if (i % 3 != 0 && i % 5 == 0) {
                    printBuzz.run();
                }
                cyclicBarrier.await();
            }
        } catch (BrokenBarrierException e) {
        }
    }

    public  void number(IntConsumer printNumber) throws InterruptedException {
        try {
            for (int i = 1; i <= n; i++) {
                if (i % 3 != 0 && i % 5 != 0) {
                    printNumber.accept(i);
                }
                cyclicBarrier.await();
            }
        } catch (
            BrokenBarrierException e) {
        }

    }
}

/**
dp[i] is the min taps needed to water first i gardens

*/
class Solution {
    public int minTaps(int n, int[] ranges) {
        int[] dp = new int[n+1];
        Arrays.fill(dp,n+3);
        //dp[0] = [0] as we need no tap to water nothing.
        dp[0]= 0 ;
        for(int i = 0;i<=n;i++){
            int k = ranges[i];
            int start = Math.max(0,i-k+1);
            int end = Math.min(i+k,n);
            int pre = dp[Math.max(0,i-k)] + 1;
            for(int j = start;j<=end;j++){
            	//if we put a tap at i, then j is watered
            	//so to water j, either dp[j] which it's alreadyed watered by previous tap
            	//or watered by i so the total number is dp[i-k] + 1.
                dp[j] = Math.min(dp[j],pre);
            }
        }
        
        //if dp[n] is larger than n+3, means at least one garden does not get watered.
        return dp[n]<n+3?dp[n]:-1;
    }
}

class Solution {

    int[][] memo;
    int[][] jump;
    final static int MOD = 1000000007;

    public int knightDialer(int N) {
        memo = new int[10][N + 1];
        jump = new int[][][[4, 6], [6, 8], [7, 9], [4, 8], [3, 9, 0], [], [1, 7, 0], [2, 6], [1, 3], [2, 4}};
        for (int i = 0; i < 10; i++) {
            memo[i][1] = 1;
        }
        int sum = 0;
        for (int i = 0; i < 10; i++) {
            sum = (sum + getNumber(i, N)) % MOD;
        }
        return sum;
    }

    private int getNumber(int start, int N) {
        if (memo[start][N] != 0) {
            return memo[start][N];
        }
        int sum = 0;
        for (int next : jump[start]) {
            sum = (sum + getNumber(next, N - 1)) % MOD;
        }
        memo[start][N] = sum;
        return sum;
    }
}

class Codec {

    // Encodes a tree to a single string.
    public String serialize(Node root) {
        if (root == null) {
            return "";
        }
        List<String> list = new LinkedList<>();
        buildString(root, list);
        return String.join(",", list);
    }

    public void buildString(Node root, List<String> list) {
        if (root.children == null) {
            list.add(String.valueOf(root.val));
            list.add(String.valueOf(0));
            return;
        }
        list.add(String.valueOf(root.val));
        list.add(String.valueOf(root.children.size()));
        for (Node child : root.children) {
            buildString(child, list);
        }
    }

    // Decodes your encoded data to tree.
    public Node deserialize(String data) {
        if (data.isEmpty()) {
            return null;
        }
        Queue<String> queue = new ArrayDeque<String>(Arrays.asList(data.split(",")));
        return deserializeHelper(queue);
    }

    public Node deserializeHelper(Queue<String> queue) {
        Node root = new Node();
        root.val = Integer.parseInt(queue.poll());
        int size = Integer.parseInt(queue.poll());
        root.children = new ArrayList<Node>(size);
        for (int i = 0; i < size; i++) {
            root.children.add(deserializeHelper(queue));
        }

        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

//same idea as find sum array. using pre sum.
class Solution {

    public int pathSum(TreeNode root, int sum) {
        if(root==null){
            return 0;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        return helper(root, map, 0, sum);
    }

    public int helper(TreeNode root, HashMap<Integer, Integer> map, int curSum, int sum) {
        //current sum from root to this node.
        curSum += root.val;
        //find count of array sum to sum.
        // cur-sum + sum  = cur
        int res = map.getOrDefault(curSum - sum,0);
        //put current sum into array.
        map.put(curSum,map.getOrDefault(curSum,0)+1);
        if(root.left!=null){
            res += helper(root.left,map,curSum,sum);
        }
        if(root.right!=null){
            res += helper(root.right,map,curSum,sum);
        }
        //need to remove because will go for different node.
        map.put(curSum,map.get(curSum)-1);
        return res;
    }
}

//straightforward storing all information using hashmaps.
class UndergroundSystem {

    HashMap<Integer,String> traveling;
    HashMap<Integer,Integer> checkinTime;
    HashMap<String,Double> time;
    HashMap<String,Integer> timeCount;

    public UndergroundSystem() {
        traveling = new HashMap<>();
        checkinTime = new HashMap<>();
        timeCount = new HashMap<>();
        time = new HashMap<>();
    }

    public void checkIn(int id, String stationName, int t) {
        traveling.put(id,stationName);
        checkinTime.put(id,t);
    }

    public void checkOut(int id, String stationName, int t) {
        String start = traveling.get(id);
        int startTime = checkinTime.get(id);
        String interval = start+" "+stationName;
        int timeInterval = t-startTime;
        int count = timeCount.getOrDefault(interval,0);
        Double average = (time.getOrDefault(interval,0.0D)*count+timeInterval) / (count+1);
        timeCount.put(interval,count+1);
        time.put(interval,average);
    }

    public double getAverageTime(String startStation, String endStation) {
        String interval = startStation+" "+endStation;
        return time.get(interval);
    }
}

class Solution {

    int[][] dirs = new int[][][[0, 1], [0, -1], [-1, 0], [1, 0]];

    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0 || rooms[0].length == 0) {
            return;
        }
        int rowLen = rooms.length;
        int colLen = rooms[0].length;
        //start from any gates to find min distance.
        for (int row = 0; row < rowLen; row++) {
            for (int col = 0; col < colLen; col++) {
                if (rooms[row][col] == 0) {
                    helper(rooms, 0, row, col);
                }
            }
        }
    }

    public void helper(int[][] rooms, int distance, int row, int col) {
        rooms[row][col] = distance;
        for (int[] dir : dirs) {
            int new_row = row + dir[0];
            int new_col = col + dir[1];
            //no need to check visited cause have condition rooms[new_row][new_col] > rooms[row][col]
            //if visited, then this condition will never meet.
            if (new_row >= 0 && new_row < rooms.length && new_col >= 0 && new_col < rooms[new_row].length
                && rooms[new_row][new_col] != -1 && rooms[new_row][new_col] > rooms[row][col]) {
                helper(rooms, distance + 1, new_row, new_col);
            }
        }
    }
}

/**
1,1,2,3,3,4,4,8,8
0,1,2,3,4,5,6,7,8
E,O,N,O,E,O,E,O,E
pair will transfer from Even,Odd to Odd,Even after the single number.
Use Binary search to find.
*/
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int len = nums.length;
        int start = 0, end = nums.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            //if mid is valid
            if (mid - 1 >= 0 && mid + 1 < len && nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1]) {
                return nums[mid];
            } else if ((mid + 1 < len && nums[mid] == nums[mid + 1] && mid % 2 == 0) || (mid - 1 >= 0 && nums[mid] == nums[mid - 1] && mid % 2 != 0)) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return nums[start];
    }
}

class Solution {
    int[][] dirs = new int[][][[0, 1], [0, -1], [1, 0], [-1, 0]];

    public int shortestPath(int[][] grid, int k) {
        int n = grid.length;
        int m = grid[0].length;
        Queue<int[]> q = new LinkedList();
        boolean[][][] visited = new boolean[n][m][k + 1];
        visited[0][0][0] = true;
        q.offer(new int[]{0, 0, k});
        int res = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] info = q.poll();
                int r = info[0], c = info[1], curK = info[2];
                if (r == n - 1 && c == m - 1) {
                    return res;
                }
                for (int[] dir : dirs) {
                    int nextR = dir[0] + r;
                    int nextC = dir[1] + c;
                    int nextK = curK;
                    if (nextR >= 0 && nextR < n && nextC >= 0 && nextC < m) {
                    	//use a elimination.
                        if (grid[nextR][nextC] == 1) {
                            nextK--;
                        }
                        //if only there remains elimination can go through next.
                        if (nextK >= 0 && !visited[nextR][nextC][nextK]) {
                            visited[nextR][nextC][nextK] = true;
                            q.offer(new int[]{nextR, nextC, nextK});
                        }
                    }
                }
            }
            res++;
        }
        return -1;
    }
}

import java.util.*;

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
    	//use deque so no need to sort again.
        Deque<Integer> res = new LinkedList<>();
        //find the position where 
        int idx = Arrays.binarySearch(arr, x);
        int len = arr.length;
        if (idx < 0) {
            idx = -idx - 1;
        }

        int left = idx - 1;
        int right = idx;
        int size = 0;
        
        while (left >= 0 && right < len && size < k) {
            if (x - arr[left] <= arr[right] - x) {
                res.addFirst(arr[left--]);
            } else if (x - arr[left] > arr[right] - x) {
                res.addLast(arr[right++]);
            }
            size++;
        }
        while (left >= 0 && size < k) {
            res.addFirst(arr[left--]);
            size++;
        }

        while (right < len && size < k) {
            res.addLast(arr[right++]);
            size++;
        }
        
        return (List)res;

    }
}

/**
Explanation
Assume we are taking A[i] ~ A[i + k -1].
We can binary research i
We compare the distance between x - A[mid] and A[mid + k] - x

@vincent_gui listed the following cases:
Assume A[mid] ~ A[mid + k] is sliding window

case 1: x - A[mid] < A[mid + k] - x, need to move window go left
-------x----A[mid]-----------------A[mid + k]----------

case 2: x - A[mid] < A[mid + k] - x, need to move window go left again
-------A[mid]----x-----------------A[mid + k]----------

case 3: x - A[mid] > A[mid + k] - x, need to move window go right
-------A[mid]------------------x---A[mid + k]----------

case 4: x - A[mid] > A[mid + k] - x, need to move window go right
-------A[mid]---------------------A[mid + k]----x------

If x - A[mid] > A[mid + k] - x,
it means A[mid + 1] ~ A[mid + k] is better than A[mid] ~ A[mid + k - 1],
and we have mid smaller than the right i.
So assign left = mid + 1.

Important
Note that, you SHOULD NOT compare the absolute value of abs(x - A[mid]) and abs(A[mid + k] - x).
It fails at cases like A = [1,1,2,2,2,2,2,3,3], x = 3, k = 3
*/
public List<Integer> findClosestElements(int[] A, int k, int x) {
        int left = 0, right = A.length - k;
        while (left < right) {
            int mid = (left + right) / 2;
            if (x - A[mid] > A[mid + k] - x)
                left = mid + 1;
            else
                right = mid;
        }

        return Arrays.stream(A, left, left + k).boxed().collect(Collectors.toList());
    }

//consider the situation two are not overlaped:
//2 is on top of 1 -> rec2[1] >= rec1[3]
//2 is on bottom of 1 -> rec2[3] <= rec1[1]
//2 is on left of 1 -> rec2[2] <= rec1[0]
//2 is on right of 1 -> rec2[0] >= rec1[2]

//otherwise they are overlaped.
class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        if (rec2[1] >= rec1[3] || rec2[3] <= rec1[1] || rec2[2] <= rec1[0] || rec2[0] >= rec1[2]) {
            return false;
        }
        return true;
    }
}

import java.util.*;

class Solution {
    int result;

    public int maxLength(List<String> arr) {
        result = 0;
        if (arr == null || arr.size() == 0) {
            return 0;
        }
        dfs(arr, "", 0);
        return result;
    }

    private void dfs(List<String> arr, String path, int idx) {
        boolean isUnique = isUniqueChars(path);
        if (isUnique) {
            result = Math.max(path.length(), result);
        }

        if (idx == arr.size() || !isUnique) {
            return;
        }


        for (int i = idx; i < arr.size(); i++) {
            dfs(arr, path + arr.get(i), i + 1);
        }

    }

    //Effeicient way to check if the string is unique.
    private boolean isUniqueChars(String str) {

        // An integer to store presence/absence
        // of 26 characters using its 32 bits.
        int checker = 0;

        for (int i = 0; i < str.length(); ++i) {
            int val = (str.charAt(i) - 'a');

            // If bit corresponding to current
            // character is already set
            if ((checker & (1 << val)) > 0)
                return false;

            // set bit in checker
            checker |= (1 << val);
        }

        return true;
    }
}

/**
 * Find the first overlapped interval, keep merging until all overlaped intervals are merged.
 */
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int i=0;
        int len = intervals.length;
        List<int[]> res = new ArrayList<>();
        //skip all intervals that's not overlapped.
        while(i<len && intervals[i][1] <newInterval[0]) {
            res.add(intervals[i++]);
        }
        //keep merging.
        while(i<len && intervals[i][0]<=newInterval[1]){
            newInterval = new int[]{Math.min(intervals[i][0], newInterval[0]), Math.max(intervals[i][1], newInterval[1])};
            i++;
        }
        res.add(newInterval);
        //add the rest non-overlap intervals.
        while(i<len){
            res.add(intervals[i++]);
        }
        return res.toArray(new int[res.size()][]);
    }
}

class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        int p1 = -1, p2 = -1, minDist = Integer.MAX_VALUE;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                p1 = i;
                if (p2 != -1) {
                	//no need to do comparision everytime
                	//only when 
                    minDist = Math.min(minDist, Math.abs(p1 - p2));
                }
            }

            if (words[i].equals(word2)) {
                p2 = i;
                if (p1 != -1) {
                    minDist = Math.min(minDist, Math.abs(p1 - p2));
                }
            }
        }
        return minDist;
    }
}

/**
two situation:
1. all a -> if len == 1 then it's impossible, otherwise replace the last char with 'b'
2. not all a -> replace the first non a char with a and return.
*/
class Solution {
    public String breakPalindrome(String palindrome) {
        char[] charArr = palindrome.toCharArray();
        int len = charArr.length;
        for (int i = 0; i < len / 2; i++) {
            if (charArr[i] != 'a') {
                charArr[i] = 'a';
                return String.valueOf(charArr);
            }
        }
        if (len == 1) {
            return "";
        } else {
            charArr[len - 1] = 'b';
            return String.valueOf(charArr);
        }
    }
}

/**
Main idea is the same BFS except 
*/
class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        if (maze == null || maze.length == 0 || maze[0].length == 0) {
            return false;
        }
        int rowLen = maze.length;
        int colLen = maze[0].length;
        int[][] dirs = new int[][[0, 1], [0, -1], [1, 0], [-1, 0]];
        Queue<int[]> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[rowLen][colLen];
        queue.add(start);
        visited[start[0]][start[1]] = true;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] dir : dirs) {
                int next_row = cur[0];
                int next_col = cur[1];
                //the ball keeps rolling until hit a wall.
                while (next_row >= 0 && next_row < rowLen && next_col >= 0 && next_col < colLen && maze[next_row][next_col] == 0) {
                    next_row += dir[0];
                    next_col += dir[1];
                }
                next_row -= dir[0];
                next_col -= dir[1];
                if (visited[next_row][next_col]) continue;
                visited[next_row][next_col] = true;
                if (next_row == destination[0] && next_col == destination[1]) {
                    return true;
                }
                queue.add(new int[]{next_row, next_col});
            }
        }
        return false;
    }


}

class Solution {

    public int closestValue(TreeNode root, double target) {
        int res = root.val;
        TreeNode cur = root;
        while (cur != null) {
            //must calc everytime or if use a double to store, will overflow.
            if (Math.abs(target - cur.val) < Math.abs(target - res)) {
                res = cur.val;
                //early stop, if the diff is less than 0.5, no other interger can achieve less diff.
                if(Math.abs(target - cur.val)<=0.5){
                    break;
                }
            }
            if (target > cur.val) {
                cur = cur.right;
            } else {
                cur = cur.left;
            }
        }

        return res;
    }
}

import java.util.Arrays;

class Solution {

    public int smallestDivisor(int[] nums, int threshold) {
        int max = 0;
        for(int num:nums){
            max  = Math.max(max,num);
        }
        int left = 1, right = max;
        while(left<right){
            int mid = left+(right-left)/2;
            int sum = getSum(nums,mid);
            if(sum > threshold){
                left = mid+1;
            }else{
                right = mid;
            }
        }
        return left;
    }

    public int getSum(int[] nums, int div) {
        int sum = 0;
        for (int num : nums) {
            //Math.ceil() also works but way slower.
            sum += (num+div-1)/div;
        }
        return sum;
    }
}

/**
No need to store all numbers, just the first k largest.

*/
class KthLargest {

    PriorityQueue<Integer> pq;
    int capacity;
    public KthLargest(int k, int[] nums) {
        this.capacity = k;
        this.pq = new PriorityQueue<>(k);
        for(int num:nums){
            add(num);
        }
    }

    public int add(int val) {
        if(pq.size()<capacity){
            pq.offer(val);
            //if the current smallest one is larger than or equal to val, means no need to update
            //cause the number will update order laster than K, k largest will not be updated
        }else if(pq.peek() < val){
            pq.poll();
            pq.offer(val);
        }

        return pq.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

/**
Special case: BA->52, AB->28, AAA->703
*/
public class Solution {

    public String convertToTitle(int n) {
        StringBuilder result = new StringBuilder();

        while(n>0){
            //handle the situation where n == 26;
            n--;
            result.append( (char)('A' + n % 26));
            n /= 26;
        }

        return result.reverse().toString();
    }
}

/**
Store the information for a certain stop, which buses go through that stop.
then for a certain stop, we can take all possible buses 
and go to all possible stops reachable by these buses.


*/
class Solution {
    public int numBusesToDestination(int[][] routes, int S, int T) {
        HashSet<Integer> visited = new HashSet<>();
        Queue<Integer> q = new LinkedList<>();
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        int ret = 0;

        if (S==T) return 0;

        //Use map to store buses go through a stop.
        for(int i = 0; i < routes.length; i++){
            for(int j = 0; j < routes[i].length; j++){
                ArrayList<Integer> buses = map.getOrDefault(routes[i][j], new ArrayList<>());
                buses.add(i);
                map.put(routes[i][j], buses);
            }
        }

        q.offer(S);
        //loop over level size.
        while (!q.isEmpty()) {
            int len = q.size();
            ret++;
            for (int i = 0; i < len; i++) {
                int cur = q.poll();
                //find all buses I can take from this stop.
                ArrayList<Integer> buses = map.get(cur);
                for (int bus: buses) {
                    if (visited.contains(bus)) continue;
                    visited.add(bus);
                    //if I take this bus, push all stops I get reach.
                    for (int j = 0; j < routes[bus].length; j++) {
                        //skip the current one.
                        if(routes[bus][j]==cur)continue;
                        if (routes[bus][j] == T) return ret;
                        q.offer(routes[bus][j]);
                    }
                }
            }
        }
        return -1;
    }
}

/**
No two characters may map to the same character but a character may map to itself.
So need to store whether the char has been mapped to.
*/
class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] map = new int[256];
        int[] mapped =new int[256];
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if (map[s.charAt(i)]!=0) {
                if (map[s.charAt(i)] != t.charAt(i)) {
                    return false;
                }
            } else if (mapped[t.charAt(i)]!=0) {
                return false;
            }else{
                map[s.charAt(i)] = t.charAt(i);
                mapped[t.charAt(i)] = 1;
            }
        }
        return true;
    }
}

/**
Recursively find the node that has the same value as the key, while setting the left/right nodes equal to the returned subtree
Once the node is found, have to handle the below 4 cases
node doesn't have left or right - return null
node only has left subtree- return the left subtree
node only has right subtree- return the right subtree
node has both left and right - find the minimum value in the right subtree, set that value to the currently found node, then recursively delete the minimum value in the right subtree
*/
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null){
            return null;
        }
        //key exist on left part, change root.left
        if(root.val > key){
            root.left = deleteNode(root.left,key);
        }else if(root.val < key){
            //else change root.right
            root.right = deleteNode(root.right,key);
        }else{
            //if this is the one to be deleted
            //no child, delete and return null.
            if(root.left==null && root.right==null){
                return null;
            }
            if(root.left==null){
                return root.right;
            }
            if(root.right==null){
                return root.left;
            }

            //find the min node on right tree.
            TreeNode min = findMin(root.right);
            //change the current one value woth min value.
            root.val = min.val;
            //recursivly delete min value on the right tree.
            root.right = deleteNode(root.right,min.val);
        }
        return root;
    }

    private TreeNode findMin(TreeNode root){
        while(root.left!=null){
            root = root.left;
        }
        return root;
    }
}

/**
Find intervals, merge it, than insert into StringBuilder

*/
class Solution {
    public String boldWords(String[] words, String S) {
    

    }

}

public String boldWords(String[] words, String S) {
        boolean[] bold = new boolean[S.length() + 1];
        for (String w : words) {
            int start = S.indexOf(w, 0);
            while (start != -1) {
                Arrays.fill(bold, start, start + w.length(), true);
                start = S.indexOf(w, start + 1);
            }
        }
        StringBuilder r = new StringBuilder().append(bold[0] ? "<b>" : "");
        for (int i = 0; i < bold.length - 1; i++) {
            r.append(S.charAt(i));
            if (!bold[i] && bold[i + 1]) r.append("<b>");
            else if (bold[i] && !bold[i + 1]) r.append("</b>");
        }
        return r.toString();
    }

/**
cmin, cmax is the number of opening we are waiting to close.
cmax assume all * as ( so it's max.
cmin assume all * as ) so it's min.
but cmin will always be larger or equal to 0 cause otherwise the current string is invalid.
so in order to make it valid, cmin = Math.max(cmin,0)

if while looping, cmax is smaller than 0, means there's no way the current string is valid.

at the end, we have to make sure no opening are waiting to be closed, that is cmin == 0.
*/
class Solution {
    public boolean checkValidString(String s) {
        int cmin = 0, cmax = 0;
        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            if (cur == '(') {
                cmin++;
                cmax++;
            } else if (cur == ')') {
                cmax--;
                cmin = Math.max(--cmin, 0);
            } else {
                cmax++;
                cmin = Math.max(--cmin, 0);
            }
            if (cmax < 0) {
                return false;
            }
        }

        return cmin == 0;
    }
}

import java.util.Arrays;

class Solution {
    public int triangleNumber(int[] nums) {
        //sort the nums first, so only need to check condition 1 + 2 < 3
        Arrays.sort(nums);
        int i = 0;
        //skip 0 as it never make a valid triangle.
        while (i < nums.length) {
            if (nums[i] != 0) {
                break;
            }
            i++;
        }
        int count = 0;
        while (i <= nums.length - 3) {
            //try every possible number after nums[i]
            for (int j = i + 1; j <= nums.length - 2; j++) {
                int key = nums[i] + nums[j] - 1;
                //find the position of last valid third number.
                int idx = Arrays.binarySearch(nums, j + 1, nums.length, key);
                if (idx < 0) {
                    idx = -idx - 2;
                }
                //binary search does not guarantee it's the last one.
                //need to move to last idx of valid number.
                while (idx < nums.length && nums[i] + nums[j] > nums[idx]) {
                    idx++;
                }
                //all numbers from j to idx-1 is valid
                count += idx - j - 1;
            }
            i++;
        }
        return count;
    }
}

/**
Keep search next node until next val.
*/
class Solution {

    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null){
            pre = cur;
            while(cur!=null && cur.val==pre.val){
                cur = cur.next;
            }
            pre.next = cur;
            pre = pre.next;
        }
        return head;
    }
}

class Solution {
    public boolean backspaceCompare(String S, String T) {
        int i = S.length() - 1;
        int j = T.length() - 1;
        int back = 0;
        while (true) {
            back = 0;
            //find the first char that will exist in the result.
            while (i >= 0 && (back > 0 || S.charAt(i) == '#')) {
                back += S.charAt(i) == '#' ? 1 : -1;
                i--;
            }

            back = 0;
            //find the first char that will exist in the result.
            while (j >= 0 && (back > 0 || T.charAt(j) == '#')) {
                back += T.charAt(j) == '#' ? 1 : -1;
                j--;
            }

            //compare them.
            if (i >= 0 && j >= 0 && S.charAt(i) == T.charAt(j)) {
                i--;
                j--;
            } else {
                break;
            }
        }
        return i == -1 && j == -1;
    }
}

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        //key point: sort first.
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        dfs(candidates,0,target,new ArrayList<>(),res);
        return res;
    }

    private void dfs(int[] candidates, int idx, int runningSum, List<Integer> temp, List<List<Integer>> res){
        if(runningSum<=0){
            if(runningSum==0){
                res.add(new ArrayList<>(temp));
            }
            return;
        }
        for(int i = idx;i<candidates.length;i++){
            //key point to prevent dup:
            //for a certain number, it can only appear at position idx once.
            //but if we put num at idx, we still have chance to put num at idx+1 by dfs(i+1)
            if(i > idx && candidates[i-1]==candidates[i]){
                continue;
            }
            temp.add(candidates[i]);
            dfs(candidates, i+1,runningSum-candidates[i],temp, res);
            temp.remove(temp.size()-1);
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.combinationSum2(new int[]{10,1,2,7,6,1,5},8));
    }
}