//using binary search twice and find left/right side each time;
public int[] searchRange(int[] nums, int target) {
  int i = 0;
  int j = nums.length - 1;
  int[] res = new int[]{-1, -1};
  if (nums.length == 0) {
    return res;
  }
  int mid = 0;
  while (i < j) {
    mid = (i + j) / 2;
//has to use >= not > because we are looking at left side,
//so when it's equal should set right j to mid;
    if (nums[mid] >= target) {
      j = mid;
    } else {
      i = mid + 1;
    }
  }
  if (nums[i] != target) {
    return res;
  }
  res[0] = i;
//no need to set i to 0;
  j = nums.length - 1;
  while (i < j) {
    mid = (i + j) / 2 + 1;
    if (nums[mid] > target) {
      j = mid - 1;
    } else {
      i = mid;
    }
  }
  res[1] = j;
  return res;
}

//Using Binary Search, if found then return, if not, just return the lo.
public int searchInsert(int[] nums, int target) {
      int lo=0,hi=nums.length-1;
      while(lo<=hi){
        int mid = (lo+hi)/2;
        if(nums[mid]==target){
          return mid;
        }else if(nums[mid]<target){
          lo = mid + 1;
        }else{
          hi = mid - 1;
        }
      }
      return lo;
    }

class Solution {

    //Global Variable for convenience
    HashSet<Integer> hash;
    int N;

    public List<List<Integer>> combinationSum(int[] candidates, int target)     {
        hash = new HashSet(Arrays.asList(candidates));
        N = candidates.length;
        List<List<Integer>> res = new ArrayList();
        helper(candidates,0,new ArrayList(),target,res);
        return res;
    }

    //using recursion and construct
    public void helper(int[] candidates, int index,List<Integer> temp,
     int target,List<List<Integer>> res){
        //situation that should stop searching.
        if(index>=N || target<0){return;}
        //if found one, add to the result.
        if(target==0){
            //must using deep copy! Or result will be all empty list.
            List r = new ArrayList();
            r.addAll(temp);
            res.add(r);
        }
        for(int i = index;i<candidates.length;i++){
            //adding candidates to temp one at a time
            //!!must using index to record position, or it will have duplicate result
            //like [2,2,3] & [2,3,2].
            temp.add(candidates[i]);
            helper(candidates,i, temp,target-candidates[i],res);
            //remember to remove it afterward.
            temp.remove(temp.size()-1);
        }
    }
}

class Solution {


    int[] A;
    int N;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        A = candidates;
        N = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        helper(res,new ArrayList<Integer>(),target,0);
        return res;
    }

    private void helper(List<List<Integer>> res, List<Integer> path,int remain, int index){
        if(remain<=0){
            if(remain == 0){
                res.add(new ArrayList<Integer>(path));
            }
            return;
        }
        for(int i = index;i<N;i++){
            //tricky part: avoid duplication.
            if(i>index && A[i-1]==A[i])continue;
            path.add(A[i]);
            helper(res,path,remain-A[i],i+1);
            path.remove(path.size()-1);
        }
    }
}

class Solution {
    //the clever version of the solution.
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        for(int i = n-1;i>=0;i--){
            //if the current digits will not carry one
            //then just add one and return.
            if(digits[i]<9){
                digits[i]++;
                return digits;
            }else{
                //if current digit is 9, then need to carry one
                //since we only add one, then the current digits must be 0.
                //set digit to 0 and continue to the next digit.
                digits[i] = 0;
            }
        }
        //if finally we still not return, means it's 9 all the way, so just carry One
        int[] newNumber = new int [n+1];
        newNumber[0] = 1;
        return newNumber;
    }
}

class Solution {
    //using iteration to go through every bit of the string and add them up.
    //Recording carry and add to next iteration.
    public String addBinary(String a, String b) {
        StringBuffer res = new StringBuffer();
        //start from the end of the string.
        int i = a.length()-1, j = b.length() -1;
        //record carry for each step.
        int carry = 0;
        while(i>=0 || j>=0){
            int sum = carry;
            if(i>=0){sum += (a.charAt(i--)-'0');}
            if(j>=0){sum += (b.charAt(j--)-'0');}
            //update carry.
            carry = sum / 2;
            res.append(sum%2);
        }
        if(carry == 1){
            res.append(1);
        }
        return res.reverse().toString();
    }
}

