class Solution {
	// start with two largest values, as soon as we find a number bigger than both, while both have been updated, return true.
    public boolean increasingTriplet(int[] nums) {
        int small = Integer.MAX_VALUE, large = Integer.MAX_VALUE;
        for (int n : nums) {
            if (n <= small) {
            	// update small if n is smaller than both
                small = n;
            } else if (n <= large) {
            	// update big only if greater than small but smaller than big
                large = n;
            } else {
                return true;
            }
        }
        return false;
    }
}

class Solution {

    public int hIndex(int[] citations) {
        int len = citations.length;
        int[] sum = new int[len + 1];
        for (int c : citations) {
            if (c < len) {
                sum[c]++;
            } else {
                sum[len]++;
            }
        }

        int count = 0;
        for (int i = len; i >= 0; i--) {
            count += sum[i];
            if (count >= i) {
                return i;
            }

        }
        return 0;
    }

class Solution {
    /**
Intuition:
Considering how to change Y to X
Opertation 1: Y = Y / 2 if Y is even
Opertation 2: Y = Y + 1


Explanation:
Obviously,
If Y <= X, we won't do Y / 2 anymore.
We will increase Y until it equals to X

So before that, while Y > X, we'll keep reducing Y, until it's smaller than X.
If Y is odd, we can do only Y = Y + 1
If Y is even, if we plus 1 to Y, then Y is odd, we need to plus another 1.
And because (Y + 1 + 1) / 2 = (Y / 2) + 1, 3 operations are more than 2.
We always choose Y / 2 if Y is even.


Why it's right
Actually, what we do is:
If Y is even, Y = Y / 2
If Y is odd, Y = (Y + 1) / 2

We reduce Y with least possible operations, until it's smaller than X.

And we know that, we won't do Y + 1 twice in a row.
Becasue we will always end with an operation Y / 2.

2N times Y + 1 and once Y / 2 needs 2N + 1 operations.
Once Y / 2 first and N times Y + 1 will end up with same result, but needs only N + 1 operations.


Time complexity
We do Y/2 all the way until it's smaller than X,
time complexity is O(log(Y/X)).
    **/
    public int brokenCalc(int X, int Y) {
        int res = 0;
        while (Y > X) {
            Y = Y % 2 > 0 ? Y + 1 : Y / 2;
            res++;
        }
        return res+(X-Y);
    }
}

class Solution {

/**
The intuition is brute force, don't need any tricky.
One thing to pay attention: A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9.
I just find many sumbmission ignoring this condition.

Here I just want share two observatons with this 1-9 condition:

Assume a magic square:
a1,a2,a3
a4,a5,a6
a7,a8,a9

a2 + a5 + a8 = 15
a4 + a5 + a6 = 15
a1 + a5 + a9 = 15
a3 + a5 + a7 = 15

Accumulate all, then we have:
sum(ai) + 3 * a5 = 60
3 * a5 = 15
a5 = 5

The center of magic square must be 5.

Another observation for other 8 numbers:
The even must be in the corner, and the odd must be on the edge.
And it must be in a order like "43816729" （clockwise or anticlockwise)

**/
  public int numMagicSquaresInside(int[][] grid) {
    int count = 0;
    for (int i = 1; i < grid.length - 1; i++) {
      for (int j = 1; j < grid[0].length - 1; j++) {
        if (grid[i][j] == 5) {
          count += isMagic(i, j, grid) ? 1 : 0;
        }
      }
    }
    return count;
  }


  private boolean isMagic(int i, int j, int[][] grid) {
    String s =
        "" + grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] + grid[i][j + 1] + grid[i
            + 1][j + 1] + grid[i + 1][j] + grid[i + 1][j - 1] + grid[i][j - 1];
    return "4381672943816729".contains(s) || "9276183492761834".contains(s);
  }
}

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {

  public String mostCommonWord(String paragraph, String[] banned) {
    // split paragraph
    // \w means non-word character.
    String[] words = paragraph.toLowerCase().split("\\W+");

    // add banned words to set
    Set<String> set = new HashSet<>(Arrays.asList(banned));

    // add paragraph words to hash map
    Map<String, Integer> map = new HashMap<>();
    for (String word : words) {
      if (!set.contains(word)) {
        map.put(word, map.getOrDefault(word, 0) + 1);
      }
    }

    // get the most frequent word
    int max = 0; // max frequency
    String res = "";
    for (Map.Entry<String,Integer> e : map.entrySet()) {
      if (e.getValue() > max) {
        max = e.getValue();
        res = e.getKey();
      }
    }

    return res;
  }
}

