class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        
        for(int i=0; i<words.length-1; i++){
            if(!check(words[i], words[i+1], order))
                return false;
        }
        
        return true;
    }
    
    public boolean check(String s1, String s2, String order){
        for(int i=0; i<Math.min(s1.length(), s2.length()); i++){
            if(order.indexOf(s1.charAt(i))<order.indexOf(s2.charAt(i)))
                return true;
            if(order.indexOf(s1.charAt(i))>order.indexOf(s2.charAt(i)))
                return false;
        }
        
        return s1.length()<=s2.length();
    }
}

class UndergroundSystem {
    Map<Integer, Pair<String, Integer>> checkInMap = new HashMap<>();
    Map<String, Pair<Integer, Integer>> timeMap = new HashMap<>();
    public UndergroundSystem() {}
    public void checkIn(int id, String stationName, int t) {
        checkInMap.put(id, new Pair<>(stationName, t));
    }
    public void checkOut(int id, String stationName, int t) {
        Pair<String, Integer> checkIn = checkInMap.get(id);
        String stations = checkIn.getKey()+"-"+stationName;
        Pair<Integer, Integer> times = timeMap.getOrDefault(stations, new Pair<>(0, 0));
        int sum=(t-checkIn.getValue())+times.getKey();
        timeMap.put(stations, new Pair<>(sum, times.getValue()+1));
    }
    public double getAverageTime(String startStation, String endStation) {
        Pair<Integer, Integer> times = timeMap.get(startStation+"-"+endStation);
        return (double)times.getKey()/times.getValue();
    }
}

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }
}

class Solution {
    public int[] sortByBits(int[] arr) {
        int n=arr.length;
        for (int i = 0; i < n-1; i++){
            for (int j = 0; j < n-i-1; j++){
                if (func(arr[j]) > func(arr[j+1]) || (arr[j] > arr[j+1] && func(arr[j]) == func(arr[j+1])))
                {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        return arr;
    }
    public int func(int n) {
        int count=0;
        while(n!=0){
            if((n&1)==1)
            count++;
            n=n>>>1;
        }
        return count;
    }
}

class Cashier {
    int count=0, order;
    double discountProduct;
    Map<Integer, Integer> map = new HashMap<>();
    
    public Cashier(int n, int discount, int[] products, int[] prices) {
        this.order=n;
        this.discountProduct=1-(double)discount/100;
        for(int i=0; i<prices.length; i++){
            map.put(products[i], prices[i]);
        }
    }
    
    public double getBill(int[] product, int[] amount) {
        count++;
        int total=0;
        for(int i=0; i<amount.length; i++){
            total+=map.get(product[i])*amount[i];
        }
        
        return count%order==0? total*discountProduct : total;
    }
}

class Bank {
    long [] balance;
    public Bank(long[] balance) {this.balance=balance;}
    
    public boolean transfer(int account1, int account2, long money) {
        if(account1>balance.length || account2>balance.length || balance[--account1]<money)
            return false;
        
        balance[account1]-=money;
        balance[account2-1]+=money;
        return true;
    }
    
    public boolean deposit(int account, long money) {
        if(account>balance.length)
            return false;
        balance[account-1]+=money;
        return true;
    }
    
    public boolean withdraw(int account, long money) {
        if(account>balance.length || balance[--account]<money)
            return false;
        balance[account]-=money;
        return true;
    }
}

select product_id, 'store1' as store, store1 as price from products where store1 is not null
union
select product_id, 'store2' as store, store2 as price from products where store2 is not null
union
select product_id, 'store3' as store, store3 as price from products where store3 is not null

class Solution {
    public int timeRequiredToBuy(int[] tickets, int k) {
        int time=0;
        while(tickets[k]!=0){
            for(int i=0; i<tickets.length; i++){
                if(tickets[i]-- > 0) time++;
                if(tickets[k]==0) break;
            }
        }
        
        return time;
    }
}

class Solution {
    public int firstUniqChar(String s) {
        int arr[] = new int[26];
        for(Character ch: s.toCharArray()){
            arr[ch-'a']++;
        }
        for(Character ch: s.toCharArray()){
            if(arr[ch-'a']==1)
                return s.indexOf(ch);
        }
        
        return -1;
    }
}

class MyStack {
    Queue<Integer> q = new LinkedList<>();
    Queue<Integer> temp = new LinkedList<>();
    public MyStack() {}
    public void push(int x) {
        q.add(x);
        for(int i=0;i<q.size()-1;i++)
        {
           q.add(q.poll());
        }
    }
    public int pop() {
        return q.remove();
    }
    public int top() {
        return q.peek();
    }
    public boolean empty() {
        return q.isEmpty();
    }
}

class Solution {
    public int maxArea(int[] height) {
        int area=0, temp;
        int left=0, right=height.length-1;
        while(left<right){
            temp=(right-left)*Math.min(height[left], height[right]);
            area=Math.max(area, temp);
            if(height[left]>height[right]) {
                right--;
            } else if(height[left]<height[right]) {
                left++;
            } else {
                left++;
                right--;
            }
        }
        return area;
    }
}

class Solution {
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int m=grid.length, n=grid[0].length, counter=m*n-k%(m*n);
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                list.add(grid[i][j]);
            }
        }
        List<Integer> piece;
        List<List<Integer>> ans = new ArrayList<>();
        for(int i=0; i<m; i++){
            piece = new ArrayList<>();
            for(int j=0; j<n; j++){
                piece.add(list.get(counter++ % (m*n)));
            }
            ans.add(piece);
        }
        return ans;
    }
}

select v.customer_id, count(*) as count_no_trans
from visits v
left join transactions t
on v.visit_id=t.visit_id
where t.transaction_id is null
group by customer_id

class Solution {
    public ListNode mergeNodes(ListNode head) {
        ListNode slow = head.next;
        ListNode fast = head.next;
        int sum=0;
        while(fast!=null){
            sum+=fast.val;
            if(fast.val==0){
                slow.val=sum;
                slow.next=fast.next;
                slow=slow.next;
                sum=0;
            }
            fast=fast.next;
        }
        return head.next;
    }
}

class Solution {
    int sum=0;
    public int sumEvenGrandparent(TreeNode root) {
        if(root==null) return 0;
        helper(root, null, null);
        return sum;
    }
    
    public void helper(TreeNode node, TreeNode p, TreeNode gp){
        if(node == null) return;
        
        if(gp!=null && gp.val%2==0){
            sum+=node.val;
        }
        
        helper(node.left, node, p);
        helper(node.right, node, p);
    }
}

select sell_date,
count(distinct product) as num_sold,
group_concat(distinct product order by product) as products
from activities
group by sell_date

class Solution {
    int sum=0;
    public TreeNode bstToGst(TreeNode root) {
        if(root==null) return null;
        bstToGst(root.right);
        sum+=root.val;
        root.val=sum;
        bstToGst(root.left);
        
        return root;
    }
}

class Solution {
    int sum=0;
    public TreeNode convertBST(TreeNode root) {
        if(root==null) return null;
        convertBST(root.right);
        sum+=root.val;
        root.val=sum;
        convertBST(root.left);
        
        return root;
    }
}