class Solution {
    //the idea is to go through the array twice, one from head to end, one from end to head.
    public int candy(int[] ratings) {
        int N = ratings.length;
        if(N==0){return 0;}
        int[] height = new int[N];
        int res = 0;
        height[0] =1;
        //first iteration, make sure the current one is more than left one.
        for(int i = 1;i<N;i++){
            height[i] = 1;
            if(ratings[i]>ratings[i-1]){
                height[i] = height[i-1]+1;
            }
        }
        //make sure suitable to right one.
        for(int i = N-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                height[i] = Math.max(height[i],height[i+1]+1);
            }
        }
        //sum up
        for(int i:height){res += i;}
        return res;
    }
}

class Solution {
    //using map to store location information.
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap();
        for(int i = 0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                int pre = map.get(nums[i]);
                //check if its distance is less than k
                if(i-pre<=k){
                    return true;
                }
            }
            map.put(nums[i],i);
        }
        return false;
    }
}

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

        SortedSet<Long> set = new TreeSet<Long>();  

        for(int j=0; j<nums.length; j++) {  
            SortedSet<Long> subSet =  set.subSet((long)nums[j]-t, (long)nums[j]+t+1);  
            if(!subSet.isEmpty()) return true;  

            if(j>=k) {  
                set.remove((long)nums[j-k]);  
            }  
            set.add((long)nums[j]);  
        }  
        return false;  
    }
}