//(1) Loop through level 0 to level n - 2; (2) Traverse this level and connect children.
class Solution {
  public Node connect(Node root) {
    if(root == null){
      return null;
    }
    Node pre = root;
    Node cur = null;
    while(pre.left!=null){
      cur = pre;
      while(cur!=null){
        cur.left.next = cur.right;
        if(cur.next!=null){
          cur.right.next = cur.next.left;
        }
        cur = cur.next;
      }
      pre = pre.left;
    }
    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 List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        helper(root,res);
        return res;
    }

    private int helper(TreeNode root, List<List<Integer>> res) {
        if (root == null) {
            return -1;
        }
        int level = Math.max(helper(root.left,res),helper(root.right,res))+1;
        if(res.size() == level){
            res.add(new ArrayList<>());
        }
        res.get(level).add(root.val);
        root.left = root.right = null;
        return level;
    }
}

/**
 * Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }
 */
public class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        //map's key is column, we assume the root column is zero, the left node will minus 1 ,and the right node will plus 1
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
        Queue<TreeNode> queue = new LinkedList<>();
        //use a HashMap to store the TreeNode and the according cloumn value
        HashMap<TreeNode, Integer> weight = new HashMap<TreeNode, Integer>();
        queue.offer(root);
        weight.put(root, 0);
        int min = 0;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            int w = weight.get(node);
            if (!map.containsKey(w)) {
                map.put(w, new ArrayList<>());
            }
            map.get(w).add(node.val);
            if (node.left != null) {
                queue.add(node.left);
                weight.put(node.left, w - 1);
            }
            if (node.right != null) {
                queue.add(node.right);
                weight.put(node.right, w + 1);
            }
            //update min ,min means the minimum column value, which is the left most node
            min = Math.min(min, w);
        }
        while (map.containsKey(min)) {
            res.add(map.get(min++));
        }
        return res;
    }
}

class Solution {

//BFS
    public boolean isBipartite(int[][] graph) {
        int len = graph.length;
        int[] colors = new int[len];
        for (int i = 0; i < len; i++) {
            if (colors[i] != 0) {
                continue;
            }
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(i);
            colors[i] = 1;
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (int next : graph[cur]) {
                    if (colors[next] == 0) {
                        queue.offer(next);
                        colors[next] = -colors[cur];
                    } else if (colors[next] != -colors[cur]) {
                        return false;
                    }
                }
            }
        }
        return true;

    }

}

class ExamRoom {

    PriorityQueue<Interval> pq;
    int N;

    class Interval {

        int left, right, len;

        public Interval(int left, int right) {
            this.left = left;
            this.right = right;
            if (left == -1) {
                this.len = right;
            } else if (right == N) {
                this.len = N - 1 - left;
            } else {
                this.len = Math.abs(left - right) / 2;
            }

        }
    }

    public ExamRoom(int N) {
        this.pq = new PriorityQueue<Interval>((a, b) -> (a.len == b.len ? a.left - b.left : b.len - a.len));
        this.N = N;
        pq.offer(new Interval(-1, N));
    }

    // O(logn): poll top candidate, split into two new intervals
    public int seat() {
        int seat = 0;
        Interval interval = this.pq.poll();
        if (interval.left == -1) {
            seat = 0;
        } else if (interval.right == N) {
            seat = N - 1;
        } else {
            seat = (interval.left + interval.right) / 2;
        }

        pq.offer(new Interval(interval.left, seat));
        pq.offer(new Interval(seat, interval.right));
        return seat;
    }

    // O(n)Find head and tail based on p. Delete and merge two ends
    public void leave(int p) {
        Interval head = null, tail = null;
        List<Interval> list = new ArrayList<>(pq);
        for (Interval i : list) {
            if (i.left == p) {
                tail = i;
            }
            if (i.right == p) {
                head = i;
            }
            if (head != null && tail != null){
                break;
            }
        }
        pq.remove(head);
        pq.remove(tail);
        pq.offer(new Interval(head.left,tail.right));
    }
}