class Solution {
    public boolean isPalindrome(int x) {
        if(x<0){
            return false;
        }
        String s = String.valueOf(x);
        int i = 0;
        int j = s.length()-1;
        char[] charList = s.toCharArray();
        while(i<=j){
            if(charList[i]!=charList[j]){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

class Solution {
    public boolean isPalindrome(int x) {
        if (x<0 || (x!=0 && x%10==0)) return false;
        int rev = 0;
        while(x>rev){
            rev = rev * 10 + x %10;
            x = x/10;
        }
        return (x==rev||x == rev/10);
    }
}

/**
 * It is also possible to finish the whole process within one pass, but as
 * it is not always a optimal solution. I skip it here. What's more, bit
 * vector can be used here too, but again, it is the same strategy and
 * increase the opportunity of writing wrong code(bit operations are always
 * easy to become a mess and hard to understand
 */
public static boolean isPalindromePermutation(String str){
    String newStr = str.toLowerCase();
    int[] alphabet = new int[256];
    int oddCount = 0;
    // 1 - pass
    for (int i = 0; i < newStr.length(); i++){
        if (newStr.charAt(i) != ' ') {
            alphabet[newStr.charAt(i)]++;
        }
    }
    // 2 - pass
    for (int i = 0; i < alphabet.length; i++){
        if (alphabet[i] != 0){
            if (alphabet[i] % 2 != 0){
                oddCount++;
            }
        }
    }
    if (oddCount > 1){
        return false;
    }

    return true;
}

class Solution {

    int N;
    int[] Nums;
    public List<List<Integer>> permuteUnique(int[] nums) {
        Nums = nums;
        N = nums.length;
        List<List<Integer>> res = new ArrayList();
        //to Avoid duplication.
        boolean[] used = new boolean[N];
        //in order to avoid duplication need to sort and check the one befor is the same.
        Arrays.sort(nums);
        helper(used,new ArrayList(),res);
        return res;
    }

    public void helper(boolean[] used,List<Integer> temp, List<List<Integer>> res){
        //if temp is full ,add to res.But remember to copy it instead of add it to res directly.
        if(temp.size() == N){
            List<Integer> a = new ArrayList(temp);
            res.add(a);
        }
        for(int i = 0; i<N; i++){
            // if the last one is same and not used then continue so it will only appear once.
            if(i>0 && Nums[i-1]==Nums[i] && !used[i-1]) continue;
            if(!used[i]){
                used[i] = true;
                temp.add(Nums[i]);
                helper(used,temp,res);
                temp.remove(temp.size()-1);
                used[i] = false;
            }
        }
    }
}

class Solution {
    /**
      * @param board: the board
        @return: wether the Sudoku is valid
      */
    public boolean isValidSudoku(char[][] board) {
        if(board == null || board.length == 0 || board[0].length == 0) return false;

        int m = 9, n = 9;
        // check row
        boolean[] visited = new boolean[9];
        for(int i = 0; i < m; i++){
            Arrays.fill(visited, false);
            for(int j = 0; j < n; j++){
                if(!precess(visited, board[i][j])) return false;
            }
        }

        for(int i = 0; i < n; i++){
            Arrays.fill(visited, false);
            for(int j = 0; j < m; j++){
                if(!precess(visited, board[j][i])) return false;
            }
        }

        for(int i = 0; i < m; i+=3){

          for(int j = 0; j < n; j+=3){
              Arrays.fill(visited, false);
              for(int k = 0; k < 9; k++){
                  if(!precess(visited, board[i+k/3][j+k%3])) return false;
              }

            }
        }
        return true;

    }

    private boolean precess(boolean[] visited, char c){
        if(c == '.') return true;
        int num = c - '0';
        if(num > 9 || num < 1 || visited[num-1]) return false;
        visited[num-1] = true;
        return true;
    }
};

class Solution {
    public String countAndSay(int n) {
        if(n == 1){
          return "1";
        }
      StringBuffer sb = new StringBuffer("1");
      for(int i = 1;i<n;i++){
        String temp = sb.toString();
        sb = new StringBuffer();
        char c = temp.charAt(0);
        int count  = 1;
        int size = temp.length();
        for(int j = 1;j<size;j++){
          if(temp.charAt(j)==c){
            count++;
          }else{
            sb.append(count);
            sb.append(c);
            count = 1;
            c = temp.charAt(j);
          }
        }
        sb.append(count);
        sb.append(c);
      }
      return sb.toString();
    }
}

class Solution {
    public int evalRPN(String[] tokens) {
      Stack<Integer> s = new Stack();
      for(int i = 0;i<tokens.length;i++){
        String c = tokens[i];
        if(c.equals("+")){
          int a = s.pop();
          int b = s.pop();
          s.push(a+b);
        }else if(c.equals("-")){
          int a = s.pop();
          int b = s.pop();
          s.push(b-a);
        }else if(c.equals("*")){
         int a = s.pop();
          int b = s.pop();
          s.push(a*b);
        }else if(c.equals("/")){
          int a = s.pop();
          int b = s.pop();
          s.push(b/a);
        }else{
          s.push(Integer.parseInt(tokens[i]));
        }
      }
      return s.pop();
    }
}

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
      Map<String,List<Integer>> map = new HashMap();
      List<List<String>> res = new ArrayList();
      for(int i = 0;i<strs.length;i++){
        String s = strs[i];
        char[] c = s.toCharArray();
        Arrays.sort(c);
        s = new String(c);
        List<Integer> l = map.getOrDefault(s,new ArrayList<Integer>());
        l.add(i);
        map.put(s,l);
      }
      for(Map.Entry<String,List<Integer>> e: map.entrySet()){
        List<String> temp = new ArrayList();
        for(int i : e.getValue()){
          temp.add(strs[i]);
        }
        res.add(temp);
      }
      return res;
    }
}

class Solution {
    public void gameOfLife(int[][] board) {
      //     before  after
      // 0    0       0
      // 1    1       1
      // 2    1       0
      // 3    0       1
      int m = board.length, n = board[0].length;
      for(int i = 0; i<m;i++){
        for(int j = 0;j<n ;j++){
          int count = findLivingNeibor(board, i,j);
          if(board[i][j]==1){
            if(count == 2|| count==3){
              board[i][j] = 1;
            }else{
              board[i][j] = 2;
            }
          }else{
            if(count == 3){
              board[i][j] = 3;
            }
          }
        }
      }
      for(int i = 0; i<m;i++){
        for(int j = 0;j<n ;j++){
        board[i][j] = board[i][j]%2;
        }
      }
    }

  public int findLivingNeibor(int[][] board, int i,int j){
    int count = 0;
    int m = board.length, n = board[0].length;
    if(i>0){
      count += board[i-1][j]==1||board[i-1][j]==2?1:0;
    }
    if(i<m-1){
      count += board[i+1][j]==1||board[i+1][j]==2?1:0;
    }
    if(j>0){
      count += board[i][j-1]==1||board[i][j-1]==2?1:0;
    }
    if(j<n-1){
      count += board[i][j+1]==1||board[i][j+1]==2?1:0;
    }
    if(i>0 && j>0){
      count += board[i-1][j-1]==1||board[i-1][j-1]==2?1:0;
    }
    if(i>0 && j<n-1){
      count += board[i-1][j+1]==1||board[i-1][j+1]==2?1:0;
    }
    if(i<m-1 && j>0){
      count += board[i+1][j-1]==1||board[i+1][j-1]==2?1:0;
    }
    if(i<m-1 && j<n-1){
      count += board[i+1][j+1]==1||board[i+1][j+1]==2?1:0;
    }
    return count;

  }
}

class Solution {
    public int hIndex(int[] citations) {
        int len = citations.length;
        if(citations == null || len == 0) return 0;
        int[] record  = new int[len+1];
        for(int c : citations){
            if(c>len){
                record[len]++;
            }else{
                record[c] ++;
            }
        }

        if(record[len]>=len){
            return len;
        }else{
            for(int i = len-1;i>=0;i--){
                record[i] += record[i+1];
                if(record[i]>=i){
                    return i;
                }
            }
        }
        return 0;
    }
}

class Solution {
    public int hIndex(int[] citations) {
        int len = citations.length;
        int low = 0, high = len-1;
      while(low<=high){
        int mid = (low+high)/2;
        if((len-mid)>citations[mid]){
          low = mid + 1;
        }else{
          high = mid-1;
        }
      }
        return len-low;
    }

}

public class Solution {
    /**
     * @param A: Given an integer array
     * @return: void
     */
    public void heapify(int[] A) {
        int start = A.length/2;
        for (int i=start;i>=0;i--)
            shiftDown(i, A);
    }

    private void shiftDown(int ind, int[] A){
        int size = A.length;
        int left = ind*2+1;
        int right = ind*2+2;
        while (left<size || right<size){
            int leftVal = (left<size) ? A[left] : Integer.MAX_VALUE;
            int rightVal = (right<size) ? A[right] : Integer.MAX_VALUE;
            int next = (leftVal<=rightVal) ? left : right;
            if (A[ind]<A[next]) break;
            else {
                swap(A, ind,next);
                ind = next;
                left = ind*2+1;
                right = ind*2+2;
            }
        }
    }

    private void swap(int[] A, int x, int y){
        int temp = A[x];
        A[x] = A[y];
        A[y] = temp;
    }
}

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        if(intervals==null || newInterval==null){
            return null;
        }
        List<Interval> res = new ArrayList();
        int insertIndex = 0;
        //there are only three possible situation, where an interval is to the new interval left/right/intervaled.
        for(Interval interval : intervals){
          //it means this interval is left to the newone.
            if(interval.end < newInterval.start){
                res.add(interval);
                insertIndex++;
            }else if(interval.start > newInterval.end){
              //it means this interval is right to the newone.
                res.add(interval);
            }else{
              //overlapped.
                newInterval.start = Math.min(newInterval.start, interval.start);
                newInterval.end = Math.max(newInterval.end, interval.end);
            }
        }
        //insert to the right position.
        res.add(insertIndex, newInterval);
        return res;
    }
}

class Solution {
  public String numberToWords(int num) {
    if (num == 0) {
      return "Zero";
    }
    String[] bigs = {" Thousand", " Million", " Billion"};
    StringBuilder sb = new StringBuilder();
    // handle less than 1000
    sb.append(intToWords(num % 1000));
    num /= 1000;
    int i = 0;
    while (num > 0) {
      if (num % 1000 != 0) {
        sb.insert(0, intToWords(num % 1000) + bigs[i]);
      }
      i++;
      num /= 1000;
    }
    // need to trim or willl have space at the head or tail.
    return sb.toString().trim();
  }

  private String intToWords(int num) {
    StringBuilder sb = new StringBuilder();
    // Don't forget the space so it will format the string.
    String[] digits = {
      "", " One", " Two", " Three", " Four", " Five", " Six", " Seven", " Eight", " Nine"
    };
    String[] tenth = {
      " Ten",
      " Eleven",
      " Twelve",
      " Thirteen",
      " Fourteen",
      " Fifteen",
      " Sixteen",
      " Seventeen",
      " Eighteen",
      " Nineteen"
    };
    String[] tenMutipleDigit = {
      "", "", " Twenty", " Thirty", " Forty", " Fifty", " Sixty", " Seventy", " Eighty", " Ninety"
    };
    // handle if has three digits.
    if (num >= 100) {
      sb.append(digits[num / 100]).append(" Hundred");
      num %= 100;
    }
    // handle number like 12, 13
    if (num > 9 && num < 20) {
      sb.append(tenth[num - 10]);
    } else {
      if (num >= 20) {
        sb.append(tenMutipleDigit[num / 10]);
        num %= 10;
      }
      sb.append(digits[num]);
    }
    return sb.toString();
  }
}

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if(intervals == null || intervals.size()<=1){
            return intervals;
        }
        List<Interval> res  = new ArrayList();
        //sort based on their start.
        intervals.sort((i1,i2) -> (i1.start - i2.start));
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for(Interval i : intervals){
          //if overlapped, update max end.
            if(i.start <= end){
                end = Math.max(end,i.end);
            }else{
              //if not overlapped, then add to res and restart start and end.
                res.add(new Interval(start,end));
                start = i.start;
                end  = i.end;
            }
        }
        //add last one to res.
        res.add(new Interval(start,end));
        return res;
    }
}

class Solution1 {
    public boolean isIsomorphic(String s, String t) {
        int[] map_a = new int[256];
        int[] map_b = new int[256];
        int N = s.length();
        if(s.length()!=t.length()){
            return false;
        }
        for(int i = 0; i<N; ++i){
            char a = s.charAt(i);
            char b = t.charAt(i);
            if(map_a[a] != map_b[b]){
                return false;
            }
            map_a[a] = i+1;
            map_b[b] = i+1;
        }
        return true;
    }
}

class Solution {
    public String largestNumber(int[] nums) {
        int size = nums.length;
        if(size == 0){
            return "";
        }
        if(size == 1){
            return String.valueOf(nums[0]);
        }
        //create own comparator based on their combined value;
        Comparator<Integer> com = new Comparator<Integer>(){
            public int compare(Integer n1, Integer n2){
                String ab = "" + n1 + n2;
                String ba = "" + n2 + n1;
                return ba.compareTo(ab);
            }
        };
        Integer[] in = new Integer[size];
        for(int i = 0;i<size;i++){
            in[i] = nums[i];
        }
        Arrays.sort(in,com);
        StringBuilder sb = new StringBuilder();
        int i = 0;
        //remove 0 before, in case [0,0,0]=>0
        while((i<size-1) && in[i]==0)i++;
        while (i < size) sb.append(in[i++]);
        return sb.toString();
    }
}

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length==0){
            return "";
        }
        //try every prefix from first element.
        for(int i = 0;i<strs[0].length();i++){
            //use element to compare with other elements.
            for(int j = 0;j<strs.length;j++){
                if(i>=strs[j].length() || strs[j].charAt(i)!=strs[0].charAt(i)){
                    return strs[0].substring(0,i);
                }
            }
        }
        return strs[0];
    }
}

class Solution {
    public int longestConsecutive(int[] nums) {
        Map<Integer,Integer> map = new HashMap();
        int max = 0;
        for(int n:nums){
            if(!map.containsKey(n)){
                //get right boundry of left side.
                int left = map.getOrDefault(n-1,0);
                //left boundry of right side.
                int right = map.getOrDefault(n+1,0);
                int sum = left+ right + 1;
                //means n is in a consequetive subsequence of length sum.
                map.put(n,sum);
                //store max value;
                max = Math.max(max,sum);
                //set boundries
                map.put(n-left,sum);
                map.put(n+right,sum);
            }
        }
        return max;
    }
}

class Solution {
    //it would be better if try bottom-up instead of top-down.
    //which would be easier.
    public int minimumTotal(List<List<Integer>> triangle) {
        int N = triangle.size();
        int M = triangle.get(N-1).size();
        int[] dp = new int[M];
        for(int i=0;i<M;i++){
            dp[i] = triangle.get(N-1).get(i);
        }
        for(int i = N-2;i>=0;i--){
            List<Integer> cur = triangle.get(i);
            for(int j=0;j<cur.size();j++){
                dp[j] = Math.min(dp[j],dp[j+1])+cur.get(j);
            }
        }
        return dp[0];

    }
}

public class Solution {
    //track with two pointer.
    public void moveZeroes(int[] nums) {
        int i = 0, j = 0;
        while (j < nums.length) {
            if (nums[j] != 0) {
                swap(i++, j, nums);
            }
            j++;
        }
    }

    public void swap(int i, int j, int[] nums) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution {
    public String multiply(String num1, String num2) {
        int l1 = num1.length();
        int l2 = num2.length();
        StringBuilder sb = new StringBuilder();
        //if one of it is empty.
        if(l1==0||l2==0){
            return "";
        }
        //if one of them is 0.
        if(num1.equals("0")||num2.equals("0")){
            return "0";
        }
        int[] multi = new int[l1+l2];
        //store multiply at an array, the smaller index is the larger its value are.
        for(int i=0;i<l1;i++){
            for(int j = 0;j<l2;j++){
                multi[i+j+1] += (num1.charAt(i)-'0')*(num2.charAt(j)-'0');
            }
        }
        int carry = 0;
        //use carry to store info about last one.
        for(int i = multi.length-1;i>=1;i--){
            multi[i] += carry;
            carry = multi[i] /10;
            multi[i] %= 10;
            sb.append(multi[i]);
        }
        if(carry != 0){
            sb.append(carry);
        }
        //need to reverse.
        return sb.reverse().toString();
    }
}

public static boolean isOneWay(String str1, String str2) {
    //zero edit.
    if (str1.equals(str2)) {
      return true;
    }
    //cannot insert/remove more than one char.
    if (str1.length() - str2.length() > 1 ||
           str2.length() - str1.length() > 1){
       return false;
   }
    int l1 = str1.length();
    int l2 = str2.length();
    String s1 = null, s2 = null;
    //set s1 to be the shorter one.
    if (l1 < l2) {
      s1 = str1;
      s2 = str2;
    } else {
      s1 = str2;
      s2 = str1;
    }
    int i1 = 0, i2 = 0;
    //only allow one dif.
    boolean isDif = false;
    while (i1 < l1 && i2 < l2) {
      if (s1.charAt(i1) != s2.charAt(i2)) {
        //if meet second dif, then it's a no-no.
        if (isDif) {
          return false;
        }
        isDif=true;
        if(l1==l2){
          i1++;
        }
      }else {
        i1++;
      }
      i2++;
    }
    return true;
  }

class Solution {
  //can use binary search, and for every mid point, choose the side where goes up.
    public int findPeakElement(int[] nums) {
        int low = 0;
        int high = nums.length-1;
        while(low<high){
            int mid1 = (low+high)/2;
            int mid2 = mid1 + 1;
            if(nums[mid1]<nums[mid2]){
                low = mid2;
            }else{
                high=mid1;
            }
        }
        return low;
    }
}

class Solution {
    public int removeDuplicates(int[] nums) {
      if(nums.length == 0){
        return 0;
      }
      int count = 1;
      int slow=0,fast=1;
      while(fast<nums.length){
        if(nums[slow]==nums[fast]){
            fast++;
        }else{
            //move to the next slot.
            nums[++slow] = nums[fast++];
            count++;
        }
      }
      return count;
    }
}
`

//general solution.
class Solution2 {
    public int removeDuplicates(int[] nums) {
        if(nums.length <=1){
            return nums.length;
        }
        int idx = 1;
        for(int i =1;i<nums.length;i++){
            if(nums[i]!=nums[idx-1]){
                nums[idx++] = nums[i];
            }
        }
        return idx;
    }
}

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length <=2){
            return nums.length;
        }
        int idx = 2;
        for(int i = 2;i<nums.length;i++){
            if(nums[i]!=nums[idx-2]){
                nums[idx++] = nums[i];
            }
        }
        return idx;
    }
}

class Solution {
    public int removeElement(int[] nums, int val) {
        int N = nums.length;
        int idx = 0;
        for(int i = 0;i<N;i++){
            if(nums[i]!=val){
                nums[idx++] = nums[i];
            }
        }
        return idx;
    }
}

public class Solution {
    public int reverse(int x) {
        int flag = 0;
        if (x > 0){
            flag = 1;
        } else if (x < 0) {
            flag = -1;
        }
        //to avoid overflow
        long tmp = (long)x;
        long answer = 0;
        tmp *= flag;
        while(tmp > 0){
            answer = answer * 10 + tmp % 10;
            tmp /= 10;
            if (answer > Integer.MAX_VALUE || flag * answer < Integer.MIN_VALUE) return 0;
        }
        return (int)answer*flag;
    }
}

class Solution {
  //get a word at a time.
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        StringBuilder res = new StringBuilder();
        for(int  i =s.length()-1;i>=0;i--){
            char c = s.charAt(i);
            if(c!=' '){
                sb.append(c);
            }
            //break point where to store the word.
            if(c == ' '){
                String temp = sb.reverse().toString();
                res.append(temp);
                //means there are multiple space, and " "should not be added to res.
                if(!temp.equals("")){
                    res.append(' ');
                }
                //clear the sb everytime a word has been put to res.
                sb = new StringBuilder();
            }
        }
        res.append(sb.reverse().toString());
        return res.toString().trim();

    }
}

class Solution {
    public void setZeroes(int[][] matrix) {
        int rowN = matrix[0].length;
        int colN = matrix.length;
        //use firsr row and col to store information, but will lose info itself.
        //keep track whether the first rol/col contains 0;
        boolean row = false;
        boolean col = false;
        //whether first row contains 0.
        for(int n : matrix[0]){
            if(n==0){
                row = true;
                break;
            }
        }
        //whether first col contains 0.
        for(int i = 0;i<colN;i++){
            if(matrix[i][0]==0){
                col = true;
                break;
            }
        }
        //check each elemnts, if contains 0, put 0 to first col and row;
        for(int i = 0;i<rowN;i++){
            for(int j = 0;j<colN;j++){
                if(matrix[j][i]==0){
                    matrix[0][i] = 0;
                    matrix[j][0] = 0;
                }
            }
        }
        //set entire col to 0.
        for(int i = 1;i<rowN;i++){
            if(matrix[0][i]==0){
                for(int j = 0;j<colN;j++){
                    matrix[j][i] = 0;
                }
            }
        }
        //set entire row to 0.
        for(int j = 1;j<colN;j++){
            if(matrix[j][0]==0){
                Arrays.fill(matrix[j],0);
            }
        }
        //see whether first row/col is 0;
        if(row){
            Arrays.fill(matrix[0],0);
        }
        if(col){
                for(int j = 0;j<colN;j++){
                    matrix[j][0] = 0;
                }
            }
    }
}

class Solution {
    public String shortestPalindrome(String s) {
        if(s.length()<2)return s;
        int mid = (s.length()-1)/2;
        String res = "";
        for(int i = mid;i>=0;i--){
            if(s.charAt(i) == s.charAt(i+1)){
                res = check(s,i,i+1);
                if(res!=null)return res;
            }

                res = check(s,i,i);
                if(res!=null)return res;


        }
        return res;
    }
    //check the longest palindorome centered at l and r.
    private String check(String s, int l, int r){
        int i  =1;
        //iterate to find the longest palindrome.
        while(l>=0 && r<s.length()){
            if(s.charAt(l)!= s.charAt(r)){
                break;
            }
            l--;
            r++;
        }
        //if l is not 0, then it's impossible to do the perform.
        if(l>=0){
            return null;
        }else{
            //perform the action and add new char to the head.
            //find the necessary string to add to head.
            StringBuilder sb = new StringBuilder(s.substring(r));
            //reverse.
            sb.reverse();
            return sb.toString() + s;
        }
    }
}

class Solution {
    public int compress(char[] chars) {
        int indexAns = 0,index =0;
        while(index<chars.length){
            char cur  = chars[index];
            int count  =0 ;
            while(index < chars.length && chars[index] == cur){
                index++;
                count++;
            }
            chars[indexAns++] = cur;
            if(count!=1){
                for(char c : String.valueOf(count).toCharArray()){
                    chars[indexAns++] = c;
                }
            }
        }
        return indexAns;
    }
}

class Solution {

    public boolean exist(char[][] board, String word) {
        char[] w = word.toCharArray();
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int y=0; y<board.length; y++) {
    	for (int x=0; x<board[y].length; x++) {
    		if (exist(board,w,visited, x, y, 0)) return true;

    	}
    }
        return false;
    }

    private boolean exist(char[][] board, char[] w, boolean[][] visited, int x, int y, int index){
      //reach the goal, word found.
        if(index == w.length){
            return true;
        }
        //out of bound and alrealdy visited
        if(x<0|| y<0||y>=board.length||x>=board[y].length||visited[y][x]){
            return false;
        }
        //not the same char.
        if(board[y][x]!=w[index]){
            return false;
        }
        visited[y][x] = true;
        //search four different directions.
        boolean exist = exist(board,w,visited,x-1,y,index+1)||
            exist(board,w,visited,x+1,y,index+1)||
            exist(board,w,visited,x,y-1,index+1)||
            exist(board,w,visited,x,y+1,index+1);
        //unvisited current position.
        visited[y][x] = false;
        return exist;
    }